d4-conf-aaai-2010-0267 (d4-conf-aaai-2010-0267)

Given a common set of features \(V\), two outcomes \(\alpha,\beta\), a fixed TCP-net semantics, and a finite support of complete TCP-net types \((N_j,\mu_j)_{j=1}^{\tau}\) with rational masses summing to \(1\), compute \(p=\sum_{j:\,\alpha\text{ dominates }\beta\text{ under }N_j}\mu_j\), and decide whether \(p\ge q\) for a rational threshold \(q\).

Let \(V=\{X_1,\ldots,X_m\}\), with explicitly listed finite nonempty domains \(D_i\); outcomes belong to \(\prod_i D_i\). Each complete TCP-net specifies parent sets and explicit conditional preference tables giving a strict total order on \(D_i\) for every parent assignment, together with unconditional importance edges and conditional importance tables orienting each importance edge for every assignment to its selector variables. Parents exclude their own feature; selectors exclude both endpoints.
Fix the following worsening semantics. All conditional orders and importance orientations are evaluated at the source outcome. A V-flip changes exactly one feature to a less preferred value. An I-flip worsens one feature \(X\) and changes an arbitrary nonempty set of features less important than \(X\), leaving all other features fixed; the changes to those less important features are unrestricted.
Promise that each type's graph of outcomes and worsening moves is acyclic. Write \(\alpha\succ_N\beta\) when a nonempty sequence of these moves leads from \(\alpha\) to \(\beta\).
A society is given by its support: the list \((N_j,\mu_j)_{j=1}^{\tau}\) of distinct types with positive binary rational masses satisfying \(\sum_j\mu_j=1\). Here \(\tau\) is the support size, not the number of possible types. Input also includes distinct outcomes \(\alpha,\beta\) and a binary rational threshold \(q\in[0,1]\).
Define \(p=\sum_{j:\,\alpha\succ_{N_j}\beta}\mu_j\). Let \(L\) be the total input bit length, including domains, networks, tables, masses, outcomes, and threshold; state running times in \(m,\tau,L\).

Can \(p\) be computed exactly in polynomial time in \(m,\tau,L\), or is this computation NP-hard? Is deciding \(p\ge q\) in P, or is it NP-hard?

