The computational complexity of dominance and consistency in CP-nets

1 Introduction

The problems of eliciting, representing and reasoning with preferences over a multivariable (or, multiattribute) domain arise in many �elds such as planning, design, and group decision making. An explicit representation of a preference ordering of elements (we refer to them as outcomes) of such multivariable domains is exponentially large in the number of attributes. Therefore, AI researchers have developed languages for representing preference orderings succinctly. The formalism of CP-nets [Boutilier et al., 1999] is among the most popular ones. A CP-net provides a succinct representation of preference ordering on outcomes in terms of local preference statements of the form p : xi > xj , where xi, xj are values of a variableX and p is a logical condition. Informally, a preference statement p : xi > xj means that given p, xi is (strictly) preferred to xj ceteris paribus, that is, all other things being equal. The meaning of a CP-net is given by a certain ordering relation (dominance) on the set of outcomes, derived from such reading of preference statements. If one outcome dominates another, we say that the dominant one is preferred.

Reasoning about the preference ordering (dominance relation) expressed by a CP-net is far from easy. The key problems include dominance testing and consistency testing. In the �rst problem, given a CP-net and two outcomes α and β, we want to decide whether β dominates α. The second problem asks whether there is a dominance cycle in the dominance ordering de�ned by an input CP-net, that is, whether there is an outcome that dominates (is preferred to) itself.

Miroslaw Truszczy ´nski Dept. of Comp. Sci.

University of Kentucky Lexington, KY 40506-0046, USA mirek@cs.uky.edu Cork Constraint Computation Centre University College Cork Ireland n.wilson@4c.ucc.ie

We study the computational complexity of these two problems. The results obtained so far concerned only restricted classes of CP-nets, all requiring that the graph of variable dependencies implied by preference statements in the CP-net be acyclic. Under certain assumptions, the dominance-testing problem is in NP and, under some additional assumptions, even in P [Domshlak and Brafman, 2002; Boutilier et al., 2004a]. Its complexity in the general case has remained until now an open problem. We show that it is in fact PSPACEcomplete, even for the propositional case, by exhibiting in Section 4 a PSPACE-hardness proof for dominance testing.

To prove the hardness part of the results, we �rst establish the PSPACE-hardness of some problems related to propositional STRIPS planning. We then show that these problems can be reduced to CP-net dominance and consistency testing by exploiting connections between actions in STRIPS planning and preference statements in CP-nets.

We then turn to consistency testing. While acyclic CPnets are guaranteed to be consistent, this is not the case with general CP-nets (see [Domshlak and Brafman, 2002; Brafman and Dimopoulos, 2004] for detailed examples and discussions). In Section 5, we show that consistency testing is as hard as dominance testing.

We assume some familiarity with the complexity class PSPACE (we refer to [Papadimitriou, 1994] for details). In particular, we rely later on the equivalences NPSPACE = PSPACE = coPSPACE.

The complexity results in this paper address cyclic CPnets. Most earlier work has concentrated on the acyclic model. However, we argue that acyclic CP-nets are not suf�ciently expressive to capture human preferences on even some simple domains. Consider, for instance, a diner who has to choose either red or white wine, and either �sh or meat. Given red wine, they prefer meat, and conversely, given meat they prefer red wine. On the other hand, given white wine, they prefer �sh, and conversely, given �sh they prefer white wine. This gives a consistent cyclic CP-net, and there is no acyclic CP-net giving rise to the same preferences on outcomes. So, such cyclicity of preference variables does not necessarily lead to a cyclic order on outcomes.

2 Generalized propositional CP-nets

Let V = {x1, . . . , xn} be a �nite set of variables. For each variable x ∈ V , we assume a �nite domainDx of values. An

Nic Wilson

outcome is an n-tuple (d1, . . . , dn) of Dx1 × · · · ×Dxn .

A conditional preference rule (or, for short, a [preference] rule) over V is an expression p : l > ¬l, where l is a literal of some atom x ∈ V and p is a propositional formula over V that does not involve variable x.

In this paper, we focus on propositional variables: variables with binary domains. Let V be a �nite set of propositional variables. For every x ∈ V , we set Dx = {x, ¬x} (thus, we overload the notation and write x both for the variable and for one of its values). We refer to x and ¬x as literals. Given a literal l we write ¬l to denote the dual literal to l. The focus on binary variables makes the presentation clearer and has no impact on our complexity results.

