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 = NP). We show that if one considers logspace isomorphisms, then there are exactly five isomorphism types (assuming that the complexity classes NP, P, NL, ⊕L, and L are all distinct). We also consider AC0 reductions, which provide a more detailed picture of the structure of P. We show that for constraint satisfaction problems that include the equality relation, there are exactly six isomorphism types under AC0 isomorphisms (under the same assumption). Our work leaves open the question of whether there is a finite number of isomorphism types of constraint satisfaction problems under AC 0 isomorphisms