Closure properties of constraints.
Many combinatorial search problems can be expressed as constraint satisfaction problems and this class of problems is known to be NP-complete in general. In this paper, we investigate the subclasses that arise from restricting the possible constraint types. We first show that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. We then investigate all the different possible forms of this algebraic closure property, and establish which of these are sufficient to ensure tractability. As examples, we show that all known classes of tractable constraints over finite domains can be characterized by such an algebraic closure property. Finally, we describe a simple computational procedure that can be used to determine the closure properties of a given set of constraints. This procedure involves solving a particular constraint satisfaction problem, which we call an indicator problem.
Introduction
Solving a constraint satisfaction problem is known to be NP-complete [20]. However,
many of the problems which arise in practice have special properties which allow them to
be solved efficiently. The question of identifying restrictions to the general problem which
are sufficient to ensure tractability is important from both a practical and a theoretical
viewpoint, and has been extensively studied.
Such restrictions may either involve the structure of the constraints, in other words,
which variables may be constrained by which other variables, or they may involve the
Earlier versions of parts of this paper were presented at the International Conferences on Constraint
Programming in 1995 and 1996. (See references [14] and [15].)
nature of the constraints, in other words, which combinations of values are allowed for
variables which are mutually constrained. Examples of the first approach can be found
in [7, 9, 12, 22, 23] and examples of the second approach can be found in [4, 14, 16, 8,
17, 22, 28, 29].
In this paper we take the second approach, and investigate those classes of constraints
which only give rise to tractable problems whatever way they are combined. A number
of distinct classes of constraints with this property have previously been identified and
shown to be maximal [4, 14, 16].
In this paper we establish that any class of constraints which does not give rise
to NP-complete problems must satisfy a certain algebraic closure condition, and hence
this algebraic property is a necessary condition for a class of constraints to be tractable
(assuming that P is not equal to NP). We also show that many forms of this algebraic
closure property are sufficient to ensure tractability.
As an example of the wide applicability of these results, we show that all known
examples of tractable constraint classes over finite domains can be characterized by an
algebraic condition of this kind, even though some of them were originally defined in very
different ways.
Finally, we describe a simple computational procedure to determine the algebraic
closure properties of a given set of constraints. The test involves calculating the solutions
to a fixed constraint satisfaction problem involving constraints from the given set.
The work described in this paper represents a generalization of earlier results concerning
tractable subproblems of the Generalized Satisfiability problem. Schaefer
[26] identified all possible tractable classes of constraints for this problem, which
corresponds to the special case of the constraint satisfaction problem in which the variables
are Boolean. The tractable classes described in [26] are special cases of the tractable
classes of general constraints described below, and they are given as examples.
A number of tractable constraint classes have also been identified by Feder and Vardi
in [8]. They define a notion of 'width' for constraint satisfaction problems in terms of the
logic programming language Datalog, and show that problems with bounded width are
solvable in polynomial time. It is stated in [8] that the problem of determining whether
a fixed collection of constraints gives rise to problems of bounded width is not known
to be decidable. However, it is shown that a more restricted property, called 'bounded
strict width', is decidable, and in fact corresponds to an algebraic closure property of the
form described here. Other tractable constraint classes are also shown to be characterised
by a closure property of this type. This paper builds on the work of Feder and Vardi
by examining the general question of the link between algebraic closure properties and
tractability of constraints, and establishing necessary and sufficient conditions for these
closure properties.
A different approach to identifying tractable constraints is taken in [28], where it
is shown that a property of constraints, referred to as 'row-convexity', together with
path-consistency, is sufficient to ensure tractability in binary constraint satisfaction prob-
lems. It should be noted, however, that because of the additional requirement for path-
consistency, row-convex constraints do not constitute a tractable class in the sense defined
in this paper. In fact, the class of problems which contain only row-convex constraints is
NP-complete [4].
The paper is organised as follows. In Section 2 we give the basic definitions, and in
Section 3 we define what we mean by an algebraic closure property for a set of relations
and examine the possible forms of such a closure property. In Section 4 we identify which
of these forms are necessary conditions for tractability, and in Section 5 we identify which
of them are sufficient for tractability. In Section 6 we describe a computational method
to determine the closure properties satisfied by a set of relations. Finally, we summarise
the results presented and draw some conclusions.
2.1 The constraint satisfaction problem
Notation 2.1 For any set D, and any natural number n, we denote the set of all n-tuples
of elements of D by D n . For any tuple t 2 D n , and any i in the range 1 to n,
we denote the value in the ith coordinate position of t by t[i]. The tuple t may then be
written in the form ht[1];
A subset of D n is called an n-ary relation over D.
We now define the (finite) constraint satisfaction problem which has been widely
studied in the Artificial Intelligence community [18, 20, 22].
Definition 2.2 An instance of a constraint satisfaction problem consists of
ffl a finite set of variables,
ffl a finite domain of values, D;
ffl a set of constraints fC g.
Each constraint C i is a pair (S i list of variables of length m i ,
called the constraint scope, and R i is an m i -ary relation over D, called the constraint
relation. (The tuples of R i indicate the allowed combinations of simultaneous
values for the variables in S i .)
The length of the tuples in the constraint relation of a given constraint will be called the
arity of that constraint. In particular, unary constraints specify the allowed values for a
single variable, and binary constraints specify the allowed combinations of values for a
pair of variables. A solution to a constraint satisfaction problem is a function from the
variables to the domain such that the image of each constraint scope is an element of the
corresponding constraint relation.
Deciding whether or not a given problem instance has a solution is NP-complete in
general [20] even when the constraints are restricted to binary constraints. In this paper
we shall consider how restricting the allowed constraint relations to some fixed subset of
all the possible relations affects the complexity of this decision problem. We therefore
make the following definition.
Definition 2.3 For any set of relations, \Gamma, CSP(\Gamma) is defined to be the decision problem
with
INSTANCE: An instance, P , of a constraint satisfaction problem, in which all constraint
relations are elements of \Gamma.
Does P have a solution?
If there exists an algorithm which solves every problem instance in CSP(\Gamma) in polynomial
time, then we shall say that CSP(\Gamma) is a tractable problem, and \Gamma is a tractable set of
relations.
Example 2.4 The binary disequality relation over a set D, denoted 6= D , is defined as
Note that CSP(f6=D g) corresponds precisely to the Graph jDj-Colorability problem
[11]. This problem is tractable when jDj - 2 and NP-complete when jDj - 3.Example 2.5 Consider the ternary relation ffi over the set which is defined
by
The problem CSP(fffig) corresponds precisely to the Not-All-Equal Satisfiability
problem [11], which is NP-complete [26]. 2
Example 2.6 We now describe three relations which will be used as examples of constraint
relations throughout the paper.
Each of these relations is a set of tuples of elements from the domain
as defined below:
The problem CSP(fR 1 consists of all constraint satisfaction problem instances
in which the constraint relations are all chosen from the set fR 1 g.
The complexity of CSP(\Gamma) for arbitrary subsets \Gamma of fR 1 will be determined
using the techniques developed later in this paper (see Example 6.6). 2
2.2 Operations on relations
In Section 4 we shall examine conditions on a set of relations \Gamma which allow known NP-complete
problems to be reduced to CSP(\Gamma). The reductions will be described using
standard operations from relational algebra [1], which are described in this section.
Definition 2.7 We define the following operations on relations.
ffl Let R be an n-ary relation over a domain D and let S be an m-ary relation over
D. The Cartesian product R \Theta S is defined to be the (n +m)-ary relation
R \Theta
ffl Let R be an n-ary relation over a domain D. Let 1 - n. The equality
selection oe i=j (R) is defined to be the n-ary relation
oe
ffl Let R be an n-ary relation over a domain D. Let i be a subsequence of
n. The projection -
(R) is defined to be the m-ary relation
It is well-known that the combined effect of two constraints in a constraint satisfaction
problem can be obtained by performing a relational join operation [1] on the two constraints
[12]. The next result is a simple consequence of the definition of the relational
join operation.
Lemma 2.8 Any relational join of relations R and S can be calculated by performing a
sequence of Cartesian product, equality selection, and projection operations on R and S.
In view of this result, it will be convenient to use the following notation.
Notation 2.9 The set of all relations which can be obtained from a given set of relations,
\Gamma, using some sequence of Cartesian product, equality selection, and projection operations
will be denoted
Note contains exactly those relations which can be obtained as 'derived' relations
in a constraint satisfaction problem instance with constraint relations chosen from \Gamma [2].
3 Closure operations
We shall establish below that significant information about CSP(\Gamma) can be determined
from algebraic properties of the set of relations \Gamma. In order to describe these algebraic
properties we need to consider arbitrary operations on D, in other words, arbitrary
functions from D k to D, for arbitrary values of k.
For the results below we shall be particularly interested in certain special kinds of
operations. We therefore make the following definition:
Definition 3.1
Let\Omega be a k-ary operation from D k to D.
If\Omega is such that, for all d 2
then\Omega is said to be idempotent.
ffl If there exists an index i 2 kg such that for all hd 1
is a non-constant unary operation on D,
then\Omega is called essentially unary. (Note that f is required to be non-constant, so
constant operations are not essentially unary.)
If f is the identity operation,
then\Omega is called a projection.
ffl If k - 3 and there exists an index i 2 kg such that for all d 1
with
but\Omega is not a projection,
then\Omega is called a semiprojection [25, 27].
then\Omega is called a majority operation.
are binary operations on D such that hD; +; \Gammai is an Abelian group [27],
is called an affine operation.
Any operation on D can be extended to an operation on tuples over D by applying the
operation in each coordinate position separately (i.e., pointwise). Hence, any operation
defined on the domain of a relation can be used to define an operation on the tuples in
that relation, as follows:
Definition 3.2
D be a k-ary operation on D and let R be an n-ary
relation over D.
For any collection of k tuples, t necessarily all distinct) the
defined as follows:
Finally, we
define\Omega (R) to be the n-ary relation
Using this definition, we now define the following closure property of relations.
Definition 3.3
Let\Omega be a k-ary operation on D, and let R be an n-ary relation over
D. The relation R is closed
under\Omega if\Omega (R) ' R.
Example 3.4 Let 4 be the ternary majority operation defined as follows:
x otherwise.
The relation R 2 defined in Example 2.6 is closed under 4, since applying the 4
operation to any 3 elements of R 2 yields an element of R 2 . For example,
The relation R 3 defined in Example 2.6 is not closed under 4, since applying the 4
operation to the last 3 elements of R 3 yields a tuple which is not an element of R 3
For any set of relations \Gamma, and any
operation\Omega , if every R 2 \Gamma is closed
under\Omega , then we
shall say that \Gamma is closed
under\Omega . The next lemma indicates that the property of being
closed under some operation is preserved by all possible projection, equality selection,
and product operations on relations, as defined in Section 2.2.
Lemma 3.5 For any set of relations \Gamma, and any
closed
under\Omega ,
closed
under\Omega .
Proof: Follows immediately from the definitions.
Notation 3.6 For any set of relations \Gamma with domain D, the set of all operations on D
under which \Gamma is closed will be denoted \Gamma   .
The set of closure operations, \Gamma   , can be used to obtain a great deal of information about
the problem CSP(\Gamma), as we shall demonstrate in the next two Sections.
As a first example of this, we shall show that the operations in \Gamma   can be used obtain
a reduction from one problem to another.
Proposition 3.7 For any set of finite relations \Gamma, and
there is a polynomial-time
reduction from CSP(\Gamma) to
CSP(\Omega (\Gamma)),
\Gammag.
Proof: Let P be any problem instance in CSP(\Gamma) and consider the instance P 0 obtained
by replacing each constraint relation R i of P by the
relation\Omega (R i ). It is clear that P 0
can be obtained from P in polynomial-time. It follows from Definition 3.3 that P 0 has a
solution if and only if P has a solution.
It follows from this result that if \Gamma   contains a non-injective unary operation, then
CSP(\Gamma) can be reduced to a problem over a smaller domain. One way to view this is
that the presence of a non-injective unary operation in \Gamma   indicates that constraints with
relations chosen from \Gamma allow a form of global 'substitutability', similar to the notion
defined by Freuder in [10].
does not contain any non-injective unary operations, then we shall say that \Gamma is
reduced. The next theorem uses a general result from universal algebra [25, 27] to show
that the possible choices for \Gamma   are quite limited.
Theorem 3.8 For any reduced set of relations \Gamma, on a finite set, either
contains essentially unary operations only, or
2. \Gamma   contains an operation which is
(a) a constant operation; or
(b) a majority operation; or
(c) an idempotent binary operation (which is not a projection); or
(d) an affine operation; or
(e) a semiprojection.
Proof: The set of operations \Gamma   contains all projections and is closed under composition,
hence it constitutes a 'clone' [3, 27]. It was shown in [25] that any non-trivial clone on a
finite set must contain a minimal clone, and that any minimal clone contains either
1. a non-identity unary operation; or
2. a constant operation; or
3. a majority operation; or
4. an idempotent binary operation (which is not a projection); or
5. an affine operation; or
6. a semiprojection.
Furthermore, if \Gamma is reduced, and \Gamma   contains any operations which are not essentially
unary, then it is straightforward to show, by considering such an operation of the smallest
possible arity, that \Gamma   contains an operation in one of the last five of these classes [27, 19].
In the next two Sections we shall examine each of these possibilities in turn, in order to
establish what can be said about the complexity of CSP(\Gamma) in the various cases.
4 A necessary condition for tractability
In this Section we will show that any set of relations which is only closed under essentially
unary operations will give rise to a class of constraint satisfaction problems which is NP-complete

Theorem 4.1 For any finite set of relations, \Gamma, over a finite set D, if \Gamma   contains
essentially unary operations only then CSP(\Gamma) is NP-complete.
Proof: When jDj - 2, then we may assume without loss of generality that D ' f0; 1g,
where 0 corresponds to the Boolean value false and 1 corresponds to the Boolean value
true. It follows that the problem CSP(\Gamma) corresponds to the Generalised Satisfiability
problem over the set of Boolean relations \Gamma, as defined in [26] (see also [11]).
It was established in [26] that this problem is NP-complete unless one of the following
conditions holds:
1. Every relation in \Gamma contains the tuple (0;
2. Every relation in \Gamma contains the tuple (1;
3. Every relation in \Gamma is definable by a formula in conjunctive normal form in which
each conjunct has at most one negated variable;
4. Every relation in \Gamma is definable by a formula in conjunctive normal form in which
each conjunct has at most one unnegated variable;
5. Every relation in \Gamma is definable by a formula in conjunctive normal form in which
each conjunct contains at most 2 literals;
Every relation in \Gamma is the set of solutions of a system of linear equations over the
finite field GF(2).
It is straightforward to show that in each of these cases \Gamma is closed under some operation
which is not essentially unary (see [13] for details). Hence the result holds when 2.
For larger values of jDj we proceed by induction. Assume that jDj - 3 and the
result holds for all smaller values of jDj. Let
M be an m by n matrix over D in which the columns consist of all possible m-tuples
over D (in some order). Let R 0 be the relation consisting of all the tuples occuring as
rows of M . The only condition we place on the choice of order for the columns of M is
that - 1;2 (R 0 is the binary disequality relation over D, as defined in
Example 2.4.
We now construct a relation -
R 0 which is the 'closest approximation' to R 0 that we can
obtain from the relations in \Gamma and the domain D using the Cartesian product, equality
selection and projection operations:
Since this is a finite intersection, and intersection is a special case of join, we have from
Lemma 2.8 that -
In other words, the relation -
R 0 can be obtained as a
derived constraint relation in some problem belonging to CSP(\Gamma).
There are now two cases to consider:
1. If there exists some tuple t
then we will construct, using
an appropriate operation under which \Gamma is closed.
Define the
is the
unique column of M corresponding to the m-tuple hd We will show
that \Gamma is closed
under\Omega .
Choose any R 2 \Gamma, and let p be the arity of R. We are required to show that R is
closed
under\Omega . Consider any sequence t of tuples of R (not necessarily
be the m-tuple ht 1 [i]; t
each pair of indices, i; j, such that c apply the equality selection oe i=j to R,
to obtain a new relation R 0 .
Now choose a maximal set of indices, I g, such that the corresponding
c i are all distinct, and construct the relation R Finally,
permute the coordinate positions of R 00 (by a sequence of Cartesian product, equality
selection, and projection operations), such that R 00 ' R 0 (this is always possible,
by the construction of R 0 and R 00 ). Since R 00 we know that t 0 is a
tuple of R 00 , by the definition of -
R 0 . Hence the appropriate projection of t 0 is an
element of R, and R is closed
under\Omega .
If\Omega is not essentially unary, then we have the result. Otherwise, let f : D ! D be
the corresponding unary operation, and set
By the choice of t 0 , f cannot be injective, so jf(D)j ! jDj. By the inductive
hypothesis, we know that either CSP(f (\Gamma)) is NP-complete (in which case CSP(\Gamma)
must also be NP-complete) or else f (\Gamma) is closed under some operation \Phi which is
not essentially unary (in which case \Gamma is closed under the operation \Phif , which is
also not essentially unary). Hence, the result follows by induction in this case.
2. Alternatively, if -
R 0 contains no tuple t such that
. But this implies that CSP(f6=D g) is reducible to CSP(\Gamma), since
every occurence of the constraint relation 6= D can be replaced with an equivalent
collection of constraints with relations chosen from \Gamma. However, it was pointed out
in Example 2.4 that CSP(f6=D g) corresponds to the Graph jDj-Colorability
problem [11], which is NP-complete when jDj - 3. Hence, this implies that CSP(\Gamma)
is NP-complete, and the result holds in this case also.
Combining Theorem 4.1 with Theorem 3.8 gives the following necessary condition for
tractability.
Corollary 4.2 Assuming that P is not equal to NP, any tractable set of reduced relations
must be closed under either a constant operation, or a majority operation, or an
idempotent binary operation, or an affine operation, or a semiprojection.
Note that the arity of a semiprojection is at most jDj, so for any finite set D there are
only finitely many operations matching the given criteria, which means that there is a
finite procedure to check whether this necessary condition is satisfied (see Corollary 6.5,
below).
5 Sufficient conditions for tractability
We have shown in the previous section that when \Gamma is a tractable set of relations, then \Gamma
must contain an operation from a limited range of types. We now consider each of these
possibilities in turn, to determine whether or not they are sufficient to ensure tractability.
5.1 Constant operations
Closure under a constant operation is easily shown to be a sufficient condition for
tractability.
Proposition 5.1 For any set of relations \Gamma, if \Gamma is closed under a constant operation,
then CSP(\Gamma) is solvable in polynomial time.
Proof: If every relation in \Gamma is closed under some constant
operation\Omega , with constant
value d, then every non-empty relation in \Gamma must contain the tuple hd;
in this case, the decision problem for any constraint satisfaction problem instance P in
CSP(\Gamma) is clearly trivial to solve, since P either contains an empty constraint, in which
case it does not have a solution, or else P allows the solution in which every variable is
assigned the value d.
The class of sets of relations closed under some constant operation is a rather trivial
tractable class. It is referred to in [14] as Class 0.
Example 5.2 Let ? denote the unary operation on the domain which
returns the constant value 1. The constraint R 3 defined in Example 2.6 is closed under
?, since applying the ? operation to any element of R 3 yields the tuple h1; 1i, which is
an element of R 3 . The constraint R 2 defined in Example 2.6 is not closed under ?, since
applying the ? operation to any element of R 2 yields the tuple h1; 1; 1i, which is not an
element of R 2 . In fact, R 2 is clearly not closed under any constant operation. 2
Example 5.3 When there are only two possible constant operations
on D.
The first two tractable subproblems of the Generalised Satisfiability problem
identified by Schaefer in [26] correspond to the tractable classes of relations characterised
by closure under these two constant operations. 2
5.2 Majority operations
We will now show that closure under a majority operation is a sufficient condition for
tractability.
We first establish that when a relation R is closed under a majority operation, any
constraint involving R can be decomposed into binary constraints.
Proposition 5.4 Let R be a relation of arity n which is closed under a majority opera-
tion, and let C be any constraint constraining the variables in S with relation
R.
For any problem P with constraint C, the problem P 0 which is obtained by replacing
C by the set of constraints
ng
has exactly the same solutions as P.
Proof: It is clear that any solution to P is a solution to P 0 , since P 0 is obtained by
taking binary projections of a constraint from P.
Now let oe be any solution to We shall
prove, by induction on n, that t 2 R, thereby establishing that oe is a solution to P.
For 3 the result holds trivially, so assume that n - 3, and that the result holds for
all smaller values. Let I = ng be the set of indices of positions in S and choose
Proposition 3.5 and the inductive hypothesis, applied to - Infi j g (R), there
is some t j 2 R which agrees with t at all positions except i j , for 3. Since R is
closed under a majority operation, applying this operation to t
Example 5.5 Recall the relation R 2 defined in Example 2.6.
It was shown in Example 3.4 that R 2 is closed under the operation 4. Since this
operation is a majority operation, we know by Proposition 5.4 that any constraint with
relation R 2 can be decomposed into a collection of binary constraints with the following
relations:
It is, of course, not always the case that a constraint can be replaced by a collection of
binary constraints on the same variables. In many cases the binary projections of the
constraint relation allow extra solutions, as the following example demonstrates.
Example 5.6 Recall the relation ffi on domain defined in Example 2.5. The
binary projections of ffi are as follows:
The join of these binary projections contains the tuples h0; 0; 0i and h1; 1; 1i, which are
not elements of ffi. It clearly follows that ffi cannot be replaced by any set of binary
constraints on the same variables. 2
Theorem 5.7 Let \Gamma be any set of relations over a finite domain, D.
If \Gamma is closed under a majority operation, then CSP(\Gamma) is solvable in polynomial time.
Proof: For any problem instance P in CSP(\Gamma) we can impose strong (jDj
consistency [5] in polynomial time to obtain a new instance P 0 with the same solutions.
All of the constraints in P 0 are elements so they are closed under a majority
operation, by Proposition 3.5. Hence, all of the constraints of P 0 are decomposable into
binary constraints by Proposition 5.4. Hence, by Corollary 3.2 of [5], P 0 is solvable in
polynomial time.
Example 5.8 When there is only one possible majority operation
on D, (which is equal to the 4 operation defined in Example 3.4). It is easily shown
that all possible binary Boolean relations are closed under 4. Hence, it follows from
Proposition 5.4 that the Boolean relations of arbitrary arity which are closed under
this majority operation are precisely the relations which are definable by a formula in
conjunctive normal form in which each conjunct contains at most 2 literals. Hence, if a
set of Boolean relations \Gamma is closed under a majority operation, then CSP(\Gamma) is equivalent
to the 2-Satisfiability problem (2-Sat) [24], which is well-known to be a tractable
subproblem of the Satisfiability problem [26]. 2
Recall the class of tractable constraints identified independently in [4] and [17], and
referred to as 0/1/all constraints or implicational constraints. (This class of tractable
constraints is referred to as Class I in [14].) It was shown in [14] that these constraints
are in fact precisely the relations closed under the majority operation 4 defined in Example
3.4. This result is rather unexpected, in view of the fact that 0/1/all constraints
were originally defined purely in terms of their syntactic structure [4].
However, we remark here that the class of tractable sets of relations defined by closure
under some majority operation is a true generalization of the class containing all sets of
0/1/all constraints. In other words, there exist tractable sets of relations which are closed
under some majority operation but are not closed under the 4 operation, as the following
example demonstrates.
Example 5.9 Let - be the ternary majority operation on which returns
the median value of its three arguments (in the standard ordering of D).
Recall the relation R 3 defined in Example 2.6. It is easy to show that R 3 is closed
under -, since applying the - operation to any 3 elements of R 3 yields an element of R 3 .
For example,
Hence, by Theorem 5.7, CSP(fR 3 g) is tractable.
However, it was shown in Example 3.4 that R 3 is not closed under 4, and hence R 3
is not a 0/1/all constraint. 2
5.3 Binary operations
We first show that closure under an arbitrary idempotent binary operation is not in
general sufficient to ensure tractability.
Lemma 5.10 There exists a set of relations \Gamma closed under an idempotent binary operation
(which is not a projection) such that CSP(\Gamma) is NP-complete.
Proof: Consider the binary operation 2 on the set which is defined by
the following table:
This operation is idempotent but it is not a projection (in fact, it is an example of a form
of binary operation known as a 'rectangular band' [21].)
Now consider the functions which return the first
and second bit in the binary expression for the numerical value of each element of D.
Using these functions, we define ternary relations R 1 and R 2 over D, as follows:
Finally, we define R
It is easily shown that R is closed under 2, since applying the operation 2 to any 2
elements of R yields an element of R.
However, it can also be shown that the Not-All-Equal Satisfiability problem
[26], which is known to be NP-complete, is reducible in polynomial time to CSP(fRg).
Hence, CSP(fRg) is NP-complete, and the result follows.
We now describe some additional conditions which may be imposed on binary operations.
It will be shown below that closure under any binary operation satisfying these additional
conditions is a sufficient condition for tractability.
D be an idempotent binary operation on the set D such
that, for all d
Then u is said to be an ACI operation.
We will make use of the following result about ACI operations, which is well-known from
elementary algebra [3, 21].
Lemma 5.12 Let u be an ACI operation on the set D. The binary relation R on D
defined by
is a partial order on D in which any two elements have a least upper bound given
by u(d
It follows from Lemma 5.12 that any (finite) non-empty set D 0 ' D which is u-closed
contains a least upper bound with respect to the partial order R. This upper bound will
be denoted u(D 0 ).
Using Lemma 5.12, we now show that relations which are closed under some arbitrary
ACI operation form a tractable class.
Theorem 5.13 For any set of relations \Gamma over a finite domain D, if \Gamma is closed under
some ACI operation, then CSP(\Gamma) is solvable in polynomial time.
be a set of relations closed under the ACI operation u, and let P be any
problem instance in CSP(\Gamma). First enforce pairwise consistency to obtain a new instance
with the same set of solutions which is pairwise consistent. Such a P 0 can be obtained
by forming the join of every pair of constraints in P, replacing these constraints with the
(possibly smaller) constraints obtained by projecting down to the original scopes, and
then repeating this process until there are no further changes in the constraints. The
time complexity of this procedure is polynomial in the size of P, and the resulting P 0 is
a member of CSP(\Gamma all the constraint relations in P 0 are closed under u, by
Proposition 3.5.
Now let D(v) denote the set of values allowed for variable v by the constraints of P 0 .
Since D(v) equals the projection of some u-closed constraint onto v, it must be u-closed,
by Proposition 3.5. There are two cases to consider:
1. If any of the sets D(v) is empty then P 0 has no solutions, so the decision problem
is trivial.
2. On the other hand, if all of these sets are non-empty, then we claim that assigning
the value u(D(v)) to each variable v gives a solution to P 0 , so the decision problem
is again trivial. To establish this claim, consider any constraint
with relation R of arity n, and scope S. For each there must be
some tuple t i 2 R such that t i by the definition of D(S[i]). Now
consider the tuple We know that t 2 R, since R
is closed under u. Furthermore, for each i, because u(D(S[i])) is
an upper bound of D(S[i]), so
for all d 2 D(S[i]). Hence the constraint C allows the assignment of u(D(v)) to
each variable v in S. Since C was arbitrary, we have shown that this assignment is
a solution to P 0 , and hence a solution to P.
Example 5.14 When there are only two idempotent binary operations
on D (which are not projections), corresponding to the logical AND operation
and the logical OR operation. These two operations are both ACI operations, and they
correspond to the two possible orderings of D.
It is well-known [6, 16, 24] that a Boolean relation is closed under AND if and only if it
can be defined by a Horn sentence (that is, a conjunction of clauses each of which contains
at most one unnegated literal). Hence, if a set of Boolean relations \Gamma is closed under AND,
then CSP(\Gamma) is equivalent to the Horn clause satisfiability problem, Hornsat [24], which
is a tractable subproblem of the Satisfiability problem [26].
Similarly, a Boolean relation is closed under OR if and only if it can be defined by a
conjunction of clauses each of which contains at most one negated literal, and this class
or relations also gives rise to a tractable subproblem of the Satisfiability problem [26].Example 5.15 Let D be a finite subset of the natural numbers. The operation MAX :
which returns the larger of any pair of numbers is an ACI operation. The
following types of arithmetic constraints (amongst many others) are closed under this
operation:
where upper-case letters represent variables and lower-case letters represent positive con-
stants. Hence, by Theorem 5.13 it is possible to determine efficiently whether any collection
of constraints of these types has a solution. These constraints include (and extend)
the 'basic' arithmetic constraints allowed by the well-known constraint programming
language, CHIP [29]. 2
The class of tractable constraints first identified in [16], and referred to as max-closed
constraints, are in fact relations closed under an u operation with the additional property
that the partial order R, defined in Lemma 5.12, is a total ordering of D. Hence, a set
of constraints is max-closed if and only if the constraint relations are closed under some
specialized ACI operation of this kind (see, for example, Example 5.15). This class of
tractable constraints is referred to as Class II in [14].
However, we remark here that the class of tractable sets of relations defined by closure
under some ACI operation is a true generalization of the class containing all sets of max-
closed constraints. In other words, there exist tractable relations which are closed under
some ACI operation but are not closed under the maximum operation associated with
any (total) ordering of the domain. (An example of such a relation is the relation R 1
defined in Example 2.6, see Example 6.4 below.)
5.4 Affine operations
We will now show that closure under an affine operation is a sufficient condition for
tractability.
This result was established in [14] using elementary methods, for the special case when
the domain D contains a prime number, p, of elements. It was shown in [14] that, in this
special case, constraints which are closed under an affine operation correspond precisely
to constraints which may be expressed as conjunctions of linear equations modulo p.
(This class of tractable constraints is referred to as Class III in [14].)
We now generalise this result to arbitrary finite domain sizes by making use of a result
stated by Feder and Vardi in [8].
Theorem 5.16 ([8]) For any finite group G, and any set \Gamma of cosets of subgroups of
direct products of G, CSP(\Gamma) is solvable in polynomial time.
Corollary 5.17 For any set of relations \Gamma, if \Gamma is closed under an affine operation, then
CSP(\Gamma) is solvable in polynomial time.
Proof: By Definitions 3.1 and 3.2, any relation R which is closed under an affine
operation is a subset of a direct product of some Abelian group, with the property that
R. However, this is equivalent to saying that R is a
coset of a subgroup of this direct product group [21], so we may apply Theorem 5.16 to
\Gamma to obtain the result.
Example 5.18 Let r be the affine operation on which is defined by
addition and subtraction are both modulo 3.
The relation R 2 defined in Example 2.6 is closed under r, since applying the r
operation to any 3 elements of R 2 yields an element of R 2 . For example,
Since jDj is prime, the results of [14] indicate that R 2 must be the set of solutions to
some system of linear equations over the integers modulo 3. In fact, we have
Example 5.19 Let G be the Abelian group hD; +; \Gammai, where 3g and the
operation is defined by the following table:
Now let r be the affine operation on which is defined by r(d
addition and subtraction are as defined in G.
Any relation R over D which is a coset of a subgroup of a direct product of G will be
closed under r, and hence CSP(fRg) will be tractable by Corolllary 5.17. One example
of such a relation is the following:
It is easily seen that in this case R is not the set of solutions to any system of linear
equations over a field. 2
Example 5.20 When there is only one possible Abelian group structure
over D and hence only one possible affine operation on D.
If a set of Boolean relations \Gamma is closed under this affine operation, then CSP(\Gamma) is
equivalent to the problem of solving a set of simultaneous linear equations over the integers
modulo 2. This corresponds to the final tractable subproblem of the generalised
Satisfiability problem identified by Schaefer in [26]. 2
Semiprojections
We now show that closure under a semiprojection operation is not in general a sufficient
condition for tractability. In fact we shall establish a much stronger result, which shows
that even being closed under all semiprojections is not sufficient to ensure tractability.
Lemma 5.21 For any finite set D, with jDj - 3, there exists a set of relations \Gamma over
D, such that \Gamma is closed under all semiprojections on D, and CSP(\Gamma) is NP-complete.
Proof: Let D be a finite set with jDj - 3 and let d 1 ; d 2 be elements of D. Consider the
ig. This
relation is closed under all semiprojections on D, since any 3 elements of R contain at
most two distinct values in each coordinate position.
However, if we identify d 1 with the Boolean value true and d 2 with the Boolean
value false, then it is easy to see that CSP(fRg) is isomorphic to the Not-All-Equal
Satisfiability problem [11], which is NP-complete [26] (see Example 2.5).
It is currently unknown whether there are tractable sets of relations closed under some
combination of semiprojections, unary operations and binary operations which are not
included in any of the tractable classes listed above.
However, when the situation is very simple, as the next example shows.
Example 5.22 When there are no semiprojections on D, so there
are no subproblems of the Satisfiability problem which are characterised by a closure
operation of this form. 2
6 Calculating closure operations
For any set of relations \Gamma, over a set D, the operations under which \Gamma is closed are simply
mappings from D k to D, for some k, which satisfy certain constraints, as described in
Definition 3.3. In this Section we show that it is possible to identify these operations by
solving a single constraint satisfaction problem in CSP(\Gamma). In fact, we shall show that
these closure operations are precisely the solutions to a constraint satisfaction problem
of the following form.
Definition 6.1 Let \Gamma be a set of relations over a finite domain D.
For any natural number m ? 0, the indicator problem for \Gamma of order m is defined to
be the constraint satisfaction problem IP (\Gamma; m) with
ffl Set of variables D m ;
ffl Domain of values D;
ffl Set of constraints fC g, such that for each R 2 \Gamma, and for each sequence
of tuples from R, there is a constraint C
is the arity of R and
Example 6.2 Consider the relation R 1 over defined in Example 2.6.
The indicator problem for fR 1 g of order 1, IP(fR 1 g; 1), has 3 variables and 4 con-
straints. The set of variables is
and the set of constraints is
The indicator problem for fR 1 g of order 2, IP(fR 1 g; 2), has 9 variables and 16 con-
straints. The set of variables is
and the set of constraints is
Further illustrative examples of indicator problems are given in [15]. 2
Solutions to the indicator problem for \Gamma of order m are functions from D m to D, or in
other words, m-ary operations on D. We now show that they are precisely the m-ary
operations under which \Gamma is closed.
Theorem 6.3 For any set of relations \Gamma over domain D, the set of solutions to IP (\Gamma; m)
is equal to the set of m-ary operations under which \Gamma is closed.
Proof: By Definition 3.3, we know that \Gamma is closed under the m-ary
operation\Omega if and
only
if\Omega satisfies the
for each possible choice of R
(not necessarily all distinct). But this is equivalent to saying that
\Omega satisfies all the constraints in IP (\Gamma; m), so the result follows.
Example 6.4 Consider the relation R 1 over defined in Example 2.6.
The indicator problem for fR 1 g of order 1, defined in Example 6.2, has 2 solutions,
which may be expressed in tabular form as follows:
Variables
Solution
Solution
One of these solutions is a constant operation, so CSP(fR 1 g) is tractable, by Proposition
5.1. In fact, any problem in CSP(fR 1 g) has the solution which assigns the value 0
to each variable, so the complexity of CSP(fR 1 g) is trivial.
The indicator problem for fR 1 g of order 2, defined in Example 6.2, has 4 solutions,
which may be expressed in tabular form as follows:
Variables
Solution
Solution
Solution
Solution
The first of these solutions is a constant operation, and the second and third are essentially
unary operations. However, the fourth solution shown in the table is more
interesting. It is easily checked that this operation is an associative, commutative, idempotent
(ACI) binary operation, so we have a second proof that CSP(fR 1 g) is tractable,
by Theorem 5.13. Furthermore, this result shows that R 1 can be combined with any
other relations (of any arity) which are also closed under this ACI operation to obtain
larger tractable problem classes. 2
Corollary 6.5 For any set of relations \Gamma over a domain D, with jDj - 3, if all solutions
to IP (\Gamma; jDj) are essentially unary, then CSP(\Gamma) is NP-complete.
Proof: Follows from Theorem 3.8, Theorem 4.1, and Theorem 6.3.
Example 6.6 Recall the relations R 1 , R 2 and R 3 defined in Example 2.6. It has been
shown in Examples 6.4, 5.18, and 5.2 that a set containing any one of these relations on
its own is tractable.
For any set \Gamma containing more than one of these relations, it can be shown, using
Corollary 6.5, that CSP(\Gamma) is NP-complete. 2
In the special case when we obtain an even stronger result.
Corollary 6.7 For any set of relations \Gamma over a domain D, with solutions
to IP (\Gamma; are essentially unary then CSP(\Gamma) is NP-complete, otherwise it is polynomial.
Proof: It has been shown in Examples 5.3, 5.8, 5.14, 5.20, and 5.22 that when
possible closure operations of the restricted types specified in Corollary 4.2 are sufficient
to ensure tractability.
This result demonstrates that solving the indicator problem of order 3 provides a simple
and complete test for tractability of any set of relations over a domain with 2 elements.
This answers a question posed by Schaefer in 1978 [26] concerning the existence of an
efficient test for tractability in the Generalised Satisfiability problem. Note that
carrying out the test requires finding the solutions to a constraint satisfaction problem
with just 8 Boolean variables.
7 Conclusion
In this paper we have shown how the algebraic properties of relations can be used to
distinguish between sets of relations which give rise to tractable constraint satisfaction
problems and those which give rise to NP-complete problems. Furthermore, we have
proposed a method for determining the operations under which a set of relations is closed
by solving a particular form of constraint satisfaction problem, which we have called an
indicator problem.
For problems where the domain contains just two elements these results provide a
necessary and sufficient condition for tractability (assuming that P is not equal to NP),
and an efficient test to distinguish the tractable sets of relations.
For problems with larger domains we have described algebraic closure properties which
are a necessary condition for tractability. We have also shown that in many cases these
closure properties are sufficient to ensure tractability.
In particular, we have shown that closure under any constant operation, any majority
operation, any ACI operation, or any affine operation, is a sufficient condition for
tractability. It can be shown using the results of [13] that for any operation of one of
these types, the set, \Gamma, containing all relations which are closed under that operation is
a maximal set of tractable relations. In other words, the addition of any other relation
which is not closed under the same operation changes CSP(\Gamma) from a tractable problem
into an NP-complete problem. Hence, the tractable classes defined in this way are as
large as possible.
We are now investigating the application of these results to particular problem types,
such as temporal problems involving subsets of the interval algebra. We are also attempting
to determine how the presence of particular algebraic closure properties in the
constraints can be used to derive appropriate efficient algorithms for tractable problems.

Acknowledgments

This research was partially supported by EPSRC research grant GR/L09936 and by the
'British-Flemish Academic Research Collaboration Programme' of the Belgian National
Fund for Scientific Research and the British Council. We are also grateful to Martin
Cooper for many helpful discussions and for suggesting the proof of Theorem 5.7.



--R

"A relational model of data for large shared databanks"
"Derivation of constraints and database rela- tions"

"Characterizing tractable constraints"
"From local to global consistency"
"Structure identification in relational data"
"Network-based heuristics for constraint-satisfaction prob- lems"
"Monotone monadic SNP and constraint satisfaction"
"A sufficient condition for backtrack-bounded search"
"Eliminating interchangeable values in constraint satisfaction prob- lems"
Computers and intractability: a guide to the theory of NP-completeness
"Decomposing constraint satisfaction problems using database techniques"
"An algebraic characterization of tractable constraints"
"A unifying framework for tractable con- straints"
"A test for tractability"
"Tractable constraints on ordered domains"
"Fast parallel constraint satisfaction"
"On binary constraint problems"
"Classifying essentially minimal clones"
"Consistency in networks of relations"

"Networks of constraints: fundamental properties and applications to picture processing"
"Constraint relaxation may be perfect"
Computational Complexity
"Minimal clones I: the five types"
"The complexity of satisfiability problems"
Clones in
"On the Minimality and Decomposability of Row-Convex Constraint Networks"
"A generic arc-consistency algorithm and its specializations"
--TR
A sufficient condition for backtrack-bounded search
Network-based heuristics for constraint-satisfaction problems
Constraint relaxation may be perfect
From local to global consistency
Structure identification in relational data
A generic arc-consistency algorithm and its specializations
Fast parallel constraint satisfaction
Monotone monadic SNP and constraint satisfaction
On binary constraint problems
Decomposing constraint satisfaction problems using database techniques
Characterising tractable constraints
Tractable constraints on ordered domains
A relational model of data for large shared data banks
Computers and Intractability
A Unifying Framework for Tractable Constraints
The complexity of satisfiability problems

--CTR
Andrei Bulatov , Andrei Krokhin , Peter Jeavons, The complexity of maximal constraint languages, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.667-674, July 2001, Hersonissos, Greece
Yuanlin Zhang , Roland H. C. Yap, Consistency and set intersection, Eighteenth national conference on Artificial intelligence, p.971-972, July 28-August 01, 2002, Edmonton, Alberta, Canada
Richard E. Stearns , Harry B. Hunt, III, Exploiting structure in quantified formulas, Journal of Algorithms, v.43 n.2, p.220-263, May 2002
Hubie Chen, The expressive rate of constraints, Annals of Mathematics and Artificial Intelligence, v.44 n.4, p.341-352, August    2005
D. A. Cohen, Tractable Decision for a Constraint Language Implies Tractable Search, Constraints, v.9 n.3, p.219-229, July 2004
Peter Jeavons , David Cohen , Justin Pearson, Constraints and universal algebra, Annals of Mathematics and Artificial Intelligence, v.24 n.1-4, p.51-67, 1998
Lane A. Hemaspaandra, SIGACT news complexity theory column 34, ACM SIGACT News, v.32 n.4, December 2001
Lefteris M. Kirousis , Phokion G. Kolaitis, The complexity of minimal satisfiability problems, Information and Computation, v.187 n.1, p.20-39, November 25,
Andrei Bulatov , Martin Grohe, The complexity of partition functions, Theoretical Computer Science, v.348 n.2, p.148-186, 8 December 2005
Lane A. Hemaspaandra, SIGACT news complexity theory column 43, ACM SIGACT News, v.35 n.1, March 2004
Andrei A. Bulatov, H-Coloring dichotomy revisited, Theoretical Computer Science, v.349 n.1, p.31-39, 12 December 2005
Victor Dalmau , Peter Jeavons, Learnability of quantified formulas, Theoretical Computer Science, v.306 n.1-3, p.485-511, 5 September
David Cohen , Peter Jeavons , Richard Gault, New Tractable Classes From Old, Constraints, v.8 n.3, p.263-282, July
David Cohen , Peter Jeavons , Richard Gault, New tractable constraint classes from old, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA,
David Cohen , Peter Jeavons , Peter Jonsson , Manolis Koubarakis, Building tractable disjunctive constraints, Journal of the ACM (JACM), v.47 n.5, p.826-853, Sept. 2000
Hubie Chen, Periodic Constraint Satisfaction Problems: Tractable Subclasses, Constraints, v.10 n.2, p.97-113, April     2005
Richard Gault , Peter Jeavons, Implementing a Test for Tractability, Constraints, v.9 n.2, p.139-160, April 2004
Harry B. Hunt, III , Madhav V. Marathe , Richard E. Stearns, Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.183-191, July 2001, London, Ontario, Canada
Vctor Dalmau, A new tractable class of constraint satisfaction problems, Annals of Mathematics and Artificial Intelligence, v.44 n.1-2, p.61-85, May       2005
Peter Jonsson , Andrei Krokhin, Recognizing frozen variables in constraint satisfaction problems, Theoretical Computer Science, v.329 n.1-3, p.93-113, 13 December 2004
Martin Grohe , Dniel Marx, Constraint solving via fractional edge covers, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.289-298, January 22-26, 2006, Miami, Florida
Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
David A. Cohen , Martin C. Cooper , Peter G. Jeavons , Andrei A. Krokhin, The complexity of soft constraint satisfaction, Artificial Intelligence, v.170 n.11, p.983-1016, August 2006
Andrei A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM (JACM), v.53 n.1, p.66-120, January 2006
Georg Gottlob , Francesco Scarcello , Martha Sideri, Fixed-parameter complexity in AI and nonmonotonic reasoning, Artificial Intelligence, v.138 n.1-2, p.55-86, June 2002
Andrei A. Bulatov , Vctor Dalmau, Towards a dichotomy theorem for the counting constraint satisfaction problem, Information and Computation, v.205 n.5, p.651-678, May, 2007
Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States
Hubie Chen, A rendezvous of logic, complexity, and algebra, ACM SIGACT News, v.37 n.4, December 2006
Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001
complexity;NP-completeness;indicator problem;constraint satisfaction problem