It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains.
Tractability can be obtained by considering specific classes of constraint satisfaction problems.
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.
For relational restrictions (see below) this question was settled in the positive for Boolean domains by Schaefer's dichotomy theorem[1] and for any finite domain by Andrei Bulanov[2] and Dmitriy Zhuk,[3] independently, in 2017.
Structural restriction can be checked by looking only at the scopes of constraints (their variables), ignoring their relations (their set of satisfying values).
An example of a tractable class defined in terms of a structural restriction is that of binary acyclic problems.
The subcase obtained by restricting to a finite constraint language is called a non-uniform problem.
This is a structural restriction, as it can be checked by looking only at the scopes of the constraints, ignoring domains and relations.
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.
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.
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.
For constraint problems with a fixed constraint language and no structural restrictions, such intermediate problems do not exist as proven by Andrei Bulatov[2] and Dmitriy Zhuk,[3] 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.
For a given non-uniform problem, the set of relations that can be used in constraints is fixed; as a result, one can give unique names
An instance of this non-uniform problem can be then written as a set of literals of the form
Satisfiability can sometimes be established by enforcing a form of local consistency and then checking the existence of an empty domain or constraint relation.
For some forms of local consistency, this algorithm may also require exponential time.
The following are conditions on binary constraint satisfaction problems where enforcing local consistency is tractable and allows establishing satisfiability: A condition that extends the last one holds for non-binary constraint satisfaction problems.
Namely, for all problems for which there exists an ordering that makes the primal graph having induced width bounded by a constant i, enforcing strong directional i-consistency is tractable and allows establishing satisfiability.
This is a structural restriction, as it can be checked by looking only at the scopes of the constraints, disregarding their relations and the domain.
This property of tree-like constraint satisfaction problems is exploited by decomposition methods, which convert problems into equivalent ones that only contain binary constraints arranged as a tree.
On the other hand, producing one such equivalent problem may be not be efficient because of two factors: the need to determine the combined effects of a group of constraints over a set of variables, and the need to store all tuples of values that satisfy a given group of constraints.
A necessary condition for the tractability of a constraint language based on the universal gadget has been proved.
The universal gadget is a particular constraint satisfaction problem that was initially defined for the sake of expressing new relations by projection.
If the solutions are exactly the rows of the table, every relation can be expressed by projecting on a subset of the variables.
Given a specific relation, its expressibility in the language can be checked by considering an arbitrary list of variables whose columns in the table above (the "ideal" solutions to the universal gadget) form that relation.
In the example above, the expressibility of the relation in the table on the right can be checked by looking whether the solutions of the universal gadget, when restricted to the variables
A necessary condition for tractability is the existence of a solution for a universal gadget of some order that is part of some classes of functions.
The necessary condition for tractability based on the universal gadget holds for reduced languages.