-1
$\begingroup$

I am studying for NP problems.
To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT to 3-CNF-SAT both proves that it is NP-hard.

I know that 3-CNF-SAT is NP-Complete, because of its number of literals, but this property seems dedicate no effect to proof.
Thanks for any suggestion.

Note: k-CNF-SAT is a conjunctive normal form which k > 3.
And my question is same as the title, I have no idea about this question, since I just only know 3-SAT is a special case of k-SAT.

$\endgroup$
  • 3
    $\begingroup$ What's your question? I don't see a clear question here, just a bunch of declarative statements. I suggest you edit your post to make clear what exactly your question is. Also, what effort have you made so far, what are your thoughts, and where are you stuck? It's not clear exactly what you're trying to accomplish or what you are having difficulty with. $\endgroup$ – D.W. Jan 4 '16 at 7:38
  • 2
    $\begingroup$ What is $k$-CNF-SAT for you? Can you give a formal definition? (In particular, does any clause need to have exactly $k$ literals or at most $k$ literals?) Also, note that the cases $k=1$ and $k=2$ are easy. $\endgroup$ – Yuval Filmus Jan 4 '16 at 8:15
  • 1
    $\begingroup$ Hint: (I use the definition of "exactly $k$"; "at most $k$" is not harder), $3CNF \to kCNF$: padding each clause of $3CNF$ with $k-3$ dummy variables and then adding $2^k - 1$ clauses to ensure that only the case of all dummies being "false" can lead to a satisfying assignment. $kCNF \to 3CNF$: we already have $CNF \to 3CNF$ (see CLRS), and that $kCNF \subseteq CNF$. $\endgroup$ – hengxin Jan 4 '16 at 11:38
  • $\begingroup$ @hengxin Thanks, For 3CNF→kCNF part, May I ask why it needs to add clauses the number of "2^(k)-1" ? how do you get this number ? And why kCNF ⊆ CNF ? Isn't kCNF harder than CNF? $\endgroup$ – proX Jan 4 '16 at 13:13
  • $\begingroup$ @D.W. I have refreshed my question above, thanks for reminding. $\endgroup$ – proX Jan 4 '16 at 13:22
2
$\begingroup$

To reduce $k$-CNF to CNF: every instance of $k$-CNF is an instance of CNF, so the reduction is trivial.

To reduce CNF to $k$-CNF, where $k \ge 3$: convert the CNF formula to a circuit that computes it; then convert the circuit to a 3-CNF formula using the Tseitin transformation. (If your definition of $k$-CNF requires that there be exactly $k$ literals in every clause, then you can pad: introduce $k$ new variables $y_1,\dots,y_k$; for every clause that has less than $k$ literals, add $\lor y_1 \lor y_2 \lor \dots$ to pad it out to exactly $k$ literals; and then add clauses that force all of $y_1,\dots,y_k$ to be false.)

If this is too terse, see our reference question and a good textbook to learn the fundamentals of reductions.

$\endgroup$
  • $\begingroup$ This doesn't necessarily work, depending on the definition of $k$-CNF. $\endgroup$ – Yuval Filmus Jan 4 '16 at 18:49
  • $\begingroup$ @YuvalFilmus, OK. Edited to address the concern that I suspect you have. $\endgroup$ – D.W. Jan 4 '16 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.