The complexity of satisfiability problems: Refining Schaefer's theorem

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)71-82
Number of pages12
JournalLECTURE NOTES IN COMPUTER SCIENCE
Volume3618
DOIs
StatePublished - 2005
Event30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland
Duration: Aug 29 2005Sep 2 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'The complexity of satisfiability problems: Refining Schaefer's theorem'. Together they form a unique fingerprint.

Cite this