To answer the question below,

4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?

I was going to prove that 4-SAT is in NP-complete. But I saw that the way to prove CNF-SAT is in NP-complete is a bit different to the way of proving 4-SAT is in NP-complete.

Is it sufficient that I just answer that question by proving 4-SAT is in NP-complete?

Thanks in advance!

  • $\begingroup$ Why not reduce 3-SAT to 4-SAT? $\endgroup$ – xskxzr Jun 9 '18 at 4:17
  • $\begingroup$ so reducing 3-SAT to 4-SAT is to prove that 4-SAT is in NP-hard? $\endgroup$ – peterparkerr Jun 9 '18 at 4:27
  • $\begingroup$ Please don't delete your question once you've already received an answer. That's impolite to answerers. Part of our mission here is to build up an archive of questions and answers that might be useful, both to you, and to others in the future. Answerers are taking the time to help both you and future readers. Thank you for your understanding. $\endgroup$ – D.W. Jun 10 '18 at 6:59
  • $\begingroup$ I don't understand your question. The thing you describe as "the question below" is just a definition of the 4-SAT problem. You then ask about answering "that question" but you haven't told us what the question is. The only question I can imagine is "Is 4-SAT NP-complete?" but you can't be asking if the way to prove 4-SAT is NP-complete is to prove that 4-SAT is NP-complete because that's a tautology. Could you edit your question to clarify? $\endgroup$ – David Richerby Jun 10 '18 at 11:43

In order to prove that 4-SAT is NP-complete, you need to prove that it is in NP and that it is NP-hard.

Prove 4-SAT $\in$ NP

Given an instance of 4-SAT and an answer that evaluates to TRUE, it's pretty quick to verify.

4-SAT is NP-hard

Like the comments suggested, reduce 3-SAT, which is a known NP-complete problem, to 4-SAT:

Assume that you are given an instance of 3-SAT. The goal is to convert it in polynomial time into an instance of 4-SAT in such a way that the answer is preserved.

Take each clause $(x \lor y \lor z)$ and turn it into $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$, where $a$ is arbitrarily set.

  • If any $(x \lor y \lor z)$ clause is satisfied, then $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ will also be satisfied. If the instance of 3-SAT is satisfiable, then the new instance of 4-SAT is satisfiable.

  • If $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ is satisfied, then $(x \lor y \lor z)$ must also be true because $a$ is opposite of $\neg a$. If the new instance of 4-SAT is satisfiable, then the instance of 3-SAT is satisfiable.

| cite | improve this answer | |

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