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 find a satisfying assignment, if one exists. Prove that EXACT-4SAT is NP-complete.

Short answer

The given statement has been proved.

Step-by-step solution

Statement for EXACT 4SAT

EXACT 4SAT is NP Problem.

The solution for any given problem each clause takes time to verify if there is any variable or literal of the clause is satisfied. For all clauses, it takes time to verify the solution in polynomial time.

Proving the statement

EXACT 4SAT is NP-Hard.

The 3-SAT problem’s input can be converted into the input to the EXACT-4-SAT in polynomial time.

The process to convert the input:

If the length of the clause is , then use a new clause and a new literal .

$\left(i\vee j\vee k\right)\to \left(i\vee j\vee k\vee Q_1\right)\wedge \left(i\vee j\vee k\vee Q_1\right)$ ..….(1)

Also, when the length of the clause is 2, then replace it with two new literals and four new clauses.$\left(\left(i\vee j\vee k\right)\to \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \left(i\vee j\vee Q_1\vee Q_2\right)\vee \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \left(i\vee j\vee Q_1\vee Q_2\right)\right)$…...(2)

When the length of the clause is 1, then replace it with three new and literal and new clauses.

$\left(i\right)\to \left(\begin{array}{c}\left(i\vee j\vee Q_1\vee Q_2\right)\wedge \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \\ \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \\ \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \\ \left(i\vee j\vee Q_1\vee Q_2\right)\wedge \left(i\vee j\vee Q_1\vee Q_2\right)\end{array}\right)$ ……(3)

Suppose each clause takes time to convert into a new clause and here are the total clauses they can be converted into , which is polynomial time. The output of the EXACT-4SAT problem can be converted into the output of the 3-SAT in polynomial time.

It can be done by removing new literal from each clause in polynomial time. Here are m clauses. The constant time for dropping new literals is .

Conclusion

The output for the EXACT-4SAT exists if there exists the output for the 3-SAT problem. From Equation (1), if the EXACT-4-SAT is true, means$\left(i\vee j\vee k\vee Q_1\right)\wedge \left(i\vee j\vee k\vee Q_1\right)$ is true, the reduced clause for 3-SAT $\left(i\vee j\vee k\right)$is always true, and the new literal value can be true or false.

Similarly, for clauses at Equations (2) and (3) clauses.

Thus, the output for EXACT-4-SAT exists if the output of the 3-SAT problem exists and vice-versa.

Therefore, the given statement has been proved.