The Computational Complexity of Dominance and Consistency in CP-Nets

NEW RESULT — discrete: hard → continuous: hard · adversarial review: proved

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given a finite library of complete CP-net types $C_1,\ldots,C_\tau$ over $V$, rational masses $\mu_t$ summing to $1$, integral outcomes $\alpha,\beta\in\{0,1\}^{|V|}$, and a quota $q$, decide whether there exists one finite sequence $\pi$ of one-variable flips from $\alpha$ to $\beta$ such that $\sum_{t=1}^{\tau}\mu_t\mathbf{1}[\pi\text{ is an improving sequence in }C_t]\ge q$.

Packaged proof task (what the prover saw — nothing else)

Let $V$ contain $m\ge 1$ binary variables. Each type $C_t$ is represented by a finite set of rules $p:\ell>\neg\ell$, where $\ell$ is a literal of a variable $x$ and $p$ is a propositional formula not involving $x$. For every assignment to the other variables, exactly one value of $x$ is preferred. Dependency cycles are allowed; global consistency is not promised.
A society is given by its support: the list of the $\tau$ types with positive mass, each with its mass $\mu_t$ as a binary rational, with $\sum_{t=1}^{\tau}\mu_t=1$. Here $\tau$ is the support size, not the number of possible types.
The input also contains outcomes $\alpha,\beta\in\{0,1\}^{m}$ and a binary rational quota $q\in(0,1]$. Let $L$ be the total input bit length, including all rule formulas; state running times in $m,\tau,L$.
A flip is improving in $C_t$ if it changes only $x$, from $\neg\ell$ to $\ell$, under a rule $p:\ell>\neg\ell$ whose condition holds. A sequence $\pi=(\gamma_0,\ldots,\gamma_k)$, with $k\ge1$, starts at $\alpha$, ends at $\beta$, and changes exactly one variable at each step; repeated outcomes are allowed. It is improving in $C_t$ when every step is improving in that type.
The decision problem asks whether one such sequence satisfies $\sum_{t=1}^{\tau}\mu_t\mathbf{1}[\pi\text{ is improving in }C_t]\ge q$.

Is this common-sequence quota problem solvable in polynomial time, or is it $\mathrm{NP}$-hard?

