Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with clones:
TR04-100 | 23rd November 2004
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

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

TR05-024 | 8th February 2005
Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

ISSN 1433-8092 | Imprint