TY - JOUR

T1 - The complexity of satisfiability problems

T2 - 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005

AU - Allender, Eric

AU - Bauland, Michael

AU - Immerman, Neil

AU - Schnoor, Henning

AU - Vollmer, Heribert

N1 - Funding Information: ✩ Supported in part by DFG Grants Vo 630/5-1/2, Vo 630/6-1, and NSF Grants CCF-0514155, DMS-0652582, CCF-0830133, CCF-0832787, and CCF-0514621. * Corresponding author. Fax: +49 511 762 19606. E-mail addresses: allender@cs.rutgers.edu (E. Allender), bauland@thi.uni-hannover.de (M. Bauland), immerman@cs.umass.edu (N. Immerman), schnoor@ti.informatik.uni-kiel.de (H. Schnoor), vollmer@thi.uni-hannover.de (H. Vollmer).

PY - 2005

Y1 - 2005

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

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

UR - http://www.scopus.com/inward/record.url?scp=26844575981&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26844575981&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/11549345_8

DO - https://doi.org/10.1007/11549345_8

M3 - Conference article

VL - 3618

SP - 71

EP - 82

JO - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

JF - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

SN - 0302-9743

Y2 - 29 August 2005 through 2 September 2005

ER -