• E. Allender, Michael Bauland, Neil Immerman, Henning Schnoor, and Heribert Vollmer, "The Complexity of Satisfiability Problems: Refining Schaefer's Theorem", Journal of Computer and System Sciences 75 (2009), 245-254. Preliminary version appeared in MFCS '05, 71-82.

    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 AC0 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