How to Determine the Expressive Power of Constraints.
Some constraint languages are more powerful than others because they allow us to express a larger collection of problems. In this paper, we give a precise meaning to this concept of expressive power for constraints over finite sets of values. The central result of the paper is that the expressive power of a given set of constraint types is determined by certain algebraic properties of the underlying relations. These algebraic properties can be calculated by solving a particular constraint satisfaction problem, which we call an indicator problem. We discuss the connection between expressive power and computational complexity, and show that indicator problems provide a simple method to test for tractability.
Introduction
Some constraint languages are more powerful than others because they allow us to
express a larger collection of problems. For example, if we are dealing with applications
involving real-valued variables, then it is possible to express more numerical
relationships using arbitrary polynomial equations than if we were restricted to
using just linear equations. Similarly, if we are dealing with applications involving
Boolean variables, then it is possible to express more logical relationships using
ternary clauses than if we were restricted to using just binary clauses.
Of course, the penalty for increased expressive power is generally an increase in
computational complexity. For example, the satisfiability problem with ternary
clauses is NP-complete [6], whereas the satisfiabiliy problem involving only binary
clauses can be solved in polynomial time [6]. More generally, the finite constraint
satisfaction problem with arbitrary constraints is known to be NP-complete [13],
whereas many families of restricted constraints have been identified which give rise
to tractable subproblems [3, 9, 10, 11, 14, 17, 18]. For any given application, it
therefore pays to select a constraint system which has sufficient expressive power
to express the desired constraints, but is sufficiently restrictive to allow an efficient
solution technique.
In this paper, we focus on problems with finite sets of possible values and examine
how the expressive power of a given set of constraint types may be defined. The
central result of the paper is that the expressive power of a given set of constraint
types is determined by certain algebraic properties of the corresponding relations.
We also show how these algebraic properties can be calculated by solving a particular
constraint satisfaction problem, which we call an 'indicator problem'. Finally,
we discuss the connection between expressive power and computational complexity,
and show that indicator problems provide a simple method to test for tractability.
The paper is organised as follows. In Section 2 we give the basic definitions,
and describe a general form of algebraic closure property for a set of relations. In
Section 3 we describe how to calculate these closure properties and in Section 4
we establish the close link between closure properties and expressive power. In
Section 5 we discuss the relationship between expressive power and tractability.
Finally, we summarise the results presented and indicate some directions for future
research.
2. Definitions
2.1. The constraint satisfaction problem
A central notion in the study of constraints and constraint satisfaction problems is
the idea of a relation, so we will make extensive use of the following notation.
Notation 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 will be
written in the form ht[1];
Definition 1. A subset of D n is called an n-ary relation over D.
Example 1 We now describe four relations which will be used as examples through-out
the paper.
Each of these relations is a set of tuples of elements from the set
as defined below:
In order to manipulate and combine relations, we will make use of the following
standard operations from relational algebra [2]:
Definition 2. We define the following operations on relations.
ffl Let R 1 be an n-ary relation over a set D and let R 2 be an m-ary relation over
D. The Cartesian product R 1 \Theta R 2 is defined to be the (n m)-ary relation
ffl Let R be an n-ary relation over a set 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 set D. Let i be a sequence of indices
chosen from the values n. The projection -
(R) is defined to be the
k-ary relation
We now define the (finite) constraint satisfaction problem which has been widely
studied in the Artificial Intelligence community [12, 13, 14].
Definition 3. An instance of a constraint satisfaction problem consists of
ffl a finite set of variables,
ffl a finite set of values, D;
ffl a set of constraints fC g.
Each constraint C i is a pair (s i list of variables of length
called the constraint scope, and R i is an m i -ary relation over D, called the
constraint relation.
The tuples of the constraint relation R i indicate the allowed combinations of simultaneous
values for the variables in the corresponding scope s i . The length of these
tuples will be called the arity of the 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.
Notation 2 For any set of relations, \Gamma, the class of all constraint satisfaction
problem instances in which the constraint relations are elements of \Gamma will be denoted
CSP(\Gamma).
Example be the set of four relations, fR 1 as defined in
Example 1.
One element of CSP(\Gamma) is the constraint satisfaction problem instance, P, which
has 6 variables and 3 constraints, defined as follows:
ffl The set of variables is
ffl The set of values is
ffl The set of constraints is fC
The structure of this problem instance is illustrated in Figure 1. 2
oe
ae
x
x
x
x
x
x

Figure

1. The CSP instance defined in Example 2
A solution to a constraint satisfaction problem is a function from the variables
to the values such that the combination of values assigned to the variables in each
constraint scope is allowed by the corresponding constraint. For any given problem
instance we may wish to:
ffl decide whether a solution exists; or
ffl find one solution, if any exist; or
ffl count the number of solutions; or
ffl find all solutions.
Each of these tasks may have a different complexity, so it is important to be precise
about which version of the problem we are trying to solve.
It is often convenient to view the solutions to a constraint satisfaction problem as
tuples in a relation, as illustrated in the next example. This relation is the largest
relation, S, such that the projection of S onto each constraint scope is a subset of
the corresponding constraint relation.
Example 3 The solutions to the constraint satisfaction problem instance P defined
in Example 2 are functions from the set of variables V to the set of values D
which satisfy all of the constraints.
There are four such functions, which may be expressed in tabular form, as follows:
Variables
Solution
Solution
Solution
Solution
This set of solutions may also be viewed as a relation, S, of arity 6, which has four
tuples, corresponding to the four rows in the table. 2
2.2. Expressive power of constraints
In any constraint satisfaction problem instance some of the constraints are explicit,
whilst others are generally present only as implicit constraints. For any instance in
CSP(\Gamma), the explicit constraint relations must be elements of \Gamma, but there may be
implicit constraints on some subsets of the variables for which the corresponding
relations are not elements of \Gamma. These implicit constraints result from the combined
effects of the explicit constraints, and so are said to be 'derived' from these explicit
constraints.
We now define exactly what it means to say that a constraint relation can be
derived from other constraint relations, and what is meant by 'expressive power'.
Definition 4. A relation R can be derived from a set of relations \Gamma if it is equal
to some projection of the set of solutions to some constraint satisfaction problem
instance in CSP(\Gamma).
Example 4 Reconsider the set of solutions S for the constraint satisfaction problem
instance P, defined in Example 2, as described in Example 3.
Note that - 1;2 binary relation can be derived
from g. 2
One way to view Definition 4 is as follows. For any relation R of arity r, and
any collection of r variables, R can be derived from \Gamma if and only if it is possible to
construct a constraint satisfaction problem instance in CSP(\Gamma) which imposes the
relation R on the values of those variables. In other words, R can be derived from
precisely when there is some combination of the relations in \Gamma that can be used
to 'express' a constraint with relation R.
Definition 5. The set of all relations that can be derived from \Gamma will be called
the expressive power of \Gamma.
We now show that the notion of a derived relation corresponds precisely to the
notion of a relation which may be obtained using the operations described in Definition
2.
be a set of relations over a finite set D.
A relation R can be derived from \Gamma if and only if R can be obtained from the
elements together with the unary relation D 1 , using some finite sequence of
Cartesian product, equality selection, and projection operations.
Proof:
We first need to show that if R is a projection of the set of solutions to some
instance 1 in CSP(\Gamma), then R can be obtained from \Gamma [ using some finite
sequence of Cartesian product, equality selection, and projection operations.
It is shown in [7] that the set of solutions to any constraint satisfaction problem
instance can be obtained by performing a relational join operation on the
constraint relations (see Definition 2.8 of [7]). For any instance in CSP(\Gamma) the
relations to be joined will either be elements of \Gamma, or the unary relation D 1 (in
the case of variables with no explicit constraint specified).
Furthermore, it is a standard result of relational database theory [2] that the
join operation can be calculated by performing a sequence of Cartesian product,
equality selection and projection operations.
Hence R can be obtained using the specified relational operations.
Conversely, if R can be obtained from \Gamma [fD 1 g using some sequence of Cartesian
product, equality selection, and projection operations, then we need to show
that R is equal to some projection of the set of solutions to some instance in
CSP(\Gamma).
To establish this, we first note that, for each of the specified operations, it
is straightforward to construct an associated constraint satisfaction problem
instance P in CSP(\Gamma) such that the result of that operation is equal to some
projection of the set of solutions to P. (The effect of the equality selection
operation is achieved by identifying the corresponding variables in P.)
By combining these constructions we can derive R from \Gamma.
In view of this result, it will be convenient to introduce the following notation.
Notation 3 Let \Gamma be a set of relations over a set D.
The set of all relations which may be obtained from \Gamma, together with the unary
relation D 1 , using some finite sequence of Cartesian product, equality selection, and
projection operations, will be denoted
states that the set of relations \Gamma precisely equal to the expressive
power of \Gamma, as defined above.
2.3. Closure properties of relations
We will show in Section 4 that the set of relations \Gamma + is determined by certain
algebraic properties of \Gamma. In order to describe these properties, we need to consider
arbitrary operations on a set D, in other words, arbitrary functions from D k to D,
for arbitrary values of k.
Any such operation on D may 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 a set may be used to define an operation on the
tuples in a relation over that set, as follows:
Definition 6. Let R be an n-ary relation over a set D, and
any k-ary operation on D.
For any collection of k tuples, t necessarily all distinct) the
defined as follows:
Using this definition, we now define the following closure property of relations.
Definition 7. Let R be a relation over a set D, and
D be a k-ary
operation on D.
R is said to be closed
under\Omega if, for all (not necessarily all
distinct),\Omega
Example 5 Let 4 denote the ternary operation which returns the first repeated
value of its three arguments, or the first value if they are all distinct.
The relation R 2 , defined in Example 1, 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 1 , defined in Example 1, is not closed under 4, since applying the
4 operation to the last 3 elements of R 1 yields a tuple which is not an element of
positive integer m, and any positive integer i - m, let
denote the operation of arity m which returns the value of its
ith argument. In other words, for all d
Every relation R over D is closed under @ m;i for all values of m and i, since
applying the @ m;i operation to any m elements of R simply returns the ith one. 2
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 each of the operations
on relations described in Definition 2.
R and R 0 be relations which are closed
under\Omega , for some operation
\Omega .
The following relations are also closed
1. the Cartesian product, R \Theta R 0 ;
2. any projection of R or R 0 ;
3. any equality selection from R or R 0 .
Proof: Follows immediately from the definitions.
Relations which are closed under the same operations have many common proper-
ties, so we introduce the following notation.
Notation 4 Let \Gamma be a set of relations over a set D.
The set of all relations over D which are closed under all of the operations under
which \Gamma is closed will be denoted \Gamma.
3. Calculating Closure Operations
In view of the results presented later in this paper, it is important to be able to
calculate the closure operations for a given set of relations. In this section, we show
that it is possible to obtain these operations, for each possible arity, by obtaining
all solutions to a single constraint satisfaction problem instance.
First note that, 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
conditions, as described in Definition 7. This suggests that it should be possible to
define a constraint satisfaction problem in which the variables are the elements of
and the constraints impose the necessary conditions to ensure that the solutions
are closure operations. This is the motivation for the idea of an 'indicator problem'
which is defined as follows.
Definition 8. Let \Gamma be a set of relations over a finite set D.
For any natural number m ? 0, the indicator problem for \Gamma of order m is defined
to be the constraint satisfaction problem instance IP (\Gamma; m) with
ffl set of variables D m ;
ffl set 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
Note that for any set of relations \Gamma over a set D, IP (\Gamma; m) has jDj m variables and
constraints.
Example 7 Consider the relation R 1 over defined in Example 1.
The indicator problem for fR 1 g of order 1, IP(fR 1 g; 1), has 3 variables and 4
constraints. 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
constraints. The set of variables is
and the set of constraints is
Example 8 Consider the relation R 2 over defined in Example 1.
The indicator problem for fR 2 g of order 1, IP(fR 2 g; 1), has 3 variables and 3
constraints. The set of variables is
and the set of constraints is
The indicator problem for fR 2 g of order 2, IP(fR 2 g; 2), has 9 variables and 9
constraints. The set of variables is
and the set of constraints is
Consider the relations R 1 and R 2 over defined in Example
1.
The indicator problem for fR 1 of order 1, IP(fR 1
and 7 constraints. The set of variables is
and the set of constraints is equal to the union of the set of constraints of IP(fR 1
as defined in Example 7, and the set of constraints of IP(fR 2 g; 1), as defined in
Example 8.
The indicator problem for fR 1 of order 2, IP(fR 1
and 25 constraints. The set of variables is
and the set of constraints is equal to the union of the set of constraints of IP(fR 1
as defined in Example 7, and the set of constraints of IP(fR 2 g; 2), as defined in
Example 8. 2
Solutions to the indicator problem for \Gamma of order k are functions from D k to D,
or in other words, k-ary operations on D. We now show that they are precisely the
k-ary operations under which \Gamma is closed.
Theorem 1 For any set of relations \Gamma over a set D, the set of solutions to IP (\Gamma;
is equal to the set of k-ary operations under which \Gamma is closed.
Proof: By Definition 7, we know that \Gamma is closed under the k-ary
operation\Omega
if and only
if\Omega satisfies the condition
for each possible
choice of R (not necessarily all distinct). By Definition 8,
this is equivalent to saying
satisfies all the constraints in IP (\Gamma; k), so the
result follows.
Example 10 Consider the relation R 1 over defined in Example 1.
The indicator problem for fR 1 g of order 1, defined in Example 7, has 2 solutions,
which may be expressed in tabular form as follows:
Variables
Solution
Solution
Hence, by Theorem 1, fR 1 g is closed under precisely two unary operations: the
constant operation with value 0, and the identity operation.
The indicator problem for fR 1 g of order 2, defined in Example 7, has 4 solutions,
which may be expressed in tabular form as follows:
Variables
Solution
Solution
Solution
Solution
Hence, by Theorem 1, fR 1 g is closed under precisely four binary operations. 2
Example 11 Consider the relation R 2 over defined in Example 1.
The indicator problem for fR 2 g of order 1, defined in Example 8, has 3 solutions,
which may be expressed in tabular form as follows:
Variables
Solution
Solution
Solution
Hence, by Theorem 1, fR 2 g is closed under precisely three unary operations.
The indicator problem for fR 2 g of order 3, has a very large number of solutions,
including the operation 4, defined in Example 5. Hence fR 2 g is closed under this
ternary operation, as well as a large number of others. 2
4. Closure Operations and Expressive Power
We have so far defined two sets of relations which are associated with a given set
\Gamma: the set of relations which can be derived from \Gamma, denoted and the set of
relations which share the same closure operators as \Gamma, denoted \Gamma.
In this section, we will show that these two sets of relations, which are defined in
very different ways, are actually identical.
Theorem 2 For any set of relations, \Gamma, over a finite set D,
Proof: By Lemma 2, we know that the property of being closed under any operation
is preserved by Cartesian product, projection, and selection operations. It
follows immediately that
To obtain the reverse inclusion, let any relation in \Gamma.
Construct the indicator problem for \Gamma of order m, IP (\Gamma; m), and let S be the
set of solutions to IP (\Gamma; m), viewed as a relation. Since every constraint relation
in IP (\Gamma; m) is an element of \Gamma, we know that S can be derived from \Gamma, and hence
We claim that R can be obtained as a projection of S, and hence R also belongs
which gives the result.
To establish this claim, let r be the arity of R, and let c
Each c j is an element of D m , and hence corresponds to some
variable of IP (\Gamma; m), and hence to some coordinate position, p j , of S. Let
(S).
By the construction of T , each tuple of T is equal to the result of applying one
solution of IP (\Gamma; m) to the sequence of tuples belongs to \Gamma,
we know that R is closed under all solutions of IP (\Gamma; m), by Theorem 1, so each
tuple in T must belong to R. Hence, T ' R.
Conversely, it was shown in Example 6 that every relation is closed under the
operations @ m;i , for m. Hence, by Theorem 1, each @ m;i is a solution
of IP (\Gamma; m), and so gives rise to a tuple in T . By the construction of T , and the
definition of @ m:i , this tuple is equal to t i . Hence, R ' T .
Hence which establishes the claim.
Combining this result with Lemma 1, we have shown that the expressive power
of a set of relations is determined by the corresponding set of closure operations.
Corollary 1 A relation R can be derived from a set of relations \Gamma over a finite
set D if and only if R is closed under all of the operations under which \Gamma is closed.
Example 12 Reconsider the relations R 1 and R 2 over defined in
Example 1.
It was shown in Examples 10 and 11 that R 1 is not closed under all the operations
under which R 2 is closed. Hence, by Corollary 1, R 1 cannot be derived from R 2 .
Similarly, the results given in Examples 10 and 11 also establish that R 2 cannot
be derived from R 1 . 2
5. Expressive Power and Complexity
We have seen that the expressive power of a set of relations is determined by their
closure operations. To illustrate one application of these results, we now examine
how they can be used to obtain information about the complexity of the class of
problem instances involving a given set of constraint types.
Deciding whether or not a given constraint satisfaction problem instance has a
solution is NP-complete in general [13] even when the constraints are restricted to
binary constraints. In this section, we shall consider how restricting the allowed
constraint relations to some fixed subset of all the possible relations affects the
complexity of this decision. We shall therefore regard CSP(\Gamma) as a decision problem
in which the question to be decided in each instance is the existence of a solution.
If there exists an algorithm which decides every instance in CSP(\Gamma) in polynomial
time, then we shall say that \Gamma is a tractable set of relations.
Example 13 The binary inequality 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 [6]. This problem is tractable when jDj - 2 and NP-complete when
The relation R 4 , defined in Example 1, is equal to the relation 6= D for
2g. Hence, CSP(\Gamma) is NP-complete for any set of relations \Gamma which contains
R 4 . 2
It turns out that certain special operations play a major role in distinguishing
tractable and intractable sets of relations. These operations are the 'essentially
unary operations', which are defined as follows.
Definition 9. An
called essentially unary if there
exists some non-constant unary operation f : D ! D and some i in the range 1 to
k such
If f is a permutation,
then\Omega is called essentially permuting.
Example 14 The operations @ m;i , defined in Example 6, are all essentially unary
operations. 2
Note that constant functions are excluded from Definition 9, and so are not essentially
unary.
Theorem 3 Let \Gamma be a set of relations over a finite set D.
If every operation under which \Gamma is closed is essentially unary, then CSP(\Gamma) is
NP-complete.
Proof: Assume that \Gamma is only closed under essentially unary operations.
First, we note that if \Gamma is closed under some essentially unary
operation\Omega , then
it is also closed under the corresponding (non-constant) unary operation f .
Let f 0 be a unary operation under which \Gamma is closed such that jf 0 (D)j is minimal.
\Gammag. By the choice of f 0 , and the assumption
about \Gamma, it follows that f 0 (\Gamma) is only closed under essentially permuting operations.
\Gamma is not closed under any constant operation (by assumption), we know
that jf 0 (D)j ? 1. There are 2 cases to consider.
ffl In the case where jf 0 2, we consider the ternary 'not-all-equal' relation,
N , over D, (i.e., the relation containing all 3-tuples over D in which the 3
values are not all equal). The relation N is closed under all essentially permuting
operations on D, which means that N 2 f 0 (\Gamma). By Theorem 2 and
Lemma 1, this implies that N may be derived from f 0 (\Gamma). Hence, CSP(fNg)
may be reduced to CSP(f 0 (\Gamma)) in polynomial time. Now, CSP(fNg) is equivalent
to the Not-All-Equal Satisfiability problem, which is known to be
NP-complete [6, 15], so it follows that CSP(f 0 (\Gamma)) is also NP-complete.
ffl In the case where jf 0 (D)j ? 2, we consider the binary disequality relation,
, defined in Example 13. The relation 6= f0(D) is closed under all essentially
permuting operations on D, which means that 6= f0(D) 2 f 0 (\Gamma). By
Theorem 2 and Lemma 1, this implies that 6= f0(D) may be derived from f 0 (\Gamma).
Hence, CSP(f6= f0(D) g) may be reduced to CSP(f 0 (\Gamma)) in polynomial time.
is equivalent to the jf 0 (D)j-Colorability problem,
which is known to be NP-complete when jf
Finally, any instance in CSP(f 0 (\Gamma)) has a solution if and only if the corresponding
instance in CSP(\Gamma) has a solution, because \Gamma is closed under f 0 . Hence CSP(f 0 (\Gamma))
is reducible to CSP(\Gamma) in polynomial time, which establishes that CSP(\Gamma) is also
NP-complete.
If we assume that NP-complete problems do not have polynomial-time algorithms,
then this result provides a necessary condition for tractability: a tractable set of
relations must be closed under some operation which is not essentially unary.
In fact, it was shown in [9] that all the currently known examples of tractable
constraint types can be characterised as sets of relations which are closed under
particular non-unary operations, even in those cases where they were originally
defined using very different criteria. For example, the '0/1/all' relations 2 , first
described in [3, 11], can be characterised as the set of all relations closed under
the operation 4, defined in Example 5. As a second example, the various sets of
'max-closed' relations, first described in [10], can each be characterised as the set
of relations closed under a particular binary associative, commutative, idempotent
operation [9].
We may sharpen the result of Theorem 3 a little further by bounding the possible
arity of the closure operations on \Gamma which we need to consider, as the next result
shows.
Theorem 4 For any set of relations \Gamma over a finite set D, if \Gamma is closed under
some
operation\Omega which is not essentially unary, then it is also closed under some
operation
-\Omega of arity at most maxf3; jDjg, which is not essentially unary.
Proof: (This proof is adapted from the proof of Lemma 1.14 in [16]). Let \Gamma be
a set of relations which is closed under some
operation\Omega which is not essentially
unary. Let
-\Omega be an operation of the smallest possible arity, such that \Gamma is closed
under
-\Omega and
-\Omega is not essentially unary, and let k be the arity of
-\Omega . If k - 3, then
the result holds, so we only need to consider the case where k - 4.
Now consider the operations which are obtained from
-\Omega by identifying two arguments
(i.e., requiring them to have the same value). Since \Gamma is closed under these
operations, which have a lower arity than
-\Omega , they must all be essentially unary.
Hence, if we identify the first two arguments we have
z -
for some non-constant unary operation f 12 and some i 2 kg. Similarly, if
we identify the third and fourth arguments we have
z -
for some non-constant unary operation f 34 and some j 2 kg. This means
that
z -
z -
for all possible choices of x which implies that either i 62 f1; 2g
or j 62 f3; 4g. It follows from this that we can permute the order of the arguments
of
-\Omega to obtain a function \Phi which satisfies the identity
z-
for some non-constant unary operation f . In particular, we have
distinct pairs of indices we know that the
is an essentially unary function. Since we have just shown that for the case x
the value of this function is equal to f(x 1 ), we know that it must
equal cases.
Similarly, for all indices
is an essentially unary function. When the remaining arguments all have the same
value, then this function is equal to f(x), by the arguments above. Hence it must
be equal to f(x) in all cases.
there are more arguments than values, so at least one
argument value must be repeated somewhere, and in all such cases we have shown
that just
-\Omega with the order of the arguments
permuted, we have contradicted the fact that
-\Omega is not essentially unary. This means
that we must have k - jDj, and the result follows.
In order to use Theorem 3 to draw conclusions about the tractability of a set of
constraints we need to be able to distinguish closure operations which are essentially
unary from those which are not. By Definition 9, this means examining each
solution to the appropriate indicator problem to check whether the value of the
solution at each variable is determined by a single coordinate position in the tuple
describing that variable. For an operation of arity m, this checking may be carried
out in mjDj m steps.
Alternatively, the next result shows that the number of solutions to certain indicator
problems provides a sufficient condition for establishing NP-completeness,
without needing to examine the individual solutions in detail.
be a set of relations over a set D, let S 1 be the set of non-constant
solutions to IP (\Gamma; 1), and let Sm be the set of solutions to IP (\Gamma; m), where
then CSP(\Gamma) is NP-complete.
Proof: By Theorem 3 and Theorem 4, we know that either CSP(\Gamma) is NP-
complete, or \Gamma is closed under some operation which is not essentially unary, and
which has arity at most m.
By Theorem 1, Sm is the set of all m-ary operations under which \Gamma is closed. By
Definition 9, the number of operations in Sm which are essentially unary is equal to
the number of non-constant unary operations under which \Gamma is closed, multiplied
by m. By Theorem 1, this number is mjS 1 j. Hence, jS m j - mjS 1 j in all cases.
In the limiting case, when jS we know that every element of Sm
is essentially unary, so \Gamma is not closed under any m-ary operation which is not
essentially unary. It follows that \Gamma is not closed under any operation of arity
lower than m which is not essentially unary, so CSP(\Gamma) must be NP-complete.
Corollary 2 establishes NP-completeness for many sets of constraints without the
need for individually constructed, ad-hoc reduction arguments, as the following
examples illustrate.
Example 15 Consider the relations R 1 and R 2 over defined in
Example 1.
The indicator problem for fR 1 of order 1, defined in Example 9, has 1 solu-
tion, corresponding to the identity operation.
The indicator problem for fR 1 of order 3, has 3 solutions (which are all
essentially unary).
Hence is NP-complete, by Corollary 2.
On the other hand, it was shown in Example 10 that R 1 is closed under a constant
operation, so CSP(fR 1 g) is tractable, by Proposition 9 of [9]. In fact, any problem
in CSP(fR 1 g) has the solution which assigns the value 0 to each variable, so this
class of problems is trivial.
Furthermore, it was shown in Example 11 that R 2 is closed under the operation
4, defined in Example 5. Hence, CSP(fR 2 g) is tractable, by Theorem 13 of [9]. 2
Example Consider the relations R 1 defined
in Example 1.
By counting the solutions to the indicator problems of order 1 and order 3 for each
relation and each pair of distinct relations in this set, we are able to complete the
analysis of the complexity of CSP(\Gamma) for each possible subset \Gamma of these relations.
Relations # Solutions # Solutions Complexity
(Corollary
(Corollary
(Corollary
For all larger sets of relations we have that \Gamma contains at
least one of the pairs of relations shown in the table, and so CSP(\Gamma) is NP-complete.How practical is the test proposed here in general? For small values of jDj, the
relevant indicator problems have very few variables, and the solutions may be found
easily. This remains true even when the arity of the relations in \Gamma is large.
In the simplest case, when 2, the constraint satisfaction problem corresponds
to the classical Satisfiability problem [6], for which all possible tractable
sets of relations are known, and are fully described in [15]. The only non-trivial examples
in this case are the sets of Boolean relations which can be expressed by Horn
clauses, or the duals of Horn clauses, or clauses containing at most two literals, or
linear equations over the two-element field [15]. It has been shown that any set of
relations that is closed under an operation which is not essentially unary belongs
to one of these tractable classes [8]. Hence the condition described in Corollary 2
is both necessary and sufficient for NP-completeness in this case (assuming that
P is not equal to NP). It follows from this that solving the indicator problems of
order 1 and order 3 provides a simple and complete test for tractability of any set
of relations over any set with 2 elements. This provides a very practical answer to a
question posed by Schaefer in 1978 [15] concerning the existence of an efficient test
for tractability in the Generalized Satisfiability problem. Note that carrying
out the test requires finding the number of solutions to a constraint satisfaction
problem with just 8 Boolean variables.
As the size of D increases, the size of the relevant indicator problems increases
rapidly, and it may become impractical to compute all solutions, or even to calculate
the number of solutions, as required by Corollary 2. On the other hand,
for cases of interest, it may be possible to establish from known properties of the
constraints that the relevant indicator problems will have particular types of solu-
tion, without carrying out a complete solution algorithm. This question is currently
being investigated.
6. Conclusion
In this paper we have shown how the algebraic properties of relations can be used
to determine the expressive power of a set of possible constraint types.
Furthermore, we have proposed a method for determining these algebraic properties
by solving a particular form of constraint satisfaction problem, which we have
called an indicator problem.
Finally, we have shown that there are simple algebraic properties which distinguish
between sets of relations which give rise to tractable constraint satisfaction
problems and those which give rise to NP-complete problems. We have used these
results to obtain a sufficient condition for NP-completeness, which we have shown
is widely applicable and easy to test.
For problems where the set of possible values contains just two elements these
results provide a necessary and sufficient condition for NP-completeness (assuming
that P is not equal to NP), and an efficient test to distinguish the tractable sets of
relations.
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 may be used to derive appropriate efficient algorithms
for tractable problem classes.

Acknowledgments

We are grateful to Victor Dalmau for helpful discussions which greatly simplified
the proof of Theorem 2
Notes
1. Since D is finite, and hence there are only finitely many possibilities for R at each arity, we
may assume, without loss of generality, that this instance contains only a finite number of
constraints.
2. Also called 'implicational' relations [11].



--R

"Constraint Satisfaction From a Deductive Viewpoint"
"A Relational Model of Data for Large Shared Databanks"
"Characterizing tractable constraints"
"Structure identification in relational data"
"A sufficient condition for backtrack-bounded search"
Computers and intractability: a guide to NP-completeness
"Decomposing constraint satisfaction problems using database techniques"
"An algebraic characterization of tractable constraints"
"A unifying framework for tractable constraints"
"Tractable constraints on ordered domains"
"Fast parallel constraint satisfaction"
"On binary constraint problems"
"Consistency in networks of relations"
"Networks of constraints: fundamental properties and applications to picture processing"
"The complexity of satisfiability problems"
Clones in Universal Algebra
"On the Minimality and Decomposability of Row-Convex Constraint Net- works"
"A generic arc-consistency algorithm and its specializations"
--TR

--CTR
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 43, ACM SIGACT News, v.35 n.1, March 2004
Richard Gault , Peter Jeavons, Implementing a Test for Tractability, Constraints, v.9 n.2, p.139-160, April 2004
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
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
constraint satisfaction problem;complexity;NP-completeness;relational algebra;indicator problem