**Abstract:**
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 AC^{0} isomorphisms, then there are exactly six
isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).

Recent Publications of Neil Immerman