Single-type dominance is $\mathrm{PSPACE}$-complete, even for globally consistent complete CP-nets, where global consistency means the absence of nonempty improving cycles ([Goldsmith et al.](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf)).
Related probabilistic CP-net work gives polynomial-time bounds on dominance probabilities for polytree structures, allowing each realized type its own dominance witness ([source](https://www.nickmattei.net/docs/pcp-nets.pdf)); this differs from requiring one common sequence. No result settling the exact mass-supported common-sequence problem was located.

Modeling choices made when packaging the task

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Result

The common-sequence quota problem is $\mathrm{PSPACE}$-complete under polynomial-time many-one reductions. In particular, it is $\mathrm{NP}$-hard, and a polynomial-time algorithm would imply $\mathrm{P}=\mathrm{PSPACE}$.

Hardness holds even with two semantically distinct types of equal positive mass, quota $q=1$, distinct endpoints, and both types globally consistent.

1. Hardness

Theorem 2 of [Goldsmith et al.](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf) establishes $\mathrm{PSPACE}$-hardness of dominance for globally consistent binary CP-nets. Their representation is precisely the relevant one: propositional rules whose conditions exclude the flipped variable, with local completeness and local consistency. Their dominance relation requires a nonempty improving sequence, and their hardness construction permits distinct endpoints.

Consequently, taking $\tau=1$, $\mu_1=1$, and $q=1$ immediately gives a polynomial-time reduction to the present problem. We next show that hardness also holds with a genuinely distinct, two-type support.

A reduction with two distinct types

Let $(C,\alpha,\beta)$ be a dominance instance from the globally consistent class, with $\alpha\ne\beta$. Introduce two fresh binary variables $w,z$.

Construct types $C_1,C_2$ by retaining every rule of $C$ and adding the following rules:

| Variable | Rules in $C_1$ | Rules in $C_2$ |
|---|---|---|
| $w$ | $\top:\neg w>w$ | $\top:\neg w>w$ |
| $z$ | $\top:\neg z>z$ | $\neg w:\neg z>z$, $w:z>\neg z$ |

Set $\alpha'=(\alpha,0,0)$, $\beta'=(\beta,0,0)$, $\mu_1=\mu_2=\tfrac12$, and $q=1$.

Both types satisfy the local preference promise. For old variables, the promise is inherited from $C$. Variable $w$ always prefers zero; variable $z$ always prefers zero in $C_1$, and prefers the value of $w$ in $C_2$. Every condition excludes the variable being flipped.

The types are semantically distinct: when $w=1$, they prefer opposite values of $z$.

Equivalence. Starting at $\alpha'$, an improving sequence in either type cannot change $w$, because its initial value zero is already preferred unconditionally. Hence $w$ remains zero. With $w=0$, both types prefer $z=0$, so $z$ also cannot change.

Therefore, every improving sequence from $\alpha'$ in either type uses only old variables. Such a sequence is improving in that type exactly when its projection is improving in $C$. Conversely, every improving sequence in $C$ lifts to a sequence improving in both types by keeping $w=z=0$.

Since quota one and the positive masses require improvement in both types, we obtain
\[ \text{$\beta$ dominates $\alpha$ in $C$} \quad\Longleftrightarrow\quad \text{the constructed quota instance is accepted}. \]
Here and below, this equivalence concerns nonempty sequences.

Global consistency. Suppose either constructed type had a nonempty improving cycle. Variable $w$ can only change from one to zero, so it cannot change on a closed sequence. With $w$ fixed, the preferred value of $z$ is fixed; thus $z$ cannot change on a closed improving sequence either. The cycle would consequently project to a nonempty improving cycle in $C$, contradicting its global consistency.

The construction adds two variables, a constant number of rules, and constant-size mass and quota encodings. It is polynomial in the source input length. This proves the stated restricted hardness.

2. An exact characterization by intersections of flip graphs

For each type $t$, let $G_t$ be the directed graph with vertex set $\{0,1\}^{m}$, whose edges are exactly the improving flips of $C_t$.

For a subset $S\subseteq\{1,\ldots,\tau\}$, define its mass by $\mu(S)=\sum_{t\in S}\mu_t$, and define $G_S$ to have edge set $\bigcap_{t\in S}E(G_t)$.

Lemma. The instance is accepted if and only if there exists a subset $S$ with $\mu(S)\ge q$ such that $G_S$ contains a nonempty directed walk from $\alpha$ to $\beta$.

Proof. Given a quota-satisfying sequence $\pi$, take $S$ to be precisely the types in which every step of $\pi$ is improving. Its mass meets the quota, and every step belongs to every graph indexed by $S$.

Conversely, a nonempty walk in $G_S$ is improving in every type in $S$. Its supporting mass is therefore at least $\mu(S)\ge q$. Since $q>0$, every qualifying subset is nonempty. This proves both directions.

The subset is fixed for the entire walk. Allowing it to change between steps would describe a different problem.

A bounded witness

Write $N=2^m$. Whenever the required walk exists, one exists with length at most $N$.

If $\alpha\ne\beta$, choose a shortest walk. Any repeated vertex would allow deletion of the intervening closed segment, preserving the endpoints and all remaining edges. Thus the walk is a simple path and has length at most $N-1$.

If $\alpha=\beta$, choose a shortest nonempty closed walk. An internal occurrence of $\alpha$ would give a shorter nonempty closed prefix. A repetition of any other vertex would permit deletion of a proper closed segment, leaving a shorter nonempty closed walk. Hence its vertices are distinct except for its coincident endpoints, and its length is at most $N$.

These deletions preserve improvement in every type of the fixed subset $S$.

3. Membership in polynomial space and running times

Consider the following nondeterministic algorithm:

Guess a subset $S$, represented by $\tau$ bits.
Compute $\mu(S)$ exactly and reject if $\mu(S)<q$.
Starting at $\alpha$, guess and check successive single-variable flips in $G_S$.
Accept upon reaching $\beta$ after at least one flip; reject any branch that has not accepted after $2^m$ flips.

The characterization and bounded-witness argument prove soundness and completeness.

Exact arithmetic and edge checks

Write $\mu_t=a_t/b_t$ and $q=c/d$, with positive denominators. The integer $D=d\prod_{t=1}^{\tau}b_t$ has $O(L)$ bits, because the sum of the encoded denominator lengths is at most $L$.

The comparison $\mu(S)\ge q$ is equivalent to comparing the integers $\sum_{t\in S}a_t(D/b_t)$ and $c(D/d)$. Both have $O(L)$ bits: each represents a quantity between zero and $D$, using the promised normalization and $q\le1$. Standard integer arithmetic therefore performs the comparison in polynomial time and space.

For a proposed flip, scan the rules of each selected type and evaluate the applicable conditions under the current outcome. Formula evaluation under a specified assignment is polynomial in formula length. Thus an edge of $G_S$ can be checked in $\operatorname{poly}(m,\tau,L)$ time and $O(L+m+\tau)$ space.

The algorithm stores the subset, current outcome, arithmetic workspace, and an $(m+1)$-bit step counter. Its total space is $O(L+m+\tau)$; its running time on each branch is $2^m\operatorname{poly}(m,\tau,L)$.

By the standard equality $\mathrm{NPSPACE}=\mathrm{PSPACE}$, the problem belongs to $\mathrm{PSPACE}$. Combined with Section 1, this proves completeness.

A deterministic time bound

There is also a direct deterministic algorithm running in $2^{m+\tau}\operatorname{poly}(m,\tau,L)$ time.

Enumerate the $2^\tau$ subsets $S$, discard those whose mass is below quota, and perform graph search in $G_S$, generating its at most $m$ outgoing neighbors per outcome.

To enforce nonemptiness even when $\alpha=\beta$, initialize the search with the outgoing neighbors of $\alpha$, marking a neighbor when it is enqueued. Accept if $\beta$ is reached. This initialization represents exactly the walks that have already taken their first edge.

Each search processes at most $2^m$ vertices and $m2^m$ candidate edges. The bound depends on the supplied support size $\tau$, without enumerating other possible types.

4. Why separate dominance witnesses do not suffice

This distinction already appears with two variables and individually acyclic types. Let $\alpha=00$, $\beta=11$, and specify preferred values as follows:

| Type | Preferred value of $x$ | Preferred value of $y$ |
|---|---|---|
| $C_1$ | $1$ | $x$ |
| $C_2$ | $y$ | $1$ |

Each specification is represented by an unconditional rule and two contextual rules.

Type $C_1$ admits the improving sequence $(00,10,11)$, while $C_2$ admits $(00,01,11)$. Thus both types individually support dominance.

However, at $00$, only the flip of $x$ is improving in $C_1$, and only the flip of $y$ is improving in $C_2$. No common improving sequence can even begin. With equal masses and quota one, this is a negative instance despite every type possessing its own witness.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

The prover’s claim is proved. The argument establishes $\mathrm{PSPACE}$-completeness for the stated representation, including the stronger restriction to two semantically distinct, globally consistent types of equal mass and quota $q=1$. I found no major or minor mathematical issues.

The cited hardness theorem applies.

Theorem 2 of Goldsmith et al. states that CP-DOMINANCE is $\mathrm{PSPACE}$-complete even for consistent CP-nets. The paper’s definitions match the task: binary variables, propositional rule conditions excluding the flipped variable, local completeness and local consistency, and dominance defined by a nonempty improving sequence. Consistency means absence of such cycles. The paragraph immediately following Theorem 2 explicitly confirms hardness with distinct endpoints. These are the hypotheses the prover needs. [Goldsmith et al., Definitions 1–5 and Theorem 2](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf)

Setting $\tau=1$, $\mu_1=1$, and $q=1$ preserves acceptance exactly and adds only constant-size numerical data. Thus the single-type reduction is valid and already establishes $\mathrm{PSPACE}$-hardness.

The two-type construction satisfies every input promise.

The old rules retain their original meaning because they do not mention the fresh variables. The added rules give exactly one preferred value for each fresh variable under every context, and their conditions exclude the variable being flipped.

Both masses are positive, their sum is one, and the quota is permitted. The endpoints remain distinct because the original endpoints are distinct.

The semantic-distinctness claim is correct: in contexts with $w=1$, the types give opposite preferences for $z$. Semantic distinction does not require that such contexts be reachable from the designated starting outcome.

The reduction’s equivalence is correct.

Starting with $w=0$, no improving flip can change $w$ in either type. Consequently, $w$ stays zero throughout any improving sequence. In that context, neither type permits changing the initially zero variable $z$.

Therefore, every relevant improving sequence consists entirely of old-variable flips. The retained rules make its projection improving in $C$, and every improving sequence in $C$ lifts with $w=z=0$.

At quota one, both positive-mass types must support the entire sequence. The projection and lifting preserve nonemptiness, so the equivalence also respects the task’s requirement of at least one flip.

Global consistency is preserved.

The cycle argument covers cycles starting at arbitrary outcomes, rather than only the designated endpoint context. On a closed improving sequence, the one-way preference for $w$ prevents $w$ from changing. With $w$ fixed, $z$ also has a fixed preferred value and cannot change on that closed sequence.

Every step of a hypothetical nonempty cycle would therefore change an old variable. Its projection would be a nonempty improving cycle in $C$, contradicting the source promise.

The construction has polynomial size and can be produced in polynomial time. The claimed restricted hardness follows.

The graph-intersection characterization has the correct quantifiers.

For a successful sequence, choosing exactly the types that support every step yields a subset of sufficient mass whose intersection graph contains the sequence.

Conversely, a walk in an intersection graph is supported by every selected type, so its total supporting mass is at least the subset’s mass. Additional supporting types cannot invalidate acceptance.

Crucially, the same subset is used throughout the walk. This matches the common-sequence requirement. Since $q>0$, an empty subset cannot qualify; no convention for its intersection graph affects the result.

The bounded-witness argument handles both endpoint cases.

For distinct endpoints, deleting a segment between repeated vertices preserves the directed walk and cannot leave an empty walk between those endpoints. A shortest witness therefore has at most $2^m-1$ edges.

For equal endpoints, the prover explicitly minimizes over nonempty closed walks. An internal return to the endpoint gives a shorter nonempty prefix. Removing a repeated segment at another vertex leaves a nonempty closed walk. Thus a shortest witness has at most $2^m$ edges.

All retained edges remain in the same intersection graph. The uniform bound of $2^m$ is valid, including when $m=1$.

Exact mass comparison has the stated bit complexity.

The common denominator
$$ D=d\prod_{t=1}^{\tau}b_t $$
has $O(L)$ bits because its logarithm is bounded by the total encoded denominator length.

The displayed integer comparison is exact. Positivity and normalization imply that each partial sum for the selected mass lies between zero and $D$; the quota term does too. Hence the relevant integers have $O(L)$ bits. Polynomial-time arithmetic with linear-size workspace suffices.

The nondeterministic algorithm establishes polynomial-space membership.

Guessing the subset once enforces common support. Checking each proposed flip against every selected type enforces membership in the intersection graph. Evaluating propositional formulas under an explicit assignment takes polynomial time and can use the claimed space.

The current outcome, subset, arithmetic workspace, and counter fit in $O(L+m+\tau)$ space. An $(m+1)$-bit counter can represent the cutoff $2^m$. Acceptance requires at least one checked flip, so equal endpoints do not cause erroneous acceptance of an empty sequence.

The witness bound proves completeness; checked edges and the mass comparison prove soundness. Every branch terminates within $2^m\operatorname{poly}(m,\tau,L)$ time.

The invoked equality $\mathrm{NPSPACE}=\mathrm{PSPACE}$ applies to this polynomial-space nondeterministic computation. Together with hardness, it establishes completeness.

The deterministic time bound is correct.

There are $2^\tau$ subsets. For each qualifying subset, graph search processes at most $2^m$ vertices and checks at most $m2^m$ candidate edges. This gives
$$ 2^{m+\tau}\operatorname{poly}(m,\tau,L) $$
time.

Initializing with outgoing neighbors correctly enforces a first edge. When the endpoints coincide, the starting outcome can subsequently be discovered through a nonempty return walk. The bound uses the supplied support size and does not enumerate unlisted types.

The separate-witness example is valid.

Both displayed sequences consist of improving flips in their respective types, and the displayed preferences define complete, locally consistent, individually acyclic types.

At the starting outcome, the two types permit different first flips, with no shared improving edge. Thus no common nonempty sequence exists, although both individual dominance queries succeed. This correctly illustrates the distinction relevant to the task.

No additional clarification or repair is needed. The answer resolves the requested complexity classification; it does not claim an unconditional separation from polynomial time.