# The Complexity of Constraint Languages

@inproceedings{Cohen2006TheCO, title={The Complexity of Constraint Languages}, author={David A. Cohen and Peter Jeavons}, booktitle={Handbook of Constraint Programming}, year={2006} }

Publisher Summary This chapter discusses one of the most fundamental challenges in constraint programming: to understand the computational complexity of problems involving constraints. One way in which this occurs is that there is some special structure in the way that the constraints overlap and intersect each other. The natural theory for discussing the structure of such interaction between constraints is the mathematical theory of hypergraphs. Another way in which constraint problems are… Expand

#### Figures, Tables, and Topics from this paper

#### 106 Citations

Algorithms and Hardness Results for Some Valued CSPs

- Mathematics
- 2009

In the Constraint Satisfaction Problem (CSP) one is supposed to find an assignment to a set of variables so that a set of given constraints are satisfied. Many problems, both practical and… Expand

Domain permutation reduction for constraint satisfaction problems

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

A new way of identifying tractable subproblems of the Constraint Satisfaction Problem is defined and the notion of a ''lifted constraint instance'' which is a powerful tool to study this question is described. Expand

Transformations of representation in constraint satisfaction

- Mathematics, Computer Science
- Constraints
- 2015

It is shown how the microstructure can be used to define CSPs that are tractable because their clause structures fall within classes of graphs for which an independent set of specified size can be found efficiently. Expand

The Constraint Satisfaction Problem: Complexity and Approximability

- Computer Science, Mathematics
- The Constraint Satisfaction Problem
- 2017

This report documents the material presented during the course of the Dagstuhl Seminar 18231 “The Constraint Satisfaction Problem: Complexity and Approximability”, aimed at bringing together researchers using all the different techniques in the study of the CSP to share their insights obtained. Expand

Complexité des homomorphismes de graphes avec listes

- Mathematics
- 2012

Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these… Expand

The tractability of CSP classes defined by forbidden patterns

- Computer Science, Mathematics
- J. Artif. Intell. Res.
- 2012

This work describes the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns and shows that this framework generalises certain known hybrid tractable classes. Expand

The Complexity of General-Valued CSPs

- Computer Science, Mathematics
- 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- 2015

It is proved that if a constraint language satisfies this algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language, then the VCSP is tractable. Expand

On the power of structural decompositions of graph-based representations of constraint problems

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

Various long-standing questions about primal, dual and incidence graph encodings are answered and a clear picture of the tractable fragments of CSP that can be specified with respect to each of these decomposition approaches, when they are applied to binary representations of non-binary CSP instances are provided. Expand

Structural decompositions for problems with global constraints

- Mathematics, Computer Science
- Constraints
- 2015

It is shown that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Expand

Universal algebra and hardness results for constraint satisfaction problems

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

Algebraic conditions on constraint languages @C are presented that ensure the hardness of the constraint satisfaction problem CSP(@C) for complexity classes L, NL, P, NP and Mod"pL and it is shown that if CSP(*C) is not first-order definable then it is L-hard. Expand

#### References

SHOWING 1-10 OF 114 REFERENCES

Classifying the Complexity of Constraints Using Finite Algebras

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

It is shown that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra is explored. 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

Implementing a Test for Tractability

- Mathematics, Computer Science
- Constraints
- 2004

An automated analysis includes the derivation of more than 450 000 new NP-completeness results, and precisely identifies the small set of individual relations which cannot be classified as either tractable or NP-complete using the algebraic conditions presented in previous papers. Expand

How to Determine the Expressive Power of Constraints

- Mathematics, Computer Science
- Constraints
- 2004

It is shown that indicator problems provide a simple method to test for tractability and the expressive power of a given set of constraint types is determined by certain algebraic properties of the underlying relations. 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

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

An Algebraic Approach to Multi-sorted Constraints

- Computer Science
- CP
- 2003

A new algebraic framework is described which allows us to deal more precisely with problems where different variables may have different domains, and is able to identify new tractable classes of constraints by combining algorithms devised for the simplified, single domain, problem. Expand

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

Towards a dichotomy theorem for the counting constraint satisfaction problem

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

It is proved that if a subclass of the #CSP is tractable, then constraints allowed by the class satisfy some very restrictive condition: it has to have a Mal'tsev polymorphism, that is a ternary operation m(x, y, z) such that x = x. Expand

Constructing Constraints

- Computer Science
- CP
- 1998

It is shown that for languages over a finite domain the concept of an 'indicator problem' gives a universal construction for any constraint within the expressive power of a language. Expand