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.

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.

answer: b

explanation: