Question

In the EXACT 4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly four literals, and such that each variable occurs at most once in each clause. The goal is to nd a satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete.

Answer 1

Step-by-step explanation:

To prove that EXACT 4-SAT is NP-complete, we prove that 4-SAT is in NP and NP-hard.

Firstly, 4-SAT is in NP, we can denote a nondeterministic polynomial-time algorithm which will take a 4-SAT instance and for input it takes a proposed truth assignment. This algorithm assess the 4-SAT instance with the truth assignment. If the 4-SAT instance assess to true, the algorithm gives the output yes; else, the output is no. This runs in polynomial time. To prove that 4-SAT is NP-hard, we reduce 3-SAT to 4-SAT as follows.

Let ? denote an instance of 3-SAT. We convert ? to a 4-SAT instance ? ? by turning each clause

(x ? y ? z) in ? to (x ? y ? z ? h) ? (x ? y ? z ? ¬h),

where h is a new variable. Clearly this is polynomial-time doable.

? If a provided clause (x ? y ? z) is contented by a truth assignment, then (x ? y ? z ? h) ? (x ? y ? z ? ¬h) is contented by the similar truth assignment with h arbitrarily set. Thus if ? is contentable, ? ? is contentable.

? Imagine ? ? is contented by a truth assignment T. Then (x ? y ? z ? h) ? (x ? y ? z ? ¬h) must be true under T. As h and ¬h assume different truth values, x?y?z must be true under T as well. Thus ? is contentable.

Answer 2

To prove that 4-SAT is NP-complete, we need to prove that 4-SAT is in NP and NP-hard both.

Case 1:

We can write a non-deterministic algorithm that will take an instance of 4-SAT and a truth assignment. Then it would verify if the instance evaluates to true.

This algorithm will take polynomial time. So 4-SAT is in NP.

Case 2:

Now let us reduce 3-SAT to 4-SAT, to prove 4-SAT in NP-hard.

Let say we have a 3-SAT instance C, where each clause is consisting of three literals.

Now to find the equivalent 4-SAT C’, replace each clause (p ∨ q ∨ r ) as (p ∨ q ∨ r ∨ s) ∧ (p ∨ q ∨ r ∨ ¬s).

• If the 3-SAT C is satisfiable by a truth assignment, then also C’ is satisfiable. As if we have the truth assignment for (p ∨ q ∨ r ), then we can find the same for (p ∨ q ∨ r ∨ s) ∧ (p ∨ q ∨ r ∨ ¬s).

• And if there is some truth assignment for C’, then that C will be satisfiable under the same assignment. Because if (p ∨ q ∨ r ∨ s) ∧ (p ∨ q ∨ r ∨ ¬s) is true then (p ∨ q ∨ r ) can be true.

Hence 4-SAT is in NP-hard.

Due to both cases, 4-SAT is NP-complete.