# Complexity Classification in Infinite-Domain Constraint Satisfaction

@article{Bodirsky2012ComplexityCI, title={Complexity Classification in Infinite-Domain Constraint Satisfaction}, author={Manuel Bodirsky}, journal={ArXiv}, year={2012}, volume={abs/1201.0856} }

A constraint satisfaction problem (CSP) is a computational problem where the input consists of a finite set of variables and a finite set of constraints, and where the task is to decide whether there exists a satisfying assignment of values to the variables. Depending on the type of constraints that we allow in the input, a CSP might be tractable, or computationally hard. In recent years, general criteria have been discovered that imply that a CSP is polynomial-time tractable, or that it is NP… Expand

#### Figures and Topics from this paper

figure 1.1 figure 1.3 figure 1.4 figure 1.6 figure 1.7 figure 1.8 figure 1.9 figure 3.1 figure 3.2 figure 4.1 figure 6.1 figure 8.1 figure 8.2 figure 9.1 figure 9.2 figure 9.3 figure 9.4 figure 9.5 figure 10.1 figure 10.10 figure 10.11 figure 10.12 figure 10.13 figure 10.14 figure 10.15 figure 10.16 figure 10.17 figure 10.18 figure 10.19 figure 10.2 figure 10.3 figure 10.4 figure 10.5 figure 10.6 figure 10.7 figure 10.8 figure 10.9 figure 11.1

#### 97 Citations

Time Complexity of Constraint Satisfaction via Universal Algebra

- Mathematics, Computer Science
- MFCS
- 2017

The worst-case time complexity of NP-complete CSPs, where one is allowed to arbitrarily restrict the values of individual variables, is studied, and it is proved that the complexity of CSP({SD}) is a lower bound for all C SPs of this particular kind. 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

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 hardness criterion for surjective constraint satisfaction

- Mathematics, Computer Science
- ArXiv
- 2014

This work presents an algebraic condition on the polymorphism clone of B and proves that it is sufficient for the hardness of the surjective CSP on a finite structure B, in the sense that this problem admits a reduction from a certain fixed-structure CSP. Expand

Tractable Set Constraints

- Computer Science, Mathematics
- IJCAI
- 2011

A large class of set CSPs is introduced that can be solved in quadratic time and has an elegant universal-algebraic characterization that is used to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem. Expand

Fine-Grained Time Complexity of Constraint Satisfaction Problems

- Computer Science
- ACM Trans. Comput. Theory
- 2021

Under the exponential-time hypothesis (ETH), the existence of subexponential algorithms for finite-domain NP-complete CSPΓ problems is ruled out and a relation SD is identified such that the time complexity of the NP- complete CSP({SD}) is a lower bound for all NP- Complete CSPs of this kind. Expand

Temporal Constraint Satisfaction Problems in Fixed-Point Logic

- Computer Science, Mathematics
- LICS
- 2020

It is proved that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q; <) and these are called temporal C SPs, which are of fundamental importance in infinite-domain constraint satisfaction. Expand

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)

- Mathematics, Computer Science
- 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- 2019

It is shown that local satisfaction and global satisfaction of nontrivial height 1 identities differ for $\omega$ -categorical structures with less than double exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures. Expand

Lower Bounds and Faster Algorithms for Equality Constraints

- Computer Science
- IJCAI
- 2020

It is proved that under the randomised exponential-time hypothesis it is not possible to find c > 1 such that a CSP over an arbitrary finite equality language is solvable in O(c) time (n is the number of variables); stronger lower bounds are possible for infinite equality languages where they rule out the existence of 2 logn) time algorithms. Expand

An initial study of time complexity in infinite-domain constraint satisfaction

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

This work analyzes backtracking algorithms and determines upper bounds on their time complexity, and proves non-trivial lower bounds applicable to many interesting CSPs, under the assumption that certain complexity-theoretic assumptions hold. Expand

#### References

SHOWING 1-10 OF 197 REFERENCES

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

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 dichotomy theorem for constraint satisfaction problems on a 3-element set

- Mathematics, Computer Science
- JACM
- 2006

Every subproblem of the CSP is either tractable or NP-complete, and the criterion separating them is that conjectured in Bulatov et al. Expand

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

Tractable Constraints on Ordered Domains

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

A restricted set of contraints is identified which gives rise to a class of tractable problems which generalizes the notion of a Horn formula in propositional logic to larger domain sizes, and it is proved that the class of problems generated by any larger set of constraints is NP-complete. 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

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

- Computer Science
- LICS
- 2010

It is proved that every CSP can be formulated with a template A such that a relation is primitive positive definable in A if and only if it is first-order definable on A and preserved by the infinitary polymorphisms of A. Expand

Universal Algebra and Hardness Results for Constraint Satisfaction Problems

- Computer Science, Mathematics
- ICALP
- 2007

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

Constraint Satisfaction, Logic and Forbidden Patterns

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

A new class of combinatorial problems is introduced, the class of forbidden patterns problems FPP, and MMSNP is characterized as the finite unions of problems from FPP because it is able to decide whether the problem is in CSP or not. Expand