Revision #1 Authors: Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Accepted on: 24th March 2005 00:00

Downloads: 2896

Keywords:

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, ParityL, NL, and L

are all distinct).

TR04-100 Authors: Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Publication: 24th November 2004 10:47

Downloads: 3353

Keywords:

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, ParityL, and L are all distinct). We also consider AC^0 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 AC^0 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.