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.

Improve this question
$\endgroup$
10
  • 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. ♦
    Commented Jan 4, 2016 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
    Commented Jan 4, 2016 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
    Commented Jan 4, 2016 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
    Commented Jan 4, 2016 at 13:13
  • $\begingroup$ @D.W. I have refreshed my question above, thanks for reminding. $\endgroup$
    – proX
    Commented Jan 4, 2016 at 13:22

2 Answers 2

Reset to default
3
$\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.

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

A clause in 3-CNF can be converted to k-CNF by adding extra padding:

(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')

Keep adding this extra padding until each clause contains k literals.

Same way, a k-CNF clause can be broken until each clause contains 3 literals.

(l1 V l2 V l3 V l4) can be broken into (l1 V l2 V y) ∧ (l3 V l4 V y') by resolution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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