ECCC-Report TR04-100https://eccc.weizmann.ac.il/report/2004/100Comments and Revisions published for TR04-100en-usThu, 24 Mar 2005 00:00:00 +0200
Revision 1
| |
Eric Allender,
Michael Bauland,
Neil Immerman,
Henning Schnoor,
Heribert Vollmer
https://eccc.weizmann.ac.il/report/2004/100#revision1Schaefer 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).
Thu, 24 Mar 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2004/100#revision1
Paper TR04-100
| The Complexity of Satisfiability Problems: Refining Schaefer's Theorem |
Eric Allender,
Michael Bauland,
Neil Immerman,
Henning Schnoor,
Heribert Vollmer
https://eccc.weizmann.ac.il/report/2004/100Schaefer 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.
Wed, 24 Nov 2004 10:47:43 +0200https://eccc.weizmann.ac.il/report/2004/100