Definition 1 (Generalized CP-net) A generalized CP-net C (for short, a GCP-net) over V is a set of conditional preference rules. For x ∈ V we define p+C (x) and p-C (x), usually written just: p+(x) and p-(x), as follows: p+C (x) is equal to the disjunction of all p such that there exists a rule p : x > ¬x in C; p-C (x) is the disjunction of all p such that there exists a rule p : ¬x > x in C. We define the associated directed graph GC (the dependency graph) over V to consist of all pairs (y, x) of variables such that y appears in either p+(x) or p-(x).

In our complexity results we will also need the following representation of GCP-nets: a GCP-net C is said to be in conjunctive form if C only contains rules p : l > ¬l such that p is a (possibly empty) conjunction of literals. In this case all formulas p-(x), p+(x) are in disjunctive normal form, that is, a disjunction of conjunctions of literals (including ⊤ � the empty conjunction of literals).

Finally, A GCP-net is consistent if there is no outcome α which is strictly preferred to itself, i.e., such that α ≺ α.

GCP-nets determine a transitive relation on outcomes, interpreted in terms of preference. A preference rule p : l > ¬l represents the statement �given that p holds, l is preferred to ¬l ceteris paribus�. Its intended meaning is as follows. If outcome β satis�es p and l, then β is preferred to the outcome α which differs from β only in that it assigns ¬l for variable x. In this situation we say that there is an improving flip from α to β sanctioned by the rule p : l > ¬l. If α0, . . . , αm is a sequence of outcomes with m ≥ 1 and each next outcome in the sequence is obtained from the previous one by an improving �ip, then we say that α0, . . . , αm is an improving sequence (from α0 to αm) for the GCP-net, and that αm dominates α0, written α0 ≺ αm.

The main objective of the paper is to establish the complexity of the following two problems concerning the notion of dominance associated with GCP-nets (sometimes under restrictions on the class of input GCP-nets).

Definition 2

GCP-CONSISTENCY: given a GCP-net C, decide whether C is consistent.

GCP-DOMINANCE: given a GCP-net C and two outcomes α and β, decide whether α ≺ β in C.

There are two properties of GCP-nets that are essential in linking them to the original notion of CP-nets [Boutilier et al., 1999; 2004a].

Definition 3

A GCP-net C over V is locally consistent if for every x ∈ V , the formula p-C (x) ∧ p+C (x) is unsatisfiable. It is locally complete if for every x ∈ V , the formula p-C (x) ∨ p+C (x) is a tautology.

Definition 4 (Propositional CP-net) A CP-net over the set V of (propositional) variables is a locally consistent and locally complete GCP-net over V .

Problems CP-DOMINANCE and CP-CONSISTENCY are de�ned analogously to De�nition 2.

When de�ning a decision problem, it is critical to specify the way to represent its input instances, as the representation may affect the complexity of the problem. Unless stated otherwise, we assume that GCP-nets (and so, also CP-nets) are represented as a set of preference rules, as described in De�- nition 1. Therefore, the size of a GCP-net is given by the total size of the formulas p-(x), p+(x), x ∈ V .

This de�nition of a CP-net differs from the one given in [Boutilier et al., 2004a], which uses explicit conditional preference tables. Our representation is often more compact, but it is easy to verify that it is equivalent in that it gives rise to the same de�nition of dominance.

3 Propositional STRIPS planning

In this section we derive some technical results on propositional STRIPS planning which form the basis of our complexity results in Sections 4 and 5. We establish the complexity of plan existence problems for propositional STRIPS planning, under restrictions on input instances that make the problem useful in the studies of dominance and consistency in GCPnets.

Let V be a �nite set of variables. A state over V is a complete and consistent set of literals over V (which we often view as the conjunction of its members). A state is therefore equivalent to an outcome, de�ned in a CP-nets context.

Definition 5 (Propositional STRIPS planning) A propositional STRIPS instance is a tuple 〈V, α0, γ, ACT〉, where

1. V is a finite set of propositional variables;
2. α0 is a state (over V ), called the initial state;
3. γ is a state called the goal;
4. ACT is a finite set of actions, where each action a ∈ ACT is described by a consistent conjunction of literals pre(a) (a precondition) and a consistent conjunction of literals post(a) (a postcondition, or effect).

