Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR04-100 | 24th March 2005 00:00

RSS-Feed




Revision #1
Authors: Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
Accepted on: 24th March 2005 00:00
Downloads: 1244
Keywords: 


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, ParityL, NL, and L
are all distinct).


Paper:

TR04-100 | 23rd November 2004 00:00

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem





TR04-100
Authors: Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
Publication: 24th November 2004 10:47
Downloads: 1430
Keywords: 


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



ISSN 1433-8092 | Imprint