SAT can be verified in polynomial time, by a conversion to CNF, then verifying the SAT of the CNF in polynomial. What is wrong with this argument?

Question

we know that any expression can be converted to a CNF in linear time where the CNF result is not 'logically equivalent' to the original expression but the 'satisfiability' is invariant meaning that the CNF is satisfiable if and only if the original expression is satisfiable (this can be done for example by calculating the 'Tseitin derivative'). Given that the satisfiability of the CNF can be checked in polynomial time, then the satisfiability of the original expression can be checked in polynomial time. Therefore, the satisfiability of any expression can be checked in polynomial time. However, the SAT problem is NP-complete so this is not true. But where am I going wrong here? I assume that the explanation comes from "CNF is not logically equivalent to the original expression" but then again this is not important in checking the satisfiability (?). Thank you in advance for any help.

Answer 1

So the confusion here was that the satisfiability of DNFs (disjunctive normal forms) can be solved in polynomial time - we just check all of the disjunct and if there is a disjunct which does not include any complementary literals then it is satisfiable. We can solve the validity of CNFs (conjunctive normal forms) in polynomial time as well - because it is valid if all of the conjuncts contain complementary literals. But we the problem of validity of DNFs or satisfiability of CNFs is NP-complete. Note that any logical expression in a CNF form which complemented will be in DNF form so it is rational to think that the validity of a CNF is equivalent to the unsatisfiability of its complement (which is in turn a DNF). I got the answer a month ago but forgot to share it with you. Hope this helps anyone who encountered the same confusion as me.

Answer 2

CNF sat cannot be checked in linear time. In fact even the restricted 3-CNF SAT is NP-complete. See https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability.

Answer 3

Given that the satisfiability of the CNF can be checked in polynomial time

There is no known deterministic polynomial time algorithm for CNF formulas. The assumption you are making above is not known to be valid. This assumption does indeed imply P=NP so that not a problem in your reasoning. The problem is instead that you are 'begging the question', i.e. you have assumed the conclusion with this statement.

Answer 4

Therefore, the satisfiability of any expression can be checked in polynomial time. However, the SAT problem is NP-complete so this is not true.

You are confusing "checking" and solving. SAT is NP-complete. To be NP-complete, it must be in NP. Being in NP means that there actually must be a polynomial time method to check if a solution is correct or not. But checking is not solving. SAT cannot be solved in polynomial time (yet), hence it is NP-complete.

Imagine Sudoku, if someone let's you check his solution to a Sudoku, you can do so in polynomial time O(n^2). Hence, Sudoku is in NP. But you cannot solve it in polynomial time, so it is not in P but only in NP, hence it is NP-complete.

See also here: https://en.wikipedia.org/wiki/NP_(complexity)

NP is the set of decision problems verifiable in polynomial time by a deterministic Turing machine.