An action a is executable in a state α if α |= pre(a). The effect of a in state α is the state α′ containing the same literals as α for all variables not mentioned in post(a), and the literals of post (a) otherwise. We assume that an action can be applied to any state, but that it has no effect if its preconditions do not hold (this assumption has no effect on complexity).

The PROPOSITIONAL STRIPS PLAN EXISTENCE problem, or STRIPS PLAN for short, is to decide whether for a given propositional STRIPS instance 〈V, α0, γ,ACT〉 there is a successful plan, that is, sequence of actions leading from the initial state α0 to a state satisfying the goal γ.

A plan is irreducible if its every action changes the state.

We assume, without loss of generality, that for any action a, no literal in post(a) also appears in pre(a); otherwise we can omit the literal from post(a) without changing the effect of the action; (if post(a) then becomes an empty conjunction, the action a can be omitted from ACT as it has no effect).

We have the following result, proved in [Bylander, 1994] :

Proposition 1 ([Bylander, 1994]) STRIPS PLAN is PSPACE-complete.

Typically, propositional STRIPS instances do not require that goals be complete. We restrict consideration to complete goals. This restriction has no effect on the complexity: the plan existence problem remains PSPACE-complete under the goal-completeness restriction [Lang, 2004].

3.1 Acyclic STRIPS

Definition 6 (Acyclic sets of actions) A set of actions ACT is acyclic if there is no state α such that 〈V, α, α,ACT〉 has a non-empty irreducible plan (informally, if there are no nontrivial directed cycles in the space of states induced by ACT ).

We will now consider the following two problems:

1. ACYCLIC STRIPS PLAN: given a propositional STRIPS instance 〈V, α0, γ,ACT〉 such that ACT is acyclic and α0 ̸= γ, decide whether there is a plan for 〈V, α0, γ, ACT 〉.
2. ACTION-SET ACYCLICITY: given a set ACT of actions, decide whether ACT is acyclic.

We will show that both problems are PSPACE-complete.

Proposition 2

ACYCLIC STRIPS PLAN is PSPACE-complete.

Proof: Membership in PSPACE is evident as the problem is a restriction of STRIPS PLAN. To prove PSPACE-hardness, we exhibit a polynomial-time reduction from STRIPS PLAN. Let PE = 〈V, α0, γ,ACT〉 be an instance of STRIPS PLAN. The idea behind the reduction is to introduce a counter, so that each time an action is executed, the counter is incremented. The counter may count up to 2n, where n = |V |, making use of n additional variables. The counter is initialized to 0. Once it reaches 2n - 1 it can no longer be incremented and no action can be executed. Hence, the set of actions in the resulting instance of STRIPS PLAN is acyclic.

To describe the reduction, we write V as {x1, . . . , xn}. We de�ne PE′ = 〈V ′ , α′0 , γ ′ , ACT ′ 〉 as follows:

• V ′ = {x1, . . . , xn, z1, . . . , zn}, where zi are new variables we will use to implement the counter;
• α′0 = α0 ∧ ¬z1 ∧ · · · ∧ ¬zn;
• γ ′ = γ ∧ z1 ∧ · · · ∧ zn;
• for each action a ∈ ACT , we include in ACT ′ n actions ai , 1 ≤ i ≤ n, such that pre(ai ) = pre(a) ∧ ¬zi ∧ zi+1 ∧ · · · ∧ zn post (ai ) = post (a) ∧ zi ∧ ¬zi+1 ∧ · · · ∧ ¬zn
• Furthermore, we include in ACT ′ n actions bi, 1 ≤ i ≤ n, such that pre(bi) = ¬zi ∧ zi+1 ∧ · · · ∧ zn post (bi) = zi ∧ ¬zi+1 ∧ · · · ∧ ¬zn

We will denote states over V ′ by pairs (α, k), where α is a state over V and k is an integer, 0 ≤ k ≤ 2n - 1. We view k as a compact representation of a state over variables z1, . . . , zn: assuming that the binary representation of k is d1 . . . dn (with dn being the least signi�cant digit), k represents the state which contains zi if di = 1 and ¬zi, otherwise.

