Menu
I am really confused why 2-CNF SAT is in P, while 3-CNF SAT is in NPC. I Read CLRS, and I understand how they prove 3-CNF SAT is in NPC. Can't I use the same reducibility from SAT to 2-CNF-SAT to prove 2-CNF-SAT is in NPC. I don't understand why 2-CNF SAT is in P.
725
Let the CNF representation of the original SAT problem is: where is satisfiable if every clause is satisfiable. Without loss of generality, let’s assume that the clause has more than literals: where is a new variable and we introduce it to make a clause with literals.
3CNF ϵ NPC: - As you know very well, you can get the 3CNF through SAT and SAT through CIRCUIT SAT that comes from NP. It shows that you can easily convert a Boolean function of SAT into 3CNF SAT and satisfied the concept of 3CNF SAT also within polynomial time through Reduction concept.
CNF : CNF is a conjunction (AND) of clauses, where every clause is a disjunction (OR). Now, 2-SAT limits the problem of SAT to only those Boolean formula which are expressed as a CNF with every clause having only 2 terms (also called 2-CNF ).
CONCEPT: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have almost 3 literals or constants. 3CNF ≤p SAT: - From the Boolean Function having three literals we can reduce the whole function into a shorter one.
why 2-CNF SAT is in P
Because there is a polynomial algorithm to solve it.
A rough sketch of a proof:
Note that any clause in 2-CNF is in the form A => B where A and B are either variables or their negation. Therefore, we can tell that this clause says when A is true, it forces B to be true. It also means that B is false forces A to be false. We have to consider that later.
Now, you can take a variable, one by one, and search if it transitively forces itself to be its negative (A => B => C => ... => non A) and vice versa (non A => ... => A). If the first is true, A has to be false; if the second, A is true. If both, the formula is unsatisfiable.
If you don't find any variable that makes the formula unsatisfiable, it is satisfiable.
Note that this "brutal" algorithm is not the actual one using strongly connected components of a graph, which I recommend you to read on. Yet, it is polynomial (the search for one variable is clearly O(N^2), since you force one variable at a time considering O(N) clauses and you consider O(N) variables, which means the algorithm is polynomial). Note that the fact that we have at most two literals in a clause is crucial. If the clauses were A => B or C or something, it wouldn't work as good.
163
The canonical reduction from CNF SAT to 3-CNF SAT is to take a clause like lit_1 OR lit_2 OR ... OR lit_n and replace it with two clauses lit_1 OR lit_2 OR ... OR lit_{floor(n/2)} OR var, lit_{floor(n/2) + 1} OR ... OR lit_n OR NOT var. If you try to crack a clause with three literals this way, you'll get another clause with three literals, so the same proof won't work for 2-CNF SAT (and probably for good reason).
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
