# Classifying the Complexity of Constraints Using Finite Algebras

@article{Bulatov2005ClassifyingTC, title={Classifying the Complexity of Constraints Using Finite Algebras}, author={Andrei A. Bulatov and Peter Jeavons and Andrei A. Krokhin}, journal={SIAM J. Comput.}, year={2005}, volume={34}, pages={720-742} }

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and we explore how the computational complexity of the corresponding constraint satisfaction problem is connected to the… Expand

#### Figures and Topics from this paper

#### 572 Citations

The complexity of soft constraint satisfaction

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

It is shown that many tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms and the notion of multimorphism is used to give a complete classification of complexity for the Boolean case which extends several earlier classification results for particular special cases. Expand

A Proof of CSP Dichotomy Conjecture

- Computer Science, Mathematics
- 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
- 2017

An algorithm is presented that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture. Expand

An Algebraic Characterisation of Complexity for Valued Constraint

- Mathematics, Computer Science
- CP
- 2006

It is shown that the existence of a non-trivial fractional polymorphism is a necessary condition for the tractability of a valued constraint language with rational or infinite costs over any finite domain (assuming P ≠ NP). Expand

A Proof of the CSP Dichotomy Conjecture

- Computer Science, Mathematics
- J. ACM
- 2020

This article presents an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture. Expand

Binarisation via Dualisation for Valued Constraints

- Computer Science
- AAAI
- 2015

A simple proof of the fact that to classify the computational complexity of allvalued constraint languages it suffices to classify only binary valued constraint languages is obtained. Expand

Tractability conditions for numeric CSPs

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

This work presents a general result for characterising computationally hard fragments and implies that polynomial-time solvable fragments are only to be found within two limited families of sets of relations. Expand

The Complexity of Constraint Languages

- Computer Science, Mathematics
- Handbook of Constraint Programming
- 2006

This chapter investigates how the complexity of solving constraint problems varies with the types of constraints which are allowed, and considers some alternative approaches, including a constructive approach that builds new tractable constraint languages by combining simpler languages. Expand

An Algorithm for Constraint Satisfaction Problem

- Mathematics, Computer Science
- 2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL)
- 2017

An algorithm is presented that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture. Expand

Proof Complexity Meets Algebra

- Mathematics, Computer Science
- ICALP
- 2017

It is shown that, for the most studied propositional, algebraic, and semi-algebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence and addition of constants to a core preserve the proof complexity of the CSP. Expand

Proof Complexity Meets Algebra

- Computer Science, Mathematics
- ACM Trans. Comput. Log.
- 2019

It is shown that, for the most studied propositional, algebraic, and semialgebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence, and addition of constants to a core preserve the proof complexity of the CSP. Expand

#### References

SHOWING 1-10 OF 68 REFERENCES

Constraints and universal algebra

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2004

It is shown that a constraint satisfaction problem instance can be viewed as a pair of relational structures, and the solutions to the problem are then the structure preserving mappings between these two relational structures. 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

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

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

A Complete Classification of Tractability in Allen's Algebra Relative to Subsets of Basic Relations

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

The conclusion is that no tractable subalgebra dial is not known in the literature can contain more than the three basic relations (≡), (b) and ( b⪰ ), which means that concerning algebras for specifying complete knowledge about temporal information, there is no hope of finding yet unknown classes with much expressivity. Expand

A new tractable class of constraint satisfaction problems

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2005

A new class of problems called para-primal problems, incomparable with the families identified by Feder and Vardi (1998), is introduced and it is proved that any constraint problem in this class is decidable in polynomial time. Expand

On binary constraint problems

- Computer Science, Mathematics
- JACM
- 1994

The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski, and a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time is given. Expand

Constraint Satisfaction with Countable Homogeneous Templates

- Computer Science, Mathematics
- J. Log. Comput.
- 2006

It is proved that the primitive positive definable relations over an ω-categorical structure Γ are precisely the relations that are preserved by the polymorphisms of Γ. Expand

On the Algebraic Structure of Combinatorial Problems

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

A general algebraic formulation for a wide range of combinatorial problems including Satisfiability, Graph Colorability and Graph Isomorphism is described, and it is demonstrated that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. Expand