We claim that there is a plan for PE if and only if there is a plan for PE′ . First, assume that there is a plan in PE. Let π be a shortest plan in PE and let m be its length. We have m ≤ 2n -1, since no state along π repeats (otherwise, shorter plans than π for PE would exist). Let α0, α1, . . . , αm = γ be the sequence of states obtained by executing π. Let a be the action used in the transition from αk to αk+1. Since k < 2n - 1, there is exactly one i, 1 ≤ i ≤ n, such that the action ai applies at the state (α, k) over V ′ . Replacing a with ai in π yields a plan that when started at (α0, 0) leads to (αm,m) = (γ,m). Appending that plan with appropriate actions bi to increment the counter to 2n -1 yields a plan for PE′ . Conversely, if τ is a plan for PE′ , the plan obtained from τ by removing all actions of the form bj and replacing each action ai with a is a plan for PE.

PE′ is acyclic, since executing any action in ACT ′ increments the counter k and no action can be executed once the counter has reached the value 2n - 1.

Thus, the claim and the assertion follow.

Proposition 3

ACTION-SET ACYCLICITY is PSPACE-complete.

Proof: The argument for the membership in PSPACE is standard. To prove PSPACE-hardness, we proceed as follows. Let PE = 〈V, α0, γ,ACT〉 be a STRIPS instance such that ACT is acyclic and α0 ̸= γ. Let a be a new action de�ned by pre(a) = γ and post(a) = α0. It is easy to see that ACT ∪ {a} is not acyclic if and only if there exists a plan for PE. Thus, the PSPACE-hardness of the complement of the ACTION-SET ACYCLICITY problem follows from Proposition 2. Since PSPACE = coPSPACE, this suf�ces to prove the hardness part of the assertion. ■

3.2 Mapping STRIPS plans to single-effect STRIPS plans

Versions of the STRIPS PLAN and ACYCLIC STRIPS PLAN problems that are important for us allow only single-effect actions (actions with exactly one literal in their postconditions) in input propositional STRIPS instances. We refer to these restrictions as SE STRIPS PLAN and ACYCLIC SE STRIPS PLAN.

Consider an instance PE = 〈V, α0, γ, ACT〉 of the STRIPS PLAN problem (where ACT is not necessarily acyclic). For each action a ∈ ACT we introduce a new variable xa. We set X = ∧a∈ACT ¬xa. That is, X is the conjunction of negative literals of all the additional variables. In addition, for each a ∈ ACT we set Xa = xa ∧ ∧b∈ACT-{a} ¬xb. We now de�ne an instance PE′ = 〈V ′ , α′0, γ ′ , S(ACT)〉 of the SE STRIPS PLAN problem as follows:

To prove PSPACE-hardness of both problems, we describe a mapping from STRIPS instances to single-effect STRIPS instances.

■

• Set of variables: V ′ = V ∪ {xa : a ∈ ACT};
• Initial state: α′0 = α0 ∧X;
• Goal state: γ ′ = γ ∧X;
• Set of actions: S(ACT) = {ai : a ∈ ACT, i =
• 1, . . . , 2|post(a)| + 1}. Let a ∈ ACT and post(a) = l1 ∧ · · · ∧ lq. For i = 1, . . . , q, we de�ne: pre(ai ) = pre(a) ∧X ∧¬li; post(ai ) = xa; pre(aq+i ) =Xa; post(aq+i ) = li. We also de�ne: pre(a2q+1 ) =Xa ∧ l1 ∧ · · · ∧ lq; post(a2q+1 ) = ¬xa.

Let π be a sequence of actions in ACT . We de�ne S(π) to be the sequence of actions in S(ACT) obtained by replacing each action a in π by a1 , . . . , a2q+1 (where q = |post(a)|). Now consider a sequence τ of actions from S(ACT). Remove from τ any action ai such that i ̸= 2|post(a)| + 1, and replace actions of the form a2|post(a)|+1 by a. We denote the resulting sequence of actions from ACT by S ′ (τ). The following properties are easy to check (details are omitted):

Lemma 1 With the above definitions,

• (i) if π is a plan for PE then S(π) is a plan for PE′ ;
• (ii) if τ is an irreducible plan for PE′ then S ′ (τ) is a plan for PE;
• (iii) ACT is acyclic if and only if S(ACT) is acyclic.

Proposition 4

SE STRIPS PLAN and ACYCLIC SE STRIPS PLAN are PSPACE-complete.

