How is SAT 2-CNF located in P and 3-CNF SAT located in NPC?

Question

I was really confused why SS-2-CNF is in P and SAT-3-CNF is in NPC. I read CLRS and I understand how they prove that SAT 3-CNF is in the NPC. Could I use the same reducibility from SAT to 2-CNF-SAT to prove that 2-CNF-SAT is in the NPC. I do not understand why the 2-CNF SAT is in P.

Answer 1

why 2-CNF SAT is in P

Since there is a polynomial algorithm for solving it.

Rough sketch of evidence:

Note that any sentence in 2-CNF is in the form A => B , where A and B are either variables or their negation. Therefore, we can say that this section says that when A is true, it makes B be true. It also means that B are false forces of A as false. We should consider this later.

Now you can take the variable one by one and search if it transitively forces itself to be negative (A => B => C => ... => non A) and vice versa (non A => ... => A). If the first is true, A must be false; if second, A is true. If both, the formula is unsatisfactory.

If you do not find any variable that makes the formula unsatisfactory, it is doable.

Note that this “brutal” algorithm is not actual, using the strongly related components of the graph, which I recommend you read. However, it is a polynomial (searching for one variable is obviously O (N ^ 2), since you force one variable at a time, looking at the sentences of O (N), and you count the variables O (N), which means that the algorithm is polynomial), Please note that the fact that we have no more than two literals in the article is crucial. If the sentences were A => B or C or something else, this would not work well.

Answer 2

The canonical reduction from CNF SAT to SAT-3-CNF should accept the condition as lit_1 OR lit_2 OR ... OR lit_n and replace it with two articles 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 hack a sentence with three literals this way, you will get another sentence with three literals, so the same proof will not work for SAT 2-CNF (and probably for a good reason).