Thus we can convert into O(nm), which is polynomial time. If clause length is 2, we can use 2 new variables and replace the clause by 4 new clauses. If clause length is 3, we can replace it by new clauses with one more variable x 1 Input to 3-SAT can be converted into input to EXACT-4-SAT in polynomial time.Īrgument → We can convert the input of 3-SAT problem by taking the following action for each clause length. We will apply reduction 3-SAT → EXACT-4-SAT. Thus in O(m) time we can verify the solution S which is in polynomial time.ĮXACT-4-SAT problem is as hard as the 3-SAT problem. We will try to solve the problem by proving EXACT-4-SAT problem as NP Complete in following steps:Īrgument → For a given solution S of the problem, for each clause, it will take O(1) time to verify if any one literal of the clause is satisfied, and we will check for all m clauses.
![sat problem sat problem](https://i.ytimg.com/vi/xBCEodgJIDI/maxresdefault.jpg)
The goal is to find a satisfying argument, if one exists.
![sat problem sat problem](https://kbimages1-a.akamaihd.net/c88239f1-a66e-41e9-beda-b2cc983dca04/353/569/90/False/mcgraw-hill-conquering-sat-math-fourth-edition.jpg)
In the Exact 4-SAT 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. #Notes: Proving Exact 4-SAT problem as NP Complete | 2 minutes read Problem : Exact 4-SAT Statement :