For individual TCP-nets, a Kripke encoding preserves worsening moves under projection and introduces only transitions that leave the outcome unchanged. [Santhanam, Basu, and Honavar](https://faculty.ist.psu.edu/vhonavar/Papers/aaai10-santhanam.pdf)
Dominance testing is NP-complete for binary CP-nets whose dependency graph is acyclic and has at most one directed path between any two features. [Boutilier et al.](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/boutilier04a.pdf)
Computing dominance probability is \(\#\mathrm{P}\)-hard for acyclic probabilistic CP-nets, which encode distributions through independent local preference choices rather than an explicit support list; this is a different input model. No result settling the specified explicit-support TCP-net problem was located. [Bigot et al.](https://arxiv.org/pdf/1309.6817)

Result

Exact computation of \(p\) is \(\mathrm{NP}\)-hard, and deciding \(p\ge q\) is \(\mathrm{NP}\)-hard. Both statements hold already for \(\tau=1\), binary domains, and TCP-nets with no importance edges. Consequently, polynomial-time algorithms in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

Here, hardness of exact computation means that an exact-value algorithm would solve an \(\mathrm{NP}\)-hard decision problem through one evaluation and a comparison.

1. The individual dominance problem used in the reduction

We use the following established theorem: dominance testing is \(\mathrm{NP}\)-complete for complete binary CP-nets whose dependency graph is acyclic and has at most one directed path between any two features. These networks have explicitly specified conditional preference tables. See [Boutilier et al., Theorem 15](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/boutilier04a.pdf).

For these networks, dominance of \(\alpha\) over \(\beta\) is equivalent to an improving-flip sequence from \(\beta\) to \(\alpha\), by the same paper’s soundness and completeness theorems, Theorems 7–8.

This is also equivalent to a worsening-flip sequence from \(\alpha\) to \(\beta\) under the question’s source-evaluated semantics. Indeed, a single-feature flip leaves that feature’s parents unchanged, because parents exclude the feature itself. Thus its conditional preference order is identical at both endpoints. Reversing an improving flip therefore gives a legal worsening flip, and conversely.

We may restrict the source problem to distinct outcomes: equal-outcome strict-dominance queries are automatically negative and can be replaced by a fixed negative query with distinct outcomes.

2. Verification of the acyclicity promise

Let \(C\) be any complete CP-net with an acyclic dependency graph. Regard \(C\) as a TCP-net with no importance edges. Its worsening moves are exactly its V-flips, since no I-flip is available.

Choose a topological ordering \(Y_1,\ldots,Y_m\) of its features. For an outcome \(o\), define \(r_i(o)\) as the position of \(o[Y_i]\) in the conditional order evaluated at \(o\), numbering positions from zero, with zero most preferred. Define the rank vector \(R(o)=(r_1(o),\ldots,r_m(o))\).

Suppose a worsening flip changes \(Y_k\), taking \(o\) to \(o'\).

• For every \(i<k\), both \(Y_i\) and all its parents remain unchanged: every parent precedes \(Y_i\) in the topological ordering. Hence \(r_i(o')=r_i(o)\).
• All parents of \(Y_k\) also remain unchanged. The flip chooses a strictly less preferred value in this unchanged conditional order, so \(r_k(o')>r_k(o)\).

Consequently, \(R(o')\) is strictly larger than \(R(o)\) in lexicographic order. This strict order cannot increase around a directed cycle. Therefore the entire worsening-move graph is acyclic.

Thus every source instance used below satisfies the promised outcome-graph acyclicity, rather than merely dependency-graph acyclicity.

3. Reduction to the explicit-support society

Given a source dominance instance \((C,\alpha,\beta)\), construct the society containing just the type \(N_1=C\), interpreted as above, with \(\tau=1\) and \(\mu_1=1\). Set \(q=1\).

This construction copies the domains, parent sets, conditional tables, and outcomes, and adds empty importance data and constant-size rational data. It takes polynomial time in the source bit length and produces polynomial total bit length \(L\). The domains remain binary, the network remains complete, and the promise holds by Section 2.

For the constructed instance, \(p=1\) if \(\alpha\succ_{N_1}\beta\), and \(p=0\) otherwise. Hence \(p\ge1\) holds exactly when the source dominance query is positive.

This proves \(\mathrm{NP}\)-hardness of the threshold problem by a polynomial-time many-one reduction. It also proves hardness of exact computation: compute \(p\) once and test whether the result equals one.

The degenerate threshold \(q=0\) is always accepted, but hardness holds at the fixed threshold \(q=1\).

4. Running times and the role of explicit support

For completeness, a finite exhaustive algorithm exists. Put \(S=\prod_{i=1}^{m}|D_i|\), the number of outcomes.

For each listed type, enumerate all ordered pairs of outcomes and test whether each pair forms a legal move. This test takes polynomial time in \(m,L\): evaluate the explicit tables at the source, determine the changed coordinates, and check either the V-flip condition or each possible distinguished feature for an I-flip. Reachability in the resulting explicit graph then determines whether that type contributes its mass.

The resulting exact algorithm has running time \(O(\tau S^2\operatorname{poly}(m,L))\). Since domains are explicitly listed, \(|D_i|\le L\), giving the bound \(O(\tau L^{2m}\operatorname{poly}(m,L))\).

Once the dominance indicators are known, rational aggregation takes only polynomial time in \(\tau,L\). To verify the bit-size bound, write \(\mu_j=a_j/b_j\) and use \(B=\prod_j b_j\) as a common denominator. Its bit length is at most the sum of the denominator bit lengths, hence \(O(L)\). The numerator of any selected mass sum is between zero and \(B\), because the masses are positive and sum to one. Exact addition and comparison with \(q\) therefore require only polynomial bit complexity.

Equivalently, an individual dominance oracle yields exact \(p\) using \(\tau\) oracle calls plus polynomial overhead in \(m,\tau,L\). The hardness arises already in a single dominance query; no implicitly represented distribution or probabilistic counting theorem is needed.

These arguments settle both requested hardness alternatives. They do not assert that the unrestricted threshold problem belongs to \(\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output proves both requested hardness claims. The reduction respects the explicit-support encoding and the promised acyclicity of the worsening-move graph. No major or minor mathematical issues were found.

• The cited hardness theorem applies. Section 1 accurately invokes Theorem 15: dominance testing is \(\mathrm{NP}\)-complete for binary, directed-path singly connected CP-nets. The cited hardness construction has an acyclic dependency graph, complete strict conditional preferences, and at most six parents per feature, so explicitly listing its conditional tables preserves polynomial input size. Thus the theorem supplies the source problem with the encoding the prover requires. [Boutilier et al., Theorem 15 and Appendix A](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/boutilier04a.pdf).

• The dominance-to-reachability equivalence is valid. Theorem 7 gives soundness of improving sequences; Theorem 8 gives completeness for acyclic CP-nets. The source networks satisfy that acyclicity hypothesis. The prover states the combined equivalence accurately. [Boutilier et al., Theorems 7–8](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/boutilier04a.pdf).

The reversal argument also matches the task’s source-evaluated semantics. A single-feature flip changes none of that feature’s parents, so its conditional order is identical at the two endpoints. Reversing each improving flip therefore produces a legal worsening flip. Reversing the sequence exchanges its endpoints as claimed. Since the queried outcomes are distinct, any connecting sequence is nonempty.

• The distinct-outcome restriction is harmless. Equal-outcome strict-dominance queries are negative for the acyclic source networks. Replacing such inputs by a fixed negative distinct-outcome query preserves the answer and requires only constant additional data. This is a routine restriction of the source problem, with no substantive missing lemma.

• The outcome-graph acyclicity proof is correct. With no importance edges, an I-flip cannot select a nonempty set of less important features, so only V-flips remain.

In the stated topological ordering, a flip of \(Y_k\) leaves every earlier feature and its parents unchanged. Consequently, every earlier rank coordinate is unchanged. The parents of \(Y_k\) are also unchanged, while its new value is strictly less preferred, so its rank strictly increases. Changes in later rank coordinates cannot affect this lexicographic comparison.

Thus every worsening edge strictly increases \(R(o)\). A directed cycle would require a strict increase back to its starting vector, which is impossible. The proof establishes precisely the outcome-graph promise required by the task.

• The society construction is a valid polynomial-time reduction. The constructed support has one type with positive rational mass \(\mu_1=1\), satisfying normalization and distinctness of listed types. Binary domains, complete preference tables, and the outcomes are copied; empty importance data are permitted. The chosen threshold \(q=1\) lies in the allowed interval. The construction increases input size only polynomially, and Section 2 verifies its promise.

For this instance, \(p=1\) exactly when the source dominance query is positive, and otherwise \(p=0\). Therefore \(p\ge q\) preserves both positive and negative answers. This establishes the claimed many-one hardness of the threshold problem.

• The exact-computation claim follows under the stated notion of hardness. An exact-value algorithm, followed by comparison with one, decides the same source problem using a single evaluation. The prover explicitly identifies this meaning of hardness for a function problem. Hence a polynomial-time exact algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). No counting-hardness claim is needed.

• The exhaustive running-time bound is valid. With \(S=\prod_i |D_i|\), enumerating all ordered outcome pairs costs \(S^2\) candidate checks per type.

The described legality check can evaluate all relevant tables at the source outcome, identify changed coordinates, and check each possible distinguished feature for an I-flip. Its work is polynomial in \(m,L\); it does not require enumerating all subsets of features. Reachability in the resulting explicit graph fits within the stated bound
\(O(\tau S^2\operatorname{poly}(m,L))\).

Explicit domain listing gives \(|D_i|\le L\), so the further bound
\(O(\tau L^{2m}\operatorname{poly}(m,L))\) is sound. This is an exhaustive upper bound, not a polynomial-time claim.

• The rational arithmetic analysis is correct. For \(B=\prod_j b_j\), the bit length is \(O(L)\), since all denominators occur in the input. Each selected mass sum has an integer numerator over \(B\), between zero and \(B\), by positivity and normalization. Exact aggregation and comparison with the binary rational threshold therefore have polynomial bit complexity. The individual-oracle statement likewise requires exactly \(\tau\) dominance queries and polynomial additional work.

The output resolves the assigned alternatives. It appropriately leaves membership of the unrestricted threshold problem in \(\mathrm{NP}\) unclaimed. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