Proof: SE STRIPS PLAN and ACYCLIC SE STRIPS PLAN problems are restrictions of STRIPS PLAN, from which membership in PSPACE follows. PSPACE-hardness of ACYCLIC SE STRIPS PLAN (and so, also of the other problem) is shown by reduction from ACYCLIC STRIPS PLAN. Consider an instance PE = 〈V, α0, γ,ACT〉 of ACYCLIC STRIPS PLAN. De�ne PE′ = 〈V ′ , α′0 , γ ′ , S(ACT)〉, which by Lemma 1(iii) is an instance of the ACYCLIC SE STRIPS PLAN problem. By Lemma 1(i) and (ii) there exists a plan for PE if and only if there exists a plan for PE′ . ■

4 Dominance

The goal of this section is to prove that the GCP-DOMINANCE problem is PSPACE-complete, and that the complexity does not go down even when we restrict the class of inputs to CPnets. We use the results on propositional STRIPS planning from Section 3 to prove that the general GCP-DOMINANCE problem is PSPACE-complete. We then show that the complexity does not change if we impose the requirements of local consistency and local completeness on input GCP-nets.

The similarities between dominance testing in CP-nets and propositional STRIPS planning were �rst noted in [Boutilier et al., 1999], where a reduction (presented in more detail in [Boutilier et al., 2004a]) was given from the dominance problem to the plan existence problem for a class of propositional STRIPS planning speci�cations consisting of unary actions (actions with single effects). We prove our results for the GCP-DOMINANCE and GCP-CONSISTENCY problems by constructing a reduction in the other direction.

For all dominance and consistency problems considered in the paper, the membership in PSPACE can be demonstrated by considering nondeterministic algorithms consisting of repeatedly guessing appropriate improving �ips. Such algorithms work in polynomial space and show the membership of problems they solve in NPSPACE and consequently in PSPACE, since NPSPACE = PSPACE. Therefore, due to space restrictions, from now on we only provide arguments for the PSPACE-hardness of problems we consider.

This reduction is much more complex than the one used in [Boutilier et al., 1999], due to the fact that CP-nets impose more restrictions than STRIPS planning. Firstly, STRIPS planning allows multiple effects, but GCP-nets only allow �ips x > ¬x or ¬x > x that change the value of one variable; this is why we constructed the reduction from STRIPS planning to single-effect STRIPS planning in the last section. Secondly, CP-nets impose two more restrictions, local consistency and local completeness, which do not have natural counterparts in the context of STRIPS planning.

4.1 Dominance for generalized CP-nets

We will prove that the GCP-DOMINANCE problem is PSPACE-complete by a reduction from the problem SE STRIPS PLAN, which we now know to be PSPACE-complete.

Mapping single-effect STRIPS problems to GCP-nets dominance problems

Let 〈V, α0, γ,ACT〉 be an instance of the SE STRIPS PLAN problem. For every action a ∈ ACT we denote by la the unique literal in the postcondition of a, that is, post(a) = la. We denote by pre′ (a) the conjunction of all literals in pre(a) different from¬la (we recall that by a conventionwe adopted earlier, pre′ (a) does not contain la either). We then de�ne ca to be the conditional preference rule pre′ (a) : la > ¬la and de�ne M(ACT) to be the GCP-net C = {ca: a ∈ ACT}.

A sequence of states in a plan corresponds to an improving sequence from α0 to γ, which leads to the following result.

Lemma 2 With the above notation,

• (i) there is a non-empty irreducible plan for 〈V, α0, γ,ACT〉 if and only if γ dominates α0 in C;
• (ii) ACT is acyclic if and only if M(ACT) is consistent.

Theorem 1 The GCP-DOMINANCE problem is PSPACEcomplete. Moreover, this remains so under the restrictions that the GCP-net is consistent and is in conjunctive form.

Proof: PSPACE-hardness is shown by reduction from ACYCLIC SE STRIPS PLAN (Proposition 4). Let 〈V, α0, γ,ACT〉 be an instance of the ACYCLIC SE STRIPS PLAN problem. By Lemma 2(ii), M(ACT) is a consistent GCP-net in conjunctive form. Since α0 ̸= γ, there is a plan for 〈V, α0, γ,ACT〉 if and only if there is a non-empty irreducible plan for 〈V, α0, γ, ACT〉, which, by Lemma 2(i), is if and only if γ dominates α0 in C. ■

4.2 Dominance in CP-nets

