1
$\begingroup$

I'm looking to prove that 4-SAT, (which will be momentarily defined) is NP-complete.

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 trying to prove that 4-SAT is in NP-complete. And was trying to take inspiration from the proof that CNF-SAT is in NP-complete, but I think there should be a direct reduction to prove 4-SAT is in NP-complete.

Could I get some direction on how to construct the explicit reduction?

$\endgroup$
4
  • $\begingroup$ Why not reduce 3-SAT to 4-SAT? $\endgroup$
    – xskxzr
    Jun 9, 2018 at 4:17
  • $\begingroup$ so reducing 3-SAT to 4-SAT is to prove that 4-SAT is in NP-hard? $\endgroup$ Jun 9, 2018 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, 2018 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$ Jun 10, 2018 at 11:43

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
0

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