# Asking the Metaquestions in Constraint Tractability

@article{Chen2017AskingTM, title={Asking the Metaquestions in Constraint Tractability}, author={Hubie Chen and Beno{\^i}t Larose}, journal={ACM Trans. Comput. Theory}, year={2017}, volume={9}, pages={11:1-11:27} }

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP is as the problem of deciding, given a pair (G ℍ) of relational structures, whether or not there is a homomorphism from the first structure to the second structure. The CSP is generally NP-hard; a common way to restrict this problem is to fix the second… Expand

#### 32 Citations

Algebraic approach to promise constraint satisfaction

- Computer Science, Mathematics
- STOC
- 2019

A new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem are introduced, and it is shown that every PCSP with a fixed constraint language is equivalent to a problem of this form. Expand

A dichotomy theorem for nonuniform CSPs simplified

- Mathematics, Computer Science
- ArXiv
- 2020

The Dichotomy Conjecture for the non-uniform CSP states that for every constraint language G the problem CSP(G) is either solvable in polynomial time or is NP-complete. Expand

A Dichotomy Theorem for Nonuniform CSPs

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

The Dichotomy Conjecture for the non-uniform CSP states that for every constraint language \Gm the problem CSP is either solvable in polynomial time or is NP-complete. 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

Testing the complexity of a valued CSP language

- Mathematics, Computer Science
- ICALP
- 2019

It is proved that for any constant $\delta<1$ there is no $O(\sqrt[3]{3}^{\,\delta|D|})$ algorithm, assuming that SETH holds, and a matching lower bound under the Strong Exponential Time Hypothesis is obtained. Expand

Harnessing tractability in constraint satisfaction problems

- Mathematics
- 2016

The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the… Expand

Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs

- Mathematics, Computer Science
- J. Comput. Syst. Sci.
- 2018

The algebraic approach to the CSP is used to give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP, and it is shown that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Expand

Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory

- Computer Science
- PODS
- 2019

The characterization shows that homomorphism inadmissibility from A is constant-query testable with one-sided error if and only if the core of A is alpha-acyclic; this result generalizes existing results for testing subgraph-freeness in the general graph model. Expand

The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable

- Computer Science, Mathematics
- CP
- 2016

The main contribution of this paper is a polynomial-time algorithm that, given a constraint language \(\varGamma \) as input, decides if c-CSP(\(\var Gamma \)) is tractable. Expand

All or Nothing: Toward a Promise Problem Dichotomy for Constraint Problems

- Computer Science, Mathematics
- CP
- 2017

The results show that such instances cannot be efficiently distinguished from those with no solutions at all, and these are true for list homomorphism problems, for graphs, and for constraint languages on small domains. Expand

#### References

SHOWING 1-10 OF 57 REFERENCES

(Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability

- Mathematics, Computer Science
- CP
- 2004

This paper introduces a new approach to obtaining CSP(B) tractability results: instead of starting with a class of structures, it starts with an algorithm called look-ahead arc consistency, and gives an algebraic characterization of the structures solvable by the algorithm. Expand

Complexity of conservative constraint satisfaction problems

- Mathematics, Computer Science
- TOCL
- 2011

This work completely characterize conservative constraint languages that give rise to polynomial time solvable CSP classes, and obtains a complete description of those (directed) graphs H for which the List H-Coloring problem is solvable in polynometric time. 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

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

Meditations on Quantified Constraint Satisfaction

- Mathematics, Computer Science
- Logic and Program Semantics
- 2012

A viewpoint on the research program of understanding the complexity of the problems QCSP( B ) on finite structures is offered and a group of conjectures are proposed and discussed. 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

The complexity of satisfiability problems: Refining Schaefer's theorem

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2004

It is shown that if one considers AC^0 isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, @?L, NL, and L are all distinct). 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

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