In this section we show that GCP-DOMINANCE remains PSPACE-complete under the restriction to locally-consistent and locally-complete GCP-nets, i.e., CP-nets. We refer to this restriction of GCP-DOMINANCE as CP-DOMINANCE.

We will show PSPACE-hardness for CP-DOMINANCE by a reduction from GCP-DOMINANCE for consistent GCP-nets.

Mapping locally-consistent GCP-nets to CP-nets

Let C be a locally-consistent GCP-net. Let V = {x1, . . . , xn} be the set of variables of C. We de�ne V ′ = V ∪ {y1, . . . , yn}, where {y1, . . . , yn} ∩ V = ∅. We de�ne a GCP-net C ′ over V ′ , which we will show is a CP-net. To this end, for every z ∈ V ′ we will de�ne conditional preference rules q+(z) : z > ¬z and q-(z) : ¬z > z to be included in C ′ by specifying formulas q+(z) and q-(z).

First, for each variable xi ∈ V , we set

Thus, xi depends only on yi. We also note that the formulas q+(xi) and q-(xi) satisfy local-consistency and localcompleteness requirements.

Next, for each variable yi, 1 ≤ i ≤ n, we de�ne

Finally, we de�ne

and

Thus, yi depends on every variable in V ′ but itself.

Let α and β be outcomes over {x1, . . . , xn} and {y1, . . . , yn}, respectively. By αβ we denote the outcome over V ′ obtained by concatenating n-tuples α and β. Conversely, every outcome for C ′ can be written in this way.

We note that by the local consistency of C, formulas f + i ∧ f - i , 1 ≤ i ≤ n, are unsatis�able. Consequently, formulas q+(yi) ∧ q-(yi), 1 ≤ i ≤ n, are unsatis�able. Thus, C ′ is locally consistent. Finally, q+(yi) ∨ q-(yi) is equivalent to f + i ∨ ¬xi ∨ f - i ∨ xi, so is a tautology. Thus, C ′ is locally complete and hence a CP-net over V ′ .

Let α be an outcome over V . We de�ne ¯α to be the outcome over {y1, . . . , yn} obtained by replacing in α every component of the form xi with yi and every component ¬xi with ¬yi. Then for every i, 1 ≤ i ≤ n, α¯α |= ei.

Let s be a sequence α0, . . . , αm of outcomes over V . De�ne L(s) to be the sequence of V ′ -outcomes: α0α0, α0α1, α1α1, α1α2, . . . , αmαm. Further, let t be a sequence ϵ0, ϵ1, . . . , ϵm of V ′ -outcomes with ϵ0 = α¯α and ϵm = β ¯ β. De�ne L′(t) to be the sequence obtained from t by projecting each element in t to V and iteratively removing elements in the sequence which are the same as their predecessor (until any two consecutive outcomes are different).

Lemma 3 With the above definitions,

• (i) if s is an improving sequence for C from α to β then L(s) is an improving sequence for C ′ from α¯α to β ¯ β;
• (ii) if t is an improving sequence from α¯α to β ¯ β then L′(t) is an improving sequence from α to β;
• (iii) C is consistent if and only if C ′ is consistent

Sketch of proof: Let e = ∧ni=1 (xi ↔ yi). The de�nitions have been arranged to ensure the following for CP-net C ′ :

• (a) Suppose e holds in an outcome, so the outcome can be written as α¯α for some α; then no improving �ip changes any variable xi; furthermore, there is an improving �ip changing variable yi if and only if there is an improving �ip for the GCP-net C from outcome α changing variable xi. After applying this �ip changing variable yi, there is exactly one improving �ip possible, changing xi, after which e holds again (this follows using (b), as yi cannot be immediately �ipped back again, because C ′ is locally consistent).
• (b) If e does not hold in an outcome then the only improving �ips possible change the value of some variable (xi or yi) to make xi ↔ yi hold for some i.

(a) implies (i) and (ii). Also, (i) implies half of (iii), that if C is inconsistent then C ′ is inconsistent. Conversely, suppose that C ′ is inconsistent, so there exists an improving sequence t for C ′ from some outcome to itself. By (b), any improving �ip applied to an outcome in which e does not hold increases (by one) the number of i such that xi ↔ yi holds. This implies that e must hold in some outcome in t, because t is cyclic. Write this outcome as α¯α. We can cyclically permute t to form an improving sequence from α¯α to itself. Part (ii) then implies that there exists an improving �ipping sequence for C from α to itself, showing that C is inconsistent. ■

