0
$\begingroup$

Does the following highly down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"? If not, why not?

Marek, V. Wiktor. Introduction to Mathematics of Satisfiability. Boca Raton; London; New-York: CRC Press, 2009, p. 310:

THEOREM 13.3 (Schaefer Theorem)
Let $Γ$ be a collection of Boolean tables. If one of conditions (1)–(6) below holds, then $CSP(Γ)$ is solvable in polynomial time. Otherwise, it is NP-complete.

If P = NP-complete, the aforementioned conditions have no bearing on the runtime:

If the conditions hold, then $CSP(Γ)$ is solvable in P = NP-complete time.
Otherwise, $CSP(Γ)$ is solvable in P = NP-complete time.

Which amounts to: "$CSP(Γ)$ is solvable in P = NP-complete time."


Review of Introduction to Mathematics of Satisfiability by M. I. Dekhtyar:

Chapter 13 ends with a proof of the well-known Shaefer dichotomy theorem which divides classes of Boolean constraints into solvable in polynomial time and NP-complete.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.