The computational complexity of dominance and consistency in CP-nets ´^ ´ Judy Goldsmith Jerome Lang Miroslaw Truszczynski Nic Wilson Dept. of Comp. Sci. IRIT Dept. of Comp. Sci. Cork Constraint University of Kentucky Universite Paul Sabatier ´ University of Kentucky Computation Centre Lexington, KY 31062 Toulouse Cedex Lexington, KY University College Cork 40506-0046, USA France 40506-0046, USA Ireland goldsmit@cs.uky.edu lang@irit.fr mirek@cs.uky.edu n.wilson@4c.ucc.ie We study the computational complexity of these two prob- Abstract lems. The results obtained so far concerned only restricted We investigate the computational complexity of classes of CP-nets, all requiring that the graph of variable de- testing dominance and consistency in CP-nets. Up pendencies implied by preference statements in the CP-net be until now, the complexity of dominance has been acyclic. Under certain assumptions, the dominance-testing determined only for restricted classes in which the problem is in NP and, under some additional assumptions, dependency graph of the CP-net is acyclic. How- even in P [Domshlak and Brafman, 2002; Boutilier et al., ever, there are preferences of interest that define 2004a]. Its complexity in the general case has remained until cyclic dependency graphs; these are modeled with now an open problem. We show that it is in fact PSPACE- general CP-nets. We show here that both domi- complete, even for the propositional case, by exhibiting in nance and consistency testing for general CP-nets Section 4 a PSPACE-hardness proof for dominance testing. are PSPACE-complete. The reductions used in the We then turn to consistency testing. While acyclic CP- proofs are from STRIPS planning, and thus estab- nets are guaranteed to be consistent, this is not the case lish strong connections between both areas. 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 1 Introduction is as hard as dominance testing. The problems of eliciting, representing and reasoning with To prove the hardness part of the results, we first establish preferences over a multivariable (or, multiattribute) domain the PSPACE-hardness of some problems related to proposi- arise in many fields such as planning, design, and group de- tional STRIPS planning. We then show that these problems cision making. An explicit representation of a preference or- can be reduced to CP-net dominance and consistency testing dering of elements (we refer to them as outcomes) of such by exploiting connections between actions in STRIPS plan- multivariable domains is exponentially large in the number ning and preference statements in CP-nets. of attributes. Therefore, AI researchers have developed lan- We assume some familiarity with the complexity class guages for representing preference orderings succinctly. The PSPACE (we refer to [Papadimitriou, 1994] for details). In formalism of CP-nets [Boutilier et al., 1999] is among the particular, we rely later on the equivalences NPSPACE = most popular ones. A CP-net provides a succinct represen- PSPACE = coPSPACE. tation of preference ordering on outcomes in terms of local The complexity results in this paper address cyclic CP- preference statements of the form p : xi > xj , where xi , xj nets. Most earlier work has concentrated on the acyclic are values of a variable X and p is a logical condition. Infor- model. However, we argue that acyclic CP-nets are not suf- mally, a preference statement p : xi > xj means that given ficiently expressive to capture human preferences on even p, xi is (strictly) preferred to xj ceteris paribus, that is, all some simple domains. Consider, for instance, a diner who other things being equal. The meaning of a CP-net is given has to choose either red or white wine, and either fish or meat. by a certain ordering relation (dominance) on the set of out- Given red wine, they prefer meat, and conversely, given meat comes, derived from such reading of preference statements. they prefer red wine. On the other hand, given white wine, If one outcome dominates another, we say that the dominant they prefer fish, and conversely, given fish they prefer white one is preferred. wine. This gives a consistent cyclic CP-net, and there is no Reasoning about the preference ordering (dominance rela- acyclic CP-net giving rise to the same preferences on out- tion) expressed by a CP-net is far from easy. The key prob- comes. So, such cyclicity of preference variables does not lems include dominance testing and consistency testing. In necessarily lead to a cyclic order on outcomes. the first problem, given a CP-net and two outcomes and , we want to decide whether dominates . The second prob- 2 Generalized propositional CP-nets lem asks whether there is a dominance cycle in the dominance Let V = {x1 , . . . , xn } be a finite set of variables. For each ordering defined by an input CP-net, that is, whether there is variable x V , we assume a finite domain Dx of values. An an outcome that dominates (is preferred to) itself. outcome is an n-tuple (d1 , . . . , dn ) of Dx1 × · · · × Dxn . Definition 3 A GCP-net C over V is locally consistent if for every x In this paper, we focus on propositional variables: vari- V , the formula p- (x) p+ (x) is unsatisfiable. It is locally ables with binary domains. Let V be a finite set of propo- C C sitional variables. For every x V , we set Dx = {x, ¬x} complete if for every x V , the formula p- (x) p+ (x) is a C C (thus, we overload the notation and write x both for the vari- tautology. able and for one of its values). We refer to x and ¬x as liter- Definition 4 (Propositional CP-net) A CP-net over the set als. Given a literal l we write ¬l to denote the dual literal to l. V of (propositional) variables is a locally consistent and lo- The focus on binary variables makes the presentation clearer cally complete GCP-net over V . and has no impact on our complexity results. Problems C P - D O M I NA N C E and C P - C O N S I S T E N C Y are de- A conditional preference rule (or, for short, a [preference] fined analogously to Definition 2. rule) over V is an expression p : l > ¬l, where l is a literal This definition of a CP-net differs from the one given in of some atom x V and p is a propositional formula over V [Boutilier et al., 2004a], which uses explicit conditional pref- that does not involve variable x. erence tables. Our representation is often more compact, but Definition 1 (Generalized CP-net) A generalized CP-net C it is easy to verify that it is equivalent in that it gives rise to (for short, a GCP-net) over V is a set of conditional prefer- the same definition of dominance. ence rules. For x V we define p+ (x) and p- (x), usually When defining a decision problem, it is critical to specify C C written just: p+ (x) and p- (x), as follows: p+ (x) is equal to the way to represent its input instances, as the representation C may affect the complexity of the problem. Unless stated oth- the disjunction of all p such that there exists a rule p : x > ¬x in C ; p- (x) is the disjunction of all p such that there exists erwise, we assume that GCP-nets (and so, also CP-nets) are C represented as a set of preference rules, as described in Defi- a rule p : ¬x > x in C . We define the associated directed graph GC (the dependency graph) over V to consist of all nition 1. Therefore, the size of a GCP-net is given by the total size of the formulas p- (x), p+ (x), x V . 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 3 Propositional STRIPS planning representation of GCP-nets: a GCP-net C is said to be in con- In this section we derive some technical results on proposi- junctive form if C only contains rules p : l > ¬l such that p tional STRIPS planning which form the basis of our complex- is a (possibly empty) conjunction of literals. In this case all ity results in Sections 4 and 5. We establish the complexity of formulas p- (x), p+ (x) are in disjunctive normal form, that plan existence problems for propositional STRIPS planning, is, a disjunction of conjunctions of literals (including ­ the under restrictions on input instances that make the problem empty conjunction of literals). useful in the studies of dominance and consistency in GCP- GCP-nets determine a transitive relation on outcomes, in- nets. terpreted in terms of preference. A preference rule p : l > ¬l Let V be a finite set of variables. A state over V is a com- represents the statement "given that p holds, l is preferred to plete and consistent set of literals over V (which we often ¬l ceteris paribus". Its intended meaning is as follows. If view as the conjunction of its members). A state is therefore outcome satisfies p and l, then is preferred to the out- equivalent to an outcome, defined in a CP-nets context. come which differs from only in that it assigns ¬l for Definition 5 (Propositional STRIPS planning) A proposi- variable x. In this situation we say that there is an improv- tional STRIPS instance is a tuple V, 0 , , ACT , where ing flip from to sanctioned by the rule p : l > ¬l. If 0 , . . . , m is a sequence of outcomes with m 1 and each 1. V is a finite set of propositional variables; next outcome in the sequence is obtained from the previous 2. 0 is a state (over V ), called the initial state; one by an improving flip, then we say that 0 , . . . , m is an 3. is a state called the goal; improving sequence (from 0 to m ) for the GCP-net, and 4. ACT is a finite set of actions, where each action a that m dominates 0 , written 0 m . Finally, A GCP-net is consistent if there is no outcome ACT is described by a consistent conjunction of literals pre(a) (a precondition) and a consistent conjunction of which is strictly preferred to itself, i.e., such that . literals post (a) (a postcondition, or effect). The main objective of the paper is to establish the com- An action a is executable in a state if |= pre(a). The ef- plexity of the following two problems concerning the notion fect of a in state is the state containing the same literals of dominance associated with GCP-nets (sometimes under re- strictions on the class of input GCP-nets). as for all variables not mentioned in post (a), and the liter- als of post (a) otherwise. We assume that an action can be ap- Definition 2 plied to any state, but that it has no effect if its preconditions G C P - D O M I N A N C E : given a GCP-net C and two outcomes do not hold (this assumption has no effect on complexity). and , decide whether in C . The P RO P O S I T I O NA L S T R I P S P L A N E X I S T E N C E problem, or G C P - C O N S I S T E N C Y : given a GCP-net C , decide whether C S T R I P S P L A N for short, is to decide whether for a given is consistent. propositional STRIPS instance V, 0 , , ACT there is a There are two properties of GCP-nets that are essential in successful plan, that is, sequence of actions leading from the linking them to the original notion of CP-nets [Boutilier et initial state 0 to a state satisfying the goal . al., 1999; 2004a]. A plan is irreducible if its every action changes the state. We will denote states over V by pairs (, k ), where is We assume, without loss of generality, that for any action a, a state over V and k is an integer, 0 k 2n - 1. We no literal in post (a) also appears in pre(a); otherwise we can view k as a compact representation of a state over variables omit the literal from post (a) without changing the effect of z1 , . . . , zn : assuming that the binary representation of k is the action; (if post (a) then becomes an empty conjunction, d1 . . . dn (with dn being the least significant digit), k repre- the action a can be omitted from ACT as it has no effect). We have the following result, proved in [Bylander, 1994] : sents the state which contains zi if di = 1 and ¬zi , otherwise. PE is acyclic, since executing any action in ACT incre- Proposition 1 ([Bylander, 1994]) ments the counter k and no action can be executed once the S T R I P S P L A N is PSPACE-complete. counter has reached the value 2n - 1. Typically, propositional STRIPS instances do not require We claim that there is a plan for PE if and only if there is that goals be complete. We restrict consideration to com- a plan for PE . First, assume that there is a plan in PE. Let plete goals. This restriction has no effect on the complex- be a shortest plan in PE and let m be its length. We have ity: the plan existence problem remains PSPACE-complete m 2n - 1, since no state along repeats (otherwise, shorter under the goal-completeness restriction [Lang, 2004]. 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 3.1 Acyclic STRIPS k < 2n - 1, there is exactly one i, 1 i n, such that Definition 6 (Acyclic sets of actions) A set of actions ACT is acyclic if there is no state such that V, , , ACT has 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 a non-empty irreducible plan (informally, if there are no non- to (m , m) = ( , m). Appending that plan with appropriate trivial directed cycles in the space of states induced by ACT ). actions bi to increment the counter to 2n - 1 yields a plan for We will now consider the following two problems: PE . Conversely, if is a plan for PE , the plan obtained from 1. AC Y C L I C S T R I P S P L A N: given a propositional STRIPS by removing all actions of the form bj and replacing each instance V, 0 , , ACT such that ACT is acyclic action ai with a is a plan for PE. and 0 = , decide whether there is a plan for P Thus, the claim and the assertion follow. V, 0 , , ACT . 2.AC T I O N - S E T AC Y C L I C I T Y : given a set ACT of actions, roposition 3 decide whether ACT is acyclic. AC T I O N - S E T AC Y C L I C I T Y is PSPACE-complete. We will show that both problems are PSPACE-complete. Proof: The argument for the membership in PSPACE is standard. To prove PSPACE-hardness, we proceed as Proposition 2 follows. Let PE = V, 0 , , ACT be a STRIPS instance AC Y C L I C S T R I P S P L A N is PSPACE-complete. such that ACT is acyclic and 0 = . Let a be a new action Proof: Membership in PSPACE is evident as the problem is a defined by pre(a) = and post (a) = 0 . It is easy to see restriction of S T R I P S P L A N. To prove PSPACE-hardness, we that ACT {a} is not acyclic if and only if there exists a exhibit a polynomial-time reduction from S T R I P S P L A N. Let plan for PE. Thus, the PSPACE-hardness of the complement PE = V, 0 , , ACT be an instance of S T R I P S P L A N. The of the AC T I O N - S E T AC Y C L I C I T Y problem follows from idea behind the reduction is to introduce a counter, so that Proposition 2. Since PSPACE = coPSPACE, this suffices each time an action is executed, the counter is incremented. to prove the hardness part of the assertion. 3 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 .2 Mapping STRIPS plans to single-effect no action can be executed. Hence, the set of actions in the STRIPS plans resulting instance of S T R I P S P L A N is acyclic. Versions of the S T R I P S P L A N and AC Y C L I C S T R I P S P L A N To describe the reduction, we write V as {x1 , . . . , xn }. We problems that are important for us allow only single-effect ac- define PE = V , 0 , , ACT as follows: tions (actions with exactly one literal in their postconditions) · V = {x1 , . . . , xn , z1 , . . . , zn }, where zi are new vari- in input propositional S T R I P S instances. We refer to these re- ables we will use to implement the counter; strictions as S E S T R I P S P L A N and AC Y C L I C S E S T R I P S P L A N. To prove PSPACE-hardness of both problems, we de- · 0 = 0 ¬z1 · · · ¬zn ; scribe a mapping from S T R I P S instances to single-effect · = z 1 · · · zn ; S T R I P S instances. · for each action a ACT , we include in ACT n actions Consider an instance PE = V, 0 , , ACT of the S T R I P S ai , 1 i n, such that P L A N problem (where ACT is not necessarily acyclic). For each action a ACT we introduce a new variable xa . We pre(ai ) = pre(a) ¬zi zi+1 · · · zn a set X = ACT ¬xa . That is, X is the conjunction of post (ai ) = post (a) zi ¬zi+1 · · · ¬zn negative literals of all the additional vab iables. In addition, r · Furthermore, we include in ACT n actions bi , 1 i for each a ACT we set Xa = xa ACT -{a} ¬xb . We n, such that now define an instance PE = V , 0 , , S (ACT ) of the pre(bi ) = ¬zi zi+1 · · · zn S E S T R I P S P L A N problem as follows: post (bi ) = zi ¬zi+1 · · · ¬zn Set of variables: V = V {xa : a ACT }; the G C P - D O M I NA N C E and G C P - C O N S I S T E N C Y problems by · constructing a reduction in the other direction. Initial state: 0 = 0 X ; · This reduction is much more complex than the one used in Goal state: = X ; [Boutilier et al., 1999], due to the fact that CP-nets impose · Set of actions: S (ACT ) = {ai : a ACT , i = more restrictions than STRIPS planning. Firstly, STRIPS · 1, . . . , 2|post (a)| + 1}. planning allows multiple effects, but GCP-nets only allow Let a ACT and post (a) = l1 · · · lq . For flips x > ¬x or ¬x > x that change the value of one vari- i = 1, . . . , q , we define: able; this is why we constructed the reduction from STRIPS pre(ai ) = pre(a) X ¬li ; post (ai ) = xa ; planning to single-effect STRIPS planning in the last section. pre(aq+i ) = Xa ; post (aq+i ) = li . Secondly, CP-nets impose two more restrictions, local con- We also define: sistency and local completeness, which do not have natural pre(a2q+1 ) = Xa l1 · · · lq ; post (a2q+1 ) = ¬xa . counterparts in the context of STRIPS planning. For all dominance and consistency problems considered in Let be a sequence of actions in ACT . We define S ( ) to the paper, the membership in PSPACE can be demonstrated be the sequence of actions in S (ACT ) obtained by replacing by considering nondeterministic algorithms consisting of re- each action a in by a1 , . . . , a2q+1 (where q = |post (a)|). peatedly guessing appropriate improving flips. Such algo- Now consider a sequence of actions from S (ACT ). Re- rithms work in polynomial space and show the membership move from any action ai such that i = 2|post (a)| + 1, and of problems they solve in NPSPACE and consequently in replace actions of the form a2|post (a)|+1 by a. We denote the PSPACE, since NPSPACE = PSPACE. Therefore, due to resulting sequence of actions from ACT by S ( ). The fol- space restrictions, from now on we only provide arguments lowing properties are easy to check (details are omitted): for the PSPACE-hardness of problems we consider. Lemma 1 With the above definitions, (i) if is a plan for PE then S ( ) is a plan for PE ; 4.1 Dominance for generalized CP-nets We will prove that the G C P - D O M I NA N C E problem is (ii) if is an irreducible plan for PE then S ( ) is a plan PSPACE-complete by a reduction from the problem S E for PE; S T R I P S P L A N , which we now know to be PSPACE-complete. (iii) ACT is acyclic if and only if S (ACT ) is acyclic. Mapping single-effect STRIPS problems to GCP-nets Proposition 4 SE STRIPS PLAN AC Y C L I C S E S T R I P S P L A N dominance problems and are Let V, 0 , , ACT be an instance of the S E S T R I P S P L A N PSPACE-complete. problem. For every action a ACT we denote by la the Proof: S E S T R I P S P L A N and AC Y C L I C S E S T R I P S P L A N unique literal in the postcondition of a, that is, post (a) = la . problems are restrictions of S T R I P S P L A N, from which We denote by pre (a) the conjunction of all literals in pre(a) membership in PSPACE follows. PSPACE-hardness of different from ¬la (we recall that by a convention we adopted AC Y C L I C S E S T R I P S P L A N (and so, also of the other prob- earlier, pre (a) does not contain la either). We then define ca lem) is shown by reduction from AC Y C L I C S T R I P S P L A N. to be the conditional preference rule pre (a) : la > ¬la and Consider an instance PE = V, 0 , , ACT of AC Y C L I C define M (ACT ) to be the GCP-net C = {ca : a ACT }. S T R I P S P L A N . Define PE V , 0 , , S (ACT ) , which = A sequence of states in a plan corresponds to an improving by Lemma 1(iii) is an instance of the AC Y C L I C S E S T R I P S sequence from 0 to , which leads to the following result. P L A N problem. By Lemma 1(i) and (ii) there exists a plan 4 r PE if and only if there exists a plan for PE fo . 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 Dominance C; The goal of this section is to prove that the G C P - D O M I NA N C E problem is PSPACE-complete, and that the complexity does (ii) ACT is acyclic if and only if M (ACT ) is consistent. not go down even when we restrict the class of inputs to CP- Theorem 1 The G C P - D O M I NA N C E problem is PSPACE- nets. We use the results on propositional STRIPS planning complete. Moreover, this remains so under the restrictions from Section 3 to prove that the general G C P - D O M I NA N C E that the GCP-net is consistent and is in conjunctive form. problem is PSPACE-complete. We then show that the com- PSPACE-hardness is shown by reduction plexity does not change if we impose the requirements of lo- Proof: from AC Y C L I C S E S T R I P S P L A N (Proposition 4). Let cal consistency and local completeness on input GCP-nets. V, 0 , , ACT be an instance of the AC Y C L I C S E S T R I P S The similarities between dominance testing in CP-nets and propositional STRIPS planning were first noted in [Boutilier P L A N problem. By Lemma 2(ii), M (ACT ) is a consistent et al., 1999], where a reduction (presented in more detail GCP-net in conjunctive form. Since 0 = , there is a in [Boutilier et al., 2004a]) was given from the dominance 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), problem to the plan existence problem for a class of propo- is if and only if dominates 0 in C . sitional STRIPS planning specifications consisting of unary actions (actions with single effects). We prove our results for 4.2 Dominance in CP-nets (i) if s is an improving sequence for C from to then ¯ L(s) is an improving sequence for C from to ; ¯ In this section we show that G C P - D O M I NA N C E remains PSPACE-complete under the restriction to locally-consistent ¯ (ii) if t is an improving sequence from to then L (t) ¯ and locally-complete GCP-nets, i.e., CP-nets. We refer to this is an improving sequence from to ; restriction of G C P - D O M I NA N C E as C P - D O M I NA N C E. (iii) C is consistent if and only if C is consistent We will show PSPACE-hardness for C P - D O M I NA N C E by n Sketch of proof: Let e = i=1 (xi yi ). The definitions a reduction from G C P - D O M I NA N C E for consistent GCP-nets. have been arranged to ensure the following for CP-net C : Mapping locally-consistent GCP-nets to CP-nets (a) Suppose e holds in an outcome, so the outcome can Let C be a locally-consistent GCP-net. Let V = be written as for some ; then no improving flip ¯ {x1 , . . . , xn } be the set of variables of C . We define V = changes any variable xi ; furthermore, there is an im- V {y1 , . . . , yn }, where {y1 , . . . , yn } V = . We define a proving flip changing variable yi if and only if there is GCP-net C over V , which we will show is a CP-net. To this an improving flip for the GCP-net C from outcome end, for every z V we will define conditional preference changing variable xi . After applying this flip changing rules q + (z ) : z > ¬z and q - (z ) : ¬z > z to be included in variable yi , there is exactly one improving flip possible, C by specifying formulas q + (z ) and q - (z ). changing xi , after which e holds again (this follows us- First, for each variable xi V , we set ing (b), as yi cannot be immediately flipped back again, because C is locally consistent). q + (xi ) = yi and q - (xi ) = ¬yi . (b) If e does not hold in an outcome then the only improving Thus, xi depends only on yi . We also note that the for- flips possible change the value of some variable (xi or mulas q + (xi ) and q - (xi ) satisfy local-consistency and local- yi ) to make xi yi hold for some i. completeness requirements. (a) implies (i) and (ii). Also, (i) implies half of (iii), that Next, for each variable yi , 1 i n, we define if C is inconsistent then C is inconsistent. Conversely, suppose that C is inconsistent, so there exists an improving = (x1 y1 ) · · · (xi-1 yi-1 ) ei sequence t for C from some outcome to itself. By (b), any (xi+1 yi+1 ) · · · (xn yn ), improving flip applied to an outcome in which e does not hold increases (by one) the number of i such that xi yi fi+ = ei p+ (xi ) and fi- = ei p- (xi ). holds. This implies that e must hold in some outcome in Finally, we define t, because t is cyclic. Write this outcome as . We can ¯ cyclically permute t to form an improving sequence from q + (yi ) = fi+ (¬fi- xi ) ¯ to itself. Part (ii) then implies that there exists an improving and flipping sequence for C from to itself, showing that C is inconsistent. q - (yi ) = fi- (¬fi+ ¬xi ) T Thus, yi depends on every variable in V but itself. We note that by the local consistency of C , formulas fi+ heorem 2 C P - D O M I NA N C E is PSPACE-complete. This fi , 1 i n, are unsatisfiable. Consequently, formulas - holds even if we restrict the CP-nets to being consistent. q + (yi ) q - (yi ), 1 i n, are unsatisfiable. Thus, C is Proof: We use a reduction from PSPACE-hardness of the locally consistent. Finally, q + (yi ) q - (yi ) is equivalent to G C P - D O M I N A N C E problem when the GCP-nets are restricted fi+ ¬xi fi- xi , so is a tautology. Thus, C is locally to being consistent (Theorem 1). Let C be a consistent complete and hence a CP-net over V . (and hence locally consistent) GCP-net over V , and let Let and be outcomes over {x1 , . . . , xn } and and be outcomes over V . Consider the CP-net C over {y1 , . . . , yn }, respectively. By we denote the outcome variables V constructed above. Lemma 3(i) and (ii) imply over V obtained by concatenating n-tuples and . Con- that dominates in C if and only if dominates in ¯ ¯ versely, every outcome for C can be written in this way. C . Moreover, C is consistent by Lemma 3(iii). Thus, the Let be an outcome over V . We define to be the out- 5ardness part of the assertion follows. h ¯ come 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 . ¯ Consistency of GCP-nets Let s be a sequence 0 , . . . , m of outcomes over In this section we show that the G C P - C O N S I S T E N C Y problem V . Define L(s) to be the sequence of V -outcomes: is PSPACE-complete, using results from Sections 3 and 4. 0 0 , 0 1 , 1 1 , 1 2 , . . . , m m . Further, let t be a se- quence 0, 1, . . . , m of V -outcomes with 0 = and ¯ Theorem 3 m = . Define L (t) to be the sequence obtained from t ¯ G C P - C O N S I S T E N C Y is PSPACE-complete. This holds even by projecting each element in t to V and iteratively removing under the restriction to GCP-nets in conjunctive form. elements in the sequence which are the same as their prede- PSPACE-hardness is shown by reduction from Proof: cessor (until any two consecutive outcomes are different). AC T I O N - S E T AC Y C L I C I T Y . We apply function S from Section 3.2 followed by M from Section 4.1. This maps Lemma 3 With the above definitions, nally, we do not know the complexity of deciding whether the instances of AC T I O N - S E T AC Y C L I C I T Y to instances of preference relation induced by a CP-net is complete. G C P - C O N S I S T E N C Y in conjunctive form. By Lemma 1(iii) and Lemma 2 (ii), an instance of AC T I O N - S E T AC Y C L I C I T Y is acyclic if and only if the corresponding instance of Acknowledgements We are grateful for a reviewer's simple example of a cyclic G C P - C O N S I S T E N C Y is consistent, proving the result. W CP-net. This material is supported in part by the NSF un- der Grants No. IIS-0325063 and IIS-0097278, by Science e now show that consistency testing remains PSPACE- Foundation Ireland under Grant No. 00/PI.1/C075, and by complete for CP-nets. the CNRS program RTP 11: "raisonner et decider". ´ CP-CONSISTENCY is PSPACE-complete. Theorem 4 References Proof: Let C be a GCP-net in conjunctive form. We define [Boutilier et al., 1999] C. Boutilier, R. I. Brafman, H. H. a CP-net C as follows. If C is locally inconsistent (the property can be decided in polynomial time), we set C to Hoos, and D. Poole. Reasoning with conditional ceteris be any fixed (independent of C ) inconsistent but locally paribus preference statements. In Proceedings of UAI99, consistent CP-net. (Such CP-nets exist.) Otherwise, C pages 71­80, 1999. is locally-consistent and for C we take the CP-net we [Boutilier et al., 2004a] C. Boutilier, R. Brafman, C. Domsh- constructed in Section 4.2. The mapping from locally lak, H. Hoos, and D. Poole. CP-nets: a tool for represent- consistent GCP-nets to CP-nets, described in Section 4.2, ing and reasoning with conditional ceteris paribus state- preserves consistency (Lemma 3 (iii)). Since local incon- ments. JAIR, 21:135­191, 2004. sistency implies inconsistency, we have that the GCP-net [Boutilier et al., 2004b] C. Boutilier, R. I. Brafman, C is consistent if and only if the CP-net C is consistent. C. Domshlak, H. Hoos, and D. Poole. Preference-based Thus, PSPACE-hardness of the C P - C O N S I S T E N C Y problem constrained optimization with CP-nets. Computational folN ws from Theorem 3. lo Intelligence, 20(2):137­157, 2004. [Brafman and Dimopoulos, 2004] R. Brafman and Y. Di- otice the huge complexity gap with the problem of de- mopoulos. Extended semantics and optimization algo- ciding whether there exists a nondominated outcome, which rithms for CP-networks. Computational Intelligence, is "only" NP-complete [Domshlak et al., 2003]. 20(2):218­245, 2004. [Brafman and Domshlak, 2002] R. Brafman and C. Domsh- 6 Concluding remarks lak. Introducing variable importance trade-offs into CP- We have shown that dominance and consistency testing in nets. In Proceedings of UAI-02, pages 69­76, 2002. CP-nets is PSPACE-complete. The repeated use of reduc- [Brafman and Domshlak, 2003] R. Brafman and C. Domsh- tions from planning problems confirms the importance of the lak. Structure and complexity of planning with unary op- structural similarity between STRIPS planning and reasoning erators. JAIR, 18:315­439, 2003. with CP-nets. This suggests that the well-developed field of [Bylander, 1994] T. Bylander. The computational complex- planning algorithms for STRIPS representations, especially ity of propositional STRIPS planning. Artificial Intelli- for unary operators [Brafman and Domshlak, 2003], could be gence Journal, 69(1-2):165­204, 1994. useful for implementing algorithms for dominance and con- sistency in CP-nets. [Domshlak and Brafman, 2002] C. Domshlak and R. I. Braf- Our theorems extend to CP-nets with non-binary domains, man. CP-nets--reasoning and consistency testing. In Pro- and to extensions and variations of CP-nets, such as TCP- ceedings of KR2002, pages 121­132, 2002. nets [Brafman and Domshlak, 2002] that allows for explicit [Domshlak et al., 2003] C. Domshlak, F. Rossi, K. B. Ven- priority of some variables over others, and the more general able, and T. Walsh. Reasoning about soft constraints and preference language described in [Wilson, 2004b; 2004a]. conditional preferences: complexity results and approx- The complexity result for dominance is also relevant imation techniques. In Proceedings of IJCAI-03, pages for constrained optimisation, where a complete algorithm 215­220, 2003. [Boutilier et al., 2004b] involves many dominance checks. [Lang, 2004] J. Lang. Logical preference representation and Our results reinforce the need for work on finding special combinatorial vote. Annals of Mathematics and Artificial classes of problems where dominance and consistency can Intelligence, 42(1):37­71, 2004. be tested efficiently [Domshlak and Brafman, 2002; Boutilier [Papadimitriou, 1994] Ch. Papadimitriou. Computational et al., 2004a], and for incomplete methods for checking con- sistency and constrained optimisation [Wilson, 2004a]. complexity. Addison­Wesley, 1994. Several open problems remain. We do not know whether [Wilson, 2004a] N. Wilson. Consistency and constrained op- dominance and consistency testing remain PSPACE- timisation for conditional preferences. In Proceedings of complete when the number of parents in the dependency ECAI-04, pages 888­892, 2004. graph is bounded by a constant. We also do not know whether [Wilson, 2004b] N. Wilson. Extending CP-nets with these two problems remain PSPACE-complete for CP-nets stronger conditional preference statements. In Proceed- in conjunctive form (the reduction used to prove Theorems ings of AAAI-04, pages 735­741, 2004. 2 and 4 yields CP-nets that are not in conjunctive form). Fi-