BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1380
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Systems of Set Constraints with Negative Constraints are 
        NEXPTIME-Complete
AUTHOR:: Stefansson, Kjartan
DATE:: August 1993
PAGES:: 10
ABSTRACT::
A system of set constraints is a system of expressions $E\subseteq F$ where 
$E$ and $F$ describe sets of ground terms over a ranked alphabet. Aiken 
et al. [AKVW93] classified the complexity of such systems. In [AKW93] 
it was shown that if negative constraints $E\not\subseteq F$ were allowed, 
then the problem is decidable. This was done by reduction to a Diophantine 
problem, the Nonlinear Reachability Problem, which was shown to be decidable.

We show that nonlinear reachability is NP-complete. By bounding the 
reduction of [AKW93] we conclude that systems of set constraints, allowing 
negative constraints, is NEXPTIME-complete.
END:: CORNELLCS//TR93-1380
BODY::
Systems of Set Constraints with Negative
Constraints are NEXPTIME-Complete
Kjartan Stefansson*
TR 93-1380
August 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*Computer Science Department, Cornell University, Ithaca, NY 14853.
Systems of Set Constrai?ts with Negative
Coiistraiiits are NEXPTIME-Complete
Kjartau Stefansson *
stefan?cs.cornell.edu
August 30,1993
Abstract
A system of set constraints is a system of expressions E C F
where E and F describe sets of ground terms over a ranked alphabet.
Aiken et aL [AKvw93] classified the complexity of such systems. b?
[AKW93] it was shown that if negative constraints E ? F were al-
lowed, then the problem is decidable. This was done by reduction to
a Diophantine problem, the Nonlinear Reachability Problem, which
was shown to be decidable.
We show that nonlinear reachability is NP-complete. By bounding
the reduction of [AKW93] we conclude that systems of set constraints,
allowing negative constraints, is NEXPTIME-complete.
1			Introduction
In [AKW93] Aiken et al' show that it is decidable whether a system of set
constraints, including negative constraints, has a solution. The same result
was achieved independently by Gilleron el at. [GTT93]. The result of Aiken
et al. is achieved by reducing the set constraint problem to a hypergraph
reachability problem, which in turn is reduced to the Nonlinear Reachability
Problem (NRF). They proceed to show that NRP is decidable, thus proving
the set constraint problem decidable.
*Computer Science Department, Cornell University, Ithaca, NY 14853
In this paper we show that if NRP has a solution, then it must have
one of polynomial size. In particular, this shows NRP c NP, giving the
first elementary bound on the Nonlinear Reachability Problem. It is easy to
show that NRP is NF-hard, so NRP is NP-complete. This also gives the
first elementary bound on the system of set constraints where negative con-
straints are allowed. We bound the reduction of [AKW93] and conclude that
the general set constraint problem can be solved in nondeterministic expo-
nential time. Combining this with the fact that the simpler problem, solving
systems of set constraints with positive constraints only is NEXPTIME-hard
[AKVW93], we have shown the general problem to be NEXFTJME-complete
too.
We proceed by defining the NRP and an associated graph, whose prop-
erties characterize how close the NRP instance is to being solved.
2 The Nonlinear Reachability Problem
In [AKW93] Aiken et al. define the Nonlinear Reachability Problem (NJ?F).
We will define NRP again, but we refer the reader to [AKW93] for more
details and proofs of some of the lemmas we will use.
Let X be a set of variables ranging over IM. Consider a system C of
inequalities of the form p < q with p, q ? N[Xj where each p is a sum of
variables over X, and each x C X occurs in at most one left hand side p.
If x does occur in a left hand side of a constraint, x is said to be con-
strazned, and we denote the constraint by Px <
A valuation is a map u : X H ? The map u extends uniquely to a
semiring morphism N[X]
For a system C and x ? X, x is enabled under u if either
o+ x does not occur on any left hand side of C; or
o+ u(px) ?
The operation of incrementing the value of x under a valuation `a will be
denoted by appending x to v, i.e. define ux by
u(y)t1 if x=y,
ux(y) =			u(y)			otherwise.
2
The definition of ux extends to va for any a C X* by defining
v
v(ax)			(va)x
The valuation v is said to satisfy C if for all p < q ? C, v(p) ? v(q). Denote
by Vc be the set of all valuations satisfying C.
For v, v ? Vc and x ? we write v7>Xv if v ux and x is v-enabled.
Define the graph Cc (Vc, E) with a directed edge (v, v) labelled x if v&v.
Let X*(C, v) denote the set of paths a E X* in the graph Cc starting
at v. A path a ? X*(C, v) gives rise to a new valuation va : X IN with
va C Vc. A string a ? X* is said to be valid (for (C, v)) if a C x*(c, v). We
will use Greek letters for valuation strings a C x*(C, v), but Roman letters
for valuations v C Vc.
For ?,P c X*, we write 0 =x (3 if o(x) = P(x) for all x E X. Note that
? =? p iff ? and (3 are permutations of each other.
Definition 1 The Non1inea? Reackability Pwbleni (NRP) is the following
problem:
E]
Given a system 0 of constraints in variables X, a valuation s E Vc
and a special variable x0 c X, decide if there exists a a C x*(C, s)
such that sa(x0) > 0.
3 The Exposure Graph
As in [AKW93] we observe that for q c ?X1 and x ? X there is a unique way
to write q = ?W0Qx' with q? E IN[X --H fx?], and we say that x is v-exposed
in q if v(q?) > 0 for some 1 ? i ?
For an instance (X, 0, v) of NRP, we define the exposvre gr?ph to be the
directed graph C(v) = (V, E), where V = X and
E = ?(x,y) C V x V : xis v-exposed in q,,?.
It follows from the definition of exposure that 0(v) is contained in C(va),
i.e. the graph is monotonic under the operation of incrementing the valuation.
3
Let a ? X*(C, u). We say that a is zi-orderly if for alt ?, ?, ? ? X* and
x, y ? x, if there is a path from x to ? in G(ua), then all ocenuences of x
in a must occur before all occurrences of y in a.
In this definition x and y may be the same, in which case x occurring
in the u-orderly a implies there is no loop through x in G(ua), self-loops
included.
Lemma 2 Let a ? X*(C,u). If a satisfies
Vx ? X if x is on a cycle of C(ua) then a(x) 0
then there exists a' ? X*(C, u) with a' =x a such that a' is orderly.
(1)
Proof. If a s then a itself is orderly. Assume Ia > 1, and write
a = ?x?, where for all y ? &?, there is no path in C(ua) from `ito x. Such a
partition of a exists since otherwise for every element Wt of a there would be
another element Xj???1 of a with a path from Xj+1 to Xj in C(ua). Since there
are finitely many vanal?les X%, we would eventually get a repeated occurrence
of some variable of a, contradicting the property (1).
Since a = ?x? and for no ? ? a is (?, x) an edge of &(ua), we have that
x is u-enabled. We claim that xc C X*(C,u).
If not, say c = ciZc2, where xc1 is valid but xc1z is not. Since ciz is
valid, x and z must have the same defining constraint, p ?
Since xc1 ? X*(C, u) and c1z ? X*(C, u) we have uxci(q --H = 0 and
uci(q --H = 1. We note that z cannot be uc1-exposed in q (then z would
have a self-loop in G(ua), contradicting (1) above), so uciz(q--Hp) = 0. Since
x is uc1zc2-enabled but not uc1z-enabled, there is some I) C c2 where (y, x)
is an edge of G(ua), contradictii?g the choice of x. lience, xc must be valid,
and so is xcP.
By induction, c,3 can be rearranged to be ux-orderly, say 0,6 =x ? Then
x? =x a, and x? is ordeily. ?
Lemma 3 Let cy c x*(c, u) with c ? X* and y ? X. If c is u-orderly and
y is u-enabled, then ye ? x*(C, u)
Proof. We use induction, the case c = r being trivial. Assume c =
We will show that ?yx ? X*(C, u). Then by induction y? ? x*(c, a) and
4
hence y?x e x*(C, n). If ? is not constrained, the lemma holds trivially, so
assume p ? q is the constraint of ?.
In an orderly string a variable cannot change from enabled to nonenabled
and back to enabled. Thus ? is enabled throughout ci.
If x is also constrained by p ? q we cannot have n?(q --H 1, because
that would imply (x, x) were an edge of C(uci), contradicting that a is orderly.
Hence u?(q --H p) > 1 and we clearly have ?ux ? X*(C, v).
If x is not constrained by p < q then since ?y ? x*(C, v) we clearly have
?yx ? X*(C,u). E]
Lemma 4 Let ci ? X*(C, v), x ? X n X with ci(x) > 0. If ci is orderly
and U(v) = G(vci), then there exists ci' = ci1ci2 ? X*(C,v) with ci' =x ci,
ci1(x) > 0, cii ? n and ci2 orderly.
Proof. Write ci = Px?. Either x is v-enabled or there is some x1 C P
such that (x1, x) is an edge of G(v). Continuing this way we get a path
..... . , x1, x in G(v), where Xk is v-enabled. Since ci is orderly, k < n. Then
we can write ? = Pix?!3?. By applying Lemma 3 on PlXk we see that xk,31P2
is valid. Then ?1?2 is orderly since ,3 = PiXkP2 is. Now note that xk?i 15
vx?-enabled and xk?i,... , xi, x is a path in G(vxk) = G(vci). By induction,
we get that Px =x xkxk?i x1x? where xkxk?i x1xP ? X*(C,v). ?
For a valuation v, let sign v denote the valuation
sign v(y) =			1; ?????(?y) >0,
=0.
Lemma5 Letx?X,p?qcCandv,vcV?. Ifsignv(y)?signv(y)
for all y E X --H ?xt and x is v-exposed in q, then x is v-exposed in q. In
particular if sign v = sign v then G(u) =
Proof. This is Lemma 6.5(i) of [AKW93]. ?
Lemma 6 Assume cix C x*(C, v) where ci is orderly and G(u) = G(uci) C
G(ucix). Then there exist P? c X*(C,v) such that
1. ?? =x cix,
2. p
5
3. C(u?x) =
Proof. By Lemma 4, any variable of ? can be assumed to be fired within
n steps of ?, with the remainder of ? orderly. Thus it can be assumed that if
? fires k ? n variables, they are all fired within kn steps. So we can assume
= ?1?2 with ?iI ? kn and ?2 orderly.
If x is u?1-enabled, by Lemma 3 ?1x?2 e X*(C,u). If x is not u?1-
enabled, there is y c ?2 such that y is zt-exposed in q?. By Lemma 3 we can
assume y is fired within n steps of o??. Since sign u?1 = sign uot, y will still
be exposed in q?, by Lemma 5.
We have shown that ?x =? p? with f3 ? n2 and sign ax = sign j?
Along with Lemma 5 this proves conditions 1-3 of this lemma. E
Lemma 7 For a
a(x0) > 0. Then
a < n4, where a
system (X,n,C) with X = n, let a ? X*(C,u) with
there exists a & ? X*(C,u) with at = a?, a! =x a and
satisfies either
1. G(ua) has a self-loop based on an exposed variable; or
2. G(ua) has a cycle whose vertices are in at least two different con-
straints; or
3. a(x0) > 0.
Proof. It is clear that every a that is a solution for the system satisfies the
third condition of the lemma. Let a be the smallest prefix of a satisfying one
(or more) of the conditions of the lemma. If a = ? we are done, otherwise
write a = a'?. By Lemma 2 we can assume a'is orderly.
If C(zta) has a cycle, then every edge of the cycle can be added within
n2 steps, by Lemma 6. llence we can assume a creates the cycle within n3
steps.
If G(ua) contains a self-loop based on an exposed variable x, we can
again assume a creates the loop within n3 steps. By a proof similar to that
of Lemma 6, it takes at most n more steps to enable the variable x. E)
4 Reducing Solutions
We restate three important lemmas from [AKW93].
6
Lezuma 8 Let (X, u, C) be an instance of NRP, p ? q E C and E'
C --H ?p ? qJ. If x ? X is unconstrained and exposed in q, then (X,u,C1)
has a solution if and only if (X, u, C') does. Furthermore, any solution to
u, C) is also solution to (X, u,
Proof This is just a restatement of Lemma 6.14 in [AKw93]. E]
Lemma 9 Let (X, u, C) be an instance of NRP. Let x C X and assume
p < q ? C constrains x. Let
--H <--H qJ) u ? --H x ? q --H xi, if q --H x E ?X]
otherwise.
If x is u-enabled then (X, u, C) has a solution if and only if (X, u, G11) does.
Furthermore, any solution to (X, u, C) is also solution to (X, u,
Proof. This is just a restatenient of Lemma 6.15 in [AKw93], except for
the last statement, which is implicit in the proof given in [AiKw93]. ?
Lemma 10 Let (X, u, C) be an instance of NRP. Assume Wi,. .. , Xk C X
have pairwise different constraints p? ?			? C 1 ? i ? k. Define
k
pi
k
(C1 --H D) u fp' ?
If .... Xk is a loop in G(u), then (X, u, C) has a solution if and only
if (X, u, C') does. Furthermore, any solution to (X, u, C) is a solution to
(X, u,
Proof. This is just a rewording of Lemma 6.16 in [AKw93]. ?
Remark We note that if 0(u) contains a simple loop W1, . , Xk, where x?
and Xj have the same constraint, 0 ? i ? j ? k, then Wt,.. %-i is also a
loop. So whenever 0(u) contains a loop, it contains either a self-loop or a
cycle, where all the constraints of (?he vertices differ. ?
7
We now have a simple nondeterministic algorithm to compute a solution
to an instance of NRP, if such a solution exists. Consider the initial system
(X, ?, C). If u(x0) > 0, we are done.
1. If for some p < q ? C there is an unconstrained variable x ? X exposed
in q, we can remove p ? q from C by Lemma 8.
2. If &(zc) contains a self-loop based on x ? X and x is u-exposed, either
replace p < q by p --H x ? q --H x or remove p < q from C, as determined
by Lemma 9.
3. If C(u) contains a cycle through variables with different constraints,
Pi < .1.... ,Pt ? qt collapse these into one constraint, Pi ??? + Pt ?
q1 + + qt, by Lemma 10.
By the lemmas mentioned, the reduced system has a solution iff the original
system does.
Guess a string a ? X*, where a is the smallest string invoking one of
the events of Lemma 7. By that leinma, a ? n4. We can recursively solve
ua, C).
Each time we invoke one of the events of Lemma 7, it leads either to a so-
lution, or it removes a constraint from C or it makes a variable unconstrained.
Each of the events can happen at iiiost n times, so this is a nondeterministic
0(n5) algorithm to find a solution.
Theorem 11 NRP is NP-complete.
Proof By the above argument, NRP ? NP. It remains to show that
NRP is NP-hard. We give a reduction from CNFSAT.
Let 13 = A?i Cj be a Boolean formula in conjunctive normal form over
the Boolean variables ..... . , X?. Let Xt??08, ??ne? and c5 be integer variables,
1 < i < n 1 <j < m. For every clause Cj = Vi?ix? v Vj?jXj we create an
inequality
Z xfos + ?
i?I			j?J
xf.os + ??n.e?
b ?
i--Hi
8
Adding the inequalities
we have an instance of NRP where the special variable b can be fired iff 13 is
satisfiable. ?
5 Application to Systems of Set Constraints
In [AKVW93] the complexity of solving systems 8 of set constraints is con-
sidered. Assuming only positive set constraints (of the form E C F), the
problem is shown to be NEXPTIME-complete in general.
When negative set constraints are also allowed (P ? F), the problem
becomes significantly harder. In [AKW93] this problem is reduced to a hy-
pergraph problem. An instance 8 of set constraints is reduced nondetermin-
istically to a hypergraph (U, Ef f ? ?), where U 2o(IsI) The hypergraph
is then reduced to a disjunction of NRP instances VvEV N(v), where each
problem instance has size N(v) --H U10(') and V o(IUI).
In particular, we have an overall nondeterministic reduction of a general
system 8 of set constraints to an NI?P instance of size 2no(1). Since NRP is
in NP, we have a NEXPTIME algorithm to solve systems of set constraints,
where negative constraints are atlowed.
Since the simpler problem of solving set constraints with positive con-
straints only is NEXPTIME-hard we have shown:
Corollary 12 A system of set const?a?nts, including negative constraints, is
NEXPTIME-complete. z
6 Acknowledgments
Many thanks are due to Dexter Kozen for valuable discussions and sugges-
tions. This work was supported in part by the National Science Foundation
and in part by the United States Army R?esearch Office through the Army
Center of Excellence for Symbolic Methods in Algorithmic Mathematics (AC-
SyAM), Mathematical Sciences Institute of Cornell University under contract
DAALO3-91-C-0027.
9
References
[AKW93J A. Aiken, D. Kozen, and E. Wimmers. Decidability of systems
of set constraints with negative constraints. Technical Report 93-1362,
Computer Science Department, Cornell University, June 1993
[AKVW93] A. Aiken, D. Kozen, M. Vardi and E. Wimmers. The complexity
of set constraints. Technical Report 93-1352, Computer Science Depart-
ment, Cornell University, May 1993
[GTT93] R. Gilleron, 5. Tison, and M. Tommasi. Solving systems of set
constraints with negated subset relationships. Technical Report LIFL IT
247, Lille 1 University, March 1993
10
