The complexity of satisfiability problems: Refining Schaefer's theorem
Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are distinct if and only if P not equal NP). We show that if one considers AC(0) isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, circle plus L, NL, and L are all distinct). A similar classification holds for quantified constraint satisfaction problems. (C) 2008 Elsevier Inc. All rights reserved.
constraint satisfaction problem computational complexity propositional satisfiability clone theory