A constraint satisfaction problem (CSP) instance has a set of
variables, each of which can take values in some
domain. It also has a set of
constraints, each of which restricts the variables in its
scope to take values limited by its constraint
relation.
The language of a constraint satisfaction problem instance is the set of different constraint relations used in its specification. For a given set of relations
over some domain we define the problem CSP (
) to the set of CSP instances whose language is contained in
.
The decision problem for a set of CSP instances is, given an instance in the class, to decide whether a solution exists. The search problem is to find such a solution. Here we address the connection between the tractability of the decision and search problems. We prove that given a constraint language
over a finite domain for which the decision problem for CSP (
) is tractable, the search problem is always tractable.
We define a surjective language over a finite domain in a standard way. We also show that we can determine in polynomial time whether an instance over a surjective language with a tractable decision problem has fewer than k solutions, and that we can generate all of its solutions with polynomial delay.
complexity - tractability - language