The complexity of constraint satisfaction is the application of computational complexity theory to constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains.
Solving a constraint satisfaction problem on a finite domain is an NP-complete problem in general. Research has shown a number of polynomial-time subcases, mostly obtained by restricting either the allowed domains or constraints or the way constraints can be placed over the variables. Research has also established a relationship between the constraint satisfaction problem and problems in other areas such as finite model theory and databases.
Overview
Establishing whether a constraint satisfaction problem on a finite domain has solutions is an NP-complete problem in general. This is an easy consequence of a number of other NP-complete problems being expressible as constraint satisfaction problems. Such other problems include propositional satisfiability and three-colorability.
Tractability can be obtained by considering specific classes of constraint satisfaction problems. As an example, if the domain is binary and all constraints are binary, establishing satisfiability is a polynomial-time problem because this problem is equivalent to 2-SAT, which is a polynomial-time problem.
One line of research used a correspondence between constraint satisfaction problem and the problem of establishing the existence of a homomorphism between two relational structures. This correspondence has been used to link constraint satisfaction with topics traditionally related to database theory.
A considered research problem is about the existence of dichotomies among sets of restrictions. This is the question of whether a set of restrictions contains only polynomial-time restrictions and NP-complete restrictions. For relational restrictions (see below) this question was settled in the positive for Boolean domains by Schaefer's dichotomy theorem and for any finite domain by Andrei Bulanov and Dmitriy Zhuk, independently, in 2017.
Restrictions
Tractable subcases of the general constraint satisfaction problem can be obtained by placing suitable restrictions on the problems. Various kinds of restrictions have been considered.
Structural and relational restrictions :-
Tractability can be obtained by restricting the possible domains or constraints. In particular, two kinds of restrictions have been considered:
relational restrictions bound the domain and the values satisfying the constraints; structural restrictions bound the way constraints are distributed over the variables.
More precisely, a relational restriction specifies a constraint language, which is a domain and a set of relations over this domain. A constraint satisfaction problem meets this restriction if it has exactly this domain and the relation of each constraint is in the given set of relations. In other words, a relational restriction bounds the domain and the set of satisfying values of each constraint, but not how the constraints are placed over variables. This is instead done by structural restrictions. Structural restriction can be checked by looking only at the scopes of constraints (their variables), ignoring their relations (their set of satisfying values).
A constraint language is tractable if there exists a polynomial algorithm solving all problems based on the language, that is, using the domain and relations specified in the domain. An example of a tractable constraint language is that of binary domains and binary constraints. Formally, this restriction corresponds to allowing only domains of size 2 and only constraints whose relation is a binary relation. While the second fact implies that the scopes of the constraints are binary, this is not a structural restriction because it does not forbid any constraint to be placed on an arbitrary pair of variables. Incidentally, the problem becomes NP-complete if either restriction is lifted: binary constraints and ternary domains can express the graph 3-coloring problem, while ternary constraints and binary domains can express 3-SAT; these two problems are both NP-complete.
An example of a tractable class defined in terms of a structural restriction is that of binary acyclic problems. Given a constraint satisfaction problem with only binary constraints, its associated graph has a vertex for every variable and an edge for every constraint; two vertices are joined if they are in a constraint. If the graph of a problem is acyclic, the problem is called acyclic as well. The problem of satisfiability on the class of binary acyclic problem is tractable. This is a structural restriction because it does not place any limit to the domain or to the specific values that satisfy a constraints; rather, it restricts the way constraints are placed over variables.
While relational and structural restrictions are the ones mostly used to derive tractable classes of constraint satisfaction, there are some tractable classes that cannot be defined by relational restrictions only or structural restrictions only. The tractable class defined in terms of row convexity cannot be defined only in terms of the relations or only in terms of the structure, as row convexity depends both on the relations and on the order of variables (and therefore cannot be checked by looking only at each constraint in turn).
Uniform and non-uniform restrictions
The subcase obtained by restricting to a finite constraint language is called a non-uniform problem. These problems are mostly considered when expressing constraint satisfaction in terms of the homomorphism problem, as explained below. Uniform problems were also defined in the settings of homomorphism problems; a uniform problem can be defined as the union of a (possibly infinite) collection of non-uniform problems. A uniform problem made of an infinite set of non-uniform problems can be intractable even if all these non-uniform problems are tractable.
Tree-based restrictions
Some considered restrictions are based on the tractability of the constraint satisfaction problem where the constraints are all binary and form a tree over the variables. This is a structural restriction, as it can be checked by looking only at the scopes of the constraints, ignoring domains and relations.
This restriction is based on the primal graph of the problem, which is a graph whose vertices are the variables of the problem and the edges represent the presence of a constraint between two variables. Tractability can however also be obtained by placing the condition of being a tree to the primal graph of problems that are reformulations of the original one.
Equivalence conditions
Constraint satisfaction problems can be reformulated in terms of other problems, leading to equivalent conditions to tractability. The most-used reformulation is that in terms of the homomorphism problem.
Constraint satisfaction and the homomorphism problem
A link between constraint satisfaction and database theory has been provided in the form of a correspondence between the problem of constraint satisfiability and the problem of checking whether there exists a homomorphism between two relational structures. A relational structure is a mathematical representation of a relational database: it is a set of values and a set of relations over these values. Formally, , where each is a relation over , that is, a set of tuples of values of .
A relational structure is different from a constraint satisfaction problem because a constraint is a relation and a tuple of variables. Also different is the way in which they are used: for a constraint satisfaction problem, finding a satisfying assignment is the main problem; for a relation structure, the main problem is finding the answer to a query.
The constraint satisfaction problem is however related to the problem of establishing the existence of a homomorphism between two relational structures. A homomorphism is a function from the values of the first relation to the values of the second that, when applied to all values of a relation of the first structure, turns it into a subset of the corresponding relation of the second structure. Formally, is a homomorphism from to if it is a function from to such that, if then .
A direct correspondence between the constraint satisfaction problem and the homomorphism problem can be established. For a given constraint satisfaction problem, one can build a pair of relational structures, the first encoding the variables and the signatures of constraints, the second encoding the domains and the relations of the constraints. Satisfiability of the constraint satisfaction problem corresponds to finding a value for every variable such that replacing a value in a signature makes it a tuple in the relation of the constraint. This is possible exactly if this evaluation is a homomorphism between the two relational structures.
The inverse correspondence is the opposite one: given two relational structures, one encodes the values of the first in the variables of a constraint satisfaction problem, and the values of the second in the domain of the same problem. For every tuple of every relation of the first structure, there is a constraint having as values the correspondent relation of the second structure. This way, a homomorphism corresponds to mapping every scope of every constraint (every tuple of every relation of the first structure) into a tuple in the relation of the constraint (a tuple in the corresponding relation of the second structure).
A non-uniform constraint satisfaction problem is a restriction where the second structure of the homomorphism problem is fixed. In other words, every relational structure defines a non-uniform problem, that of telling whether a relation structure is homomorphic to it. A similar restriction can be placed on the first structure; for any fixed first structure, the homomorphism problem is tractable, because then there are only a polynomial number of functions from the first structure to the second. A uniform constraint satisfaction problem is an arbitrary restriction to the sets of structures for the first and second structure of the homomorphism problem.
Conjunctive query evaluation and containment
Since the homomorphism problem is equivalent to conjunctive query evaluation and conjunctive query containment, these two problems are equivalent to constraint satisfaction as well.
Join evaluation
Every constraint can be viewed as a table in a database, where the variables are interpreted as attribute names and the relation is the set of records in the table. The solutions of a constraint satisfaction problem are the result of an inner join of the tables representing its constraints; therefore, the problem of existence of solutions can be reformulated as the problem of checking whether the result of an inner join of a number of tables is nonempty.
Dichotomy theorems
Some constraint languages (or non-uniform problems) are known to correspond to problems solvable in polynomial time, and some others are known to express NP-complete problems. However, it is possible that some constraint languages are neither. It is known by Ladner's theorem that if P is not equal to NP, then there exist problems in NP that are neither polynomial-time nor NP-hard. For constraint problems with a fixed constraint language and no structural restrictions, such intermediate problems do not exist as proven by Andrei Bulatov and Dmitriy Zhuk, independently, in 2017. If no Ladner languages are expressible as constraint satisfaction problems, the set of all constraint languages can be divided exactly into those defining polynomial-time and those defining NP-complete problems; that is, this set exhibits a dichotomy.