Theorem 2 CP-DOMINANCE is PSPACE-complete. This holds even if we restrict the CP-nets to being consistent.

Proof: We use a reduction from PSPACE-hardness of the GCP-DOMINANCE problem when the GCP-nets are restricted to being consistent (Theorem 1). Let C be a consistent (and hence locally consistent) GCP-net over V , and let α and β be outcomes over V . Consider the CP-net C ′ over variables V ′ constructed above. Lemma 3(i) and (ii) imply that β dominates α in C if and only if β ¯ β dominates α¯α in C ′ . Moreover, C ′ is consistent by Lemma 3(iii). Thus, the hardness part of the assertion follows. ■

5 Consistency of GCP-nets

In this section we show that the GCP-CONSISTENCY problem is PSPACE-complete, using results from Sections 3 and 4.

Theorem 3

GCP-CONSISTENCY is PSPACE-complete. This holds even under the restriction to GCP-nets in conjunctive form.

Proof: PSPACE-hardness is shown by reduction from ACTION-SET ACYCLICITY. We apply function S from Section 3.2 followed by M from Section 4.1. This maps instances of ACTION-SET ACYCLICITY to instances of GCP-CONSISTENCY in conjunctive form. By Lemma 1(iii) and Lemma 2 (ii), an instance of ACTION-SET ACYCLICITY is acyclic if and only if the corresponding instance of GCP-CONSISTENCY is consistent, proving the result. ■

We now show that consistency testing remains PSPACEcomplete for CP-nets.

Theorem 4 CP-CONSISTENCY is PSPACE-complete.

Proof: Let C be a GCP-net in conjunctive form. We de�ne a CP-net C ′ as follows. If C is locally inconsistent (the property can be decided in polynomial time), we set C ′ to be any �xed (independent of C) inconsistent but locally consistent CP-net. (Such CP-nets exist.) Otherwise, C is locally-consistent and for C ′ we take the CP-net we constructed in Section 4.2. The mapping from locally consistent GCP-nets to CP-nets, described in Section 4.2, preserves consistency (Lemma 3 (iii)). Since local inconsistency implies inconsistency, we have that the GCP-net C is consistent if and only if the CP-net C ′ is consistent. Thus, PSPACE-hardness of the CP-CONSISTENCY problem follows from Theorem 3. ■

Notice the huge complexity gap with the problem of deciding whether there exists a nondominated outcome, which is �only� NP-complete [Domshlak et al., 2003].

6 Concluding remarks

We have shown that dominance and consistency testing in CP-nets is PSPACE-complete. The repeated use of reductions from planning problems con�rms the importance of the structural similarity between STRIPS planning and reasoning with CP-nets. This suggests that the well-developed �eld of planning algorithms for STRIPS representations, especially for unary operators [Brafman and Domshlak, 2003], could be useful for implementing algorithms for dominance and consistency in CP-nets.

The complexity result for dominance is also relevant for constrained optimisation, where a complete algorithm [Boutilier et al., 2004b] involves many dominance checks. Our results reinforce the need for work on �nding special classes of problems where dominance and consistency can be tested ef�ciently [Domshlak and Brafman, 2002; Boutilier et al., 2004a], and for incomplete methods for checking consistency and constrained optimisation [Wilson, 2004a].

Our theorems extend to CP-nets with non-binary domains, and to extensions and variations of CP-nets, such as TCPnets [Brafman and Domshlak, 2002] that allows for explicit priority of some variables over others, and the more general preference language described in [Wilson, 2004b; 2004a].

Several open problems remain. We do not know whether dominance and consistency testing remain PSPACEcomplete when the number of parents in the dependency graph is bounded by a constant. We also do not know whether these two problems remain PSPACE-complete for CP-nets in conjunctive form (the reduction used to prove Theorems 2 and 4 yields CP-nets that are not in conjunctive form). Finally, we do not know the complexity of deciding whether the preference relation induced by a CP-net is complete.

Acknowledgements

We are grateful for a reviewer's simple example of a cyclic CP-net. This material is supported in part by the NSF under Grants No. IIS-0325063 and IIS-0097278, by Science Foundation Ireland under Grant No. 00/PI.1/C075, and by the CNRS program RTP 11: �raisonner et d·ecider�.