# Quantified Constraints: Algorithms and Complexity

@inproceedings{Brner2003QuantifiedCA, title={Quantified Constraints: Algorithms and Complexity}, author={Ferdinand B{\"o}rner and Andrei A. Bulatov and Peter Jeavons and Andrei A. Krokhin}, booktitle={CSL}, year={2003} }

The standard constraint satisfaction problem over an arbitrary finite domain can be expressed as follows: given a first-order sentence consisting of a conjunction of predicates, where all of the variables are existentially quantified, determine whether the sentence is true. This problem can be parameterized by the set of allowed constraint predicates. With each predicate, one can associate certain predicate-preserving operations, called polymorphisms, and the complexity of the parameterized… Expand

#### Topics from this paper

#### 77 Citations

Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms

- Computer Science, Mathematics
- STACS
- 2005

The quantified constraint satisfaction problem (QCSP), a more general framework in which variables can be quantified both universally and existentially, is concerned with and a complete complexity classification of maximal constraint languages is given. Expand

Relatively quantified constraint satisfaction

- Mathematics, Computer Science
- Constraints
- 2008

This paper gives a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language. Expand

The Complexity of Problems for Quantified Constraints

- Computer Science, Mathematics
- Theory of Computing Systems
- 2009

This paper investigates quantified propositional formulas in conjunctive normal form with “clauses” of arbitrary shapes, i.e., consisting of applying arbitrary relations to variables, and determines the complexity of each of these problems depending on the set of relations allowed in the input formulas. Expand

The computational complexity of quantified constraint satisfaction

- Mathematics
- 2004

The constraint satisfaction problem (CSP) is a framework for modelling search problems. An instance of the CSP consists of a set of variables and a set of constraints on the variables; the question… Expand

Recognizing frozen variables in constraint satisfaction problems

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2003

The complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the instances is studied, and it is shown that the complexity of such problems is determined by certain algebraic properties of these relations. Expand

Quantified constraint satisfaction and the polynomially generated powers property

- Mathematics
- 2011

The quantified constraint satisfaction probem (QCSP) is the problem of deciding, given a relational structure and a sentence consisting of a quantifier prefix followed by a conjunction of atomic… Expand

Quantified Constraint Satisfaction and the Polynomially Generated Powers Property

- Mathematics, Computer Science
- ICALP
- 2008

This article studies restricted versions of the quantified constraint satisfaction probem that arise from prespecifying the relations that may occur via a set of relations called a constraint language, and identifies a new combinatorial property on algebras, the polynomially generated powers(PGP) property, which it is shown is tightly connected to QCSP complexity. Expand

Constraint satisfaction with infinite domains

- Computer Science, Mathematics
- 2004

Omega-categoricity is a rather strong model-theoretic assumption on a relational structure, and it can be used to show that many techniques for constraint satisfaction with finite templates extend to omega- categorical templates. Expand

The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case

- Computer Science, Mathematics
- SIAM J. Comput.
- 2008

The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the… Expand

The complexity of constraint satisfaction games and QCSP

- Computer Science, Mathematics
- Inf. Comput.
- 2009

The quantified constraint satisfaction framework is used to study how the complexity of deciding such a game depends on the parameter set of allowed predicates, and it is shown that the complexity is determined by the surjective polymorphisms of the constraint predicates. Expand

#### References

SHOWING 1-10 OF 37 REFERENCES

Closure properties of constraints

- Mathematics, Computer Science
- JACM
- 1997

This paper investigates the subclasses that arise from restricting the possible constraint types, and shows that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. Expand

Tractable conservative constraint satisfaction problems

- Mathematics, Computer Science
- 18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings.
- 2003

This work completely characterize conservative constraint languages that give rise to CSP classes solvable in polynomial time, and obtains a complete description of those (directed) graphs H for which the List H-Coloring problem is poynomial time solvable. Expand

The complexity of maximal constraint languages

- Mathematics, Computer Science
- STOC '01
- 2001

This paper systematically study the complexity of all maximal constraint languages, that is, languages whose expressive power is just weaker than that of the language of all constraints. Expand

Equivalence and Isomorphism for Boolean Constraint Satisfaction

- Mathematics, Computer Science
- CSL
- 2002

This paper considers the problem of determining whether two given constraint satisfaction instances are equivalent and proves a dichotomy theorem by showing that for all finite sets C of constraints, this problem is either polynomial-time solvable or coNP-complete. Expand

Constraint Satisfaction Problems and Finite Algebras

- Mathematics, Computer Science
- ICALP
- 2000

It is shown that any restricted set of constraint types can be associated with a finite universal algebra and the result is a dichotomy theorem which significantly generalises Schaefer's dichotomy for the Generalised Satisfiability problem. Expand

A dichotomy theorem for constraints on a three-element set

- Mathematics, Computer Science
- The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
- 2002

Every subclass of the CSP defined by a set of allowed constraints is either tractable or NP-complete, and the criterion separating them is that conjectured by Bulatov et al. (2001). Expand

The complexity of satisfiability problems

- Computer Science, Mathematics
- STOC
- 1978

An infinite class of satisfiability problems is considered which contains these two particular problems as special cases, and it is shown that every member of this class is either polynomial-time decidable or NP-complete. Expand

A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1979

A simple constructive algorithm for the evaluation of formulas having two literals per clause, which runs in linear time on a random access machine. Expand

Characterising Tractable Constraints

- Mathematics, Computer Science
- Artif. Intell.
- 1994

A set of constraints is identified which gives rise to a class of tractable problems and given polynomial time algorithms for solving such problems, and it is proved that the class of problems generated by any set of constraint not contained in this restricted set is NP-complete. Expand

Constraint Satisfaction Problems in Non-deterministic Logarithmic Space

- Mathematics, Computer Science
- ICALP
- 2002

A general condition called bounded path duality is identified, that explains all the families of CSPs previously known to be in NL, and it is shown that closure under any operation in the pseudovariety generated by the class of dual discriminator operations is a sufficient condition for bounded pathDuality. Expand