Answer: \(\mathrm{NP}\text{-hard}\), even for \(\tau=1\) and \(d=2\); no polynomial-time algorithm in \(m,\tau,d,L\) exists unless \(\mathrm{P}=\mathrm{NP}\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateDT* is complete for any arbitrary acyclic CP- nets. PROOF. DT* traverses the tree searching all neighbours; it fol- lows lowest evaluated value path and keeps a sorted priority queue of alternate path segments along the way. If at any point the path being followed has a higher evaluated value than other encoun- tered path segments, the higher evaluated value path is kept in the fringe and the process is continued at the lower value sub-path. This continues until the currently considered node for expansion is the target outcome or the fringe is empty.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of acyclic CP-net types \(t\), each with a complete conditional preference model and rational mass \(\mu_t>0\) satisfying \(\sum_t \mu_t=1\), and outcomes \(\alpha,\beta\), compute exactly \(p_{\alpha\succ\beta}=\sum_{t:\,N_t\models\alpha\succ\beta}\mu_t\).
All types share variables \(X_1,\ldots,X_m\), with explicitly listed finite nonempty domains \(D_i\); an outcome is an element of \(\prod_i D_i\). Each type \(t\) specifies an acyclic CP-net \(N_t\), with an explicitly listed strict total order on \(D_i\) for every assignment to the parents of \(X_i\); dependency graphs may differ across types.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(\sum_t\mu_t=1\). Let \(L\) be the total binary input length and \(d=\max_i|D_i|\); state running times in \(m,\tau,d,L\).
Write \(N_t\models\alpha\succ\beta\) exactly when a nonempty sequence of improving flips leads from \(\beta\) to \(\alpha\): each flip changes one variable to any strictly preferred value in its current parent context, leaving all other variables fixed.
Given distinct outcomes \(\alpha,\beta\), the required output is the exact rational \(p_{\alpha\succ\beta}=\sum_{t:\,N_t\models\alpha\succ\beta}\mu_t\).
Is exact computation of \(p_{\alpha\succ\beta}\) possible in polynomial time in \(m,\tau,d,L\), or is it NP-hard?
DT* is complete for arbitrary acyclic CP-nets, without a polynomial worst-case guarantee ([Li, Vo and Kowalczyk](https://www.ifaamas.org/Proceedings/aamas2011/papers/D2_R49.pdf)); discrete dominance is NP-complete even for binary acyclic networks with at most one directed path between any two variables ([Boutilier et al.](https://arxiv.org/pdf/1107.0023)).
Dominance probability is \(\#\mathrm{P}\)-hard for acyclic probabilistic CP-nets whose local preference rules are sampled independently; that representation specifies the distribution implicitly rather than listing its support ([Bigot et al.](https://arxiv.org/pdf/1309.6817)). No result for exactly the explicit-support problem was verified.
Exact computation is \(\mathrm{NP}\)-hard, already when \(\tau=1\) and \(d=2\). Consequently, an algorithm polynomial in \(m,\tau,d,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
We use the following established theorem: deciding whether an improving-flip sequence connects two specified outcomes is \(\mathrm{NP}\)-complete for binary acyclic CP-nets whose graphs have at most one directed path between any two variables. The hardness construction has maximum indegree at most six, fully specified strict preferences, and distinct source and target outcomes. See Theorem 15 and its proof in Appendix A of [Boutilier et al.](https://arxiv.org/pdf/1107.0023).
These restrictions satisfy the present task’s hypotheses. In particular, every variable has at most \(2^6\) parent assignments, so explicitly listing every CPT row preserves the polynomial size of the hardness construction. Since domains are binary, its improving flips also coincide exactly with the flips permitted here.
Take an instance \((N,\alpha,\beta)\) from that restricted dominance problem. Construct a society with the same variables, domains, and outcomes, and exactly one supported type:
\(N_1=N,\qquad \mu_1=1.\)
This is a valid explicit-support instance: its mass is positive, has a constant-length binary rational encoding, and sums to one. The construction merely copies the dominance instance and adds the mass, so it takes linear time in its encoding length.
By the definition of the required probability,
\(p_{\alpha\succ\beta}=\mathbf{1}\{N\models\alpha\succ\beta\}.\)
Thus the exact output is one precisely for yes-instances of dominance, and zero otherwise. One call to an exact probability algorithm, followed by comparison with one, therefore decides the restricted dominance problem.
If exact computation took time polynomial in \(m,\tau,d,L\), this reduction would yield a polynomial-time dominance algorithm: here \(\tau=1\), \(d=2\), and both \(m\) and the constructed length \(L\) are bounded polynomially by the original input length. This proves the claimed hardness.
Explicit support makes the aggregation straightforward once dominance has been decided for each listed type. It does not make those dominance decisions polynomial-time solvable.
For completeness, a direct exact algorithm has running time
\(O\!\left(\tau m d^{m+1}\operatorname{poly}(L)\right).\)
To justify this bound, let \(K=\prod_{i=1}^{m}|D_i|\), so \(K\leq d^m\). For each type, form the outcome graph implicitly: its vertices are outcomes, and its edges are improving flips. Each vertex has at most \(m(d-1)\) candidate outgoing edges. Checking a candidate against the explicitly listed CPT takes polynomial time in \(L\).
A graph search starting at \(\beta\) consequently decides reachability of \(\alpha\) in \(O(Kmd\operatorname{poly}(L))\) time per type. Every generated edge is an allowed improving flip, and every allowed improving flip is generated, so reachability is exactly the task’s dominance relation. Because \(\alpha\neq\beta\), a successful path is necessarily nonempty.
The final rational summation also takes polynomial time in the input length. Write each mass as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\), and let \(S\) be the set of types for which dominance holds. Set
\(B=\prod_{t=1}^{\tau}b_t,\qquad A=\sum_{t\in S}a_t(B/b_t).\)
Then the required output is \(A/B\), reduced if desired. The binary length of \(B\) is at most the sum of the denominator encoding lengths plus a constant, hence \(O(L)\). Since the masses sum to one, \(0\leq A\leq B\), so \(A\) also has \(O(L)\) bits. Products, exact divisions, additions, and reduction by a greatest common divisor therefore require only polynomial time.
The hardness proof uses discrete dominance directly; no transfer from an implicitly represented probabilistic CP-net is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The cited hardness result applies to the required explicit input representation, the reduction preserves the dominance question exactly, and the additional algorithm and arithmetic bounds are valid. No major or minor mathematical issues were found.
Theorem 15 establishes NP-completeness of dominance testing for binary, directed-path singly connected CP-nets. Appendix A constructs an acyclic network with maximum indegree six, specifies a strict preference for every parent context, and uses distinct outcomes assigning opposite values to all variables. These facts verify the restrictions asserted by the prover. [Boutilier et al., Theorem 15 and Appendix A](https://arxiv.org/pdf/1107.0023)
With binary domains and at most six parents, each conditional preference table has at most \(2^6=64\) rows. Thus expanding the construction into explicitly listed tables takes polynomial space and time. There is no hidden reliance on a succinct table representation.
Binary domains also ensure that the source problem’s improving flips agree with the task’s permitted flips: there is only one possible alternative value for a changed variable.
Setting \(N_1=N\) and \(\mu_1=1\) produces support size \(\tau=1\), with a positive binary rational mass summing to one. The variables, nonempty domains, complete preference tables, acyclic graph, and distinct outcomes are inherited from the source instance.
Copying an already explicitly encoded dominance instance and adding a constant-size mass is linear in its encoding length. The constructed \(L\) and \(m\) are therefore polynomially bounded by the source input length.
For the singleton society, the definition gives
\[
p_{\alpha\succ\beta}=\mathbf{1}\{N\models\alpha\succ\beta\}.
\]
Hence the exact output is \(1\) precisely when an improving sequence leads from \(\beta\) to \(\alpha\), and is \(0\) otherwise. There is no reversal of the dominance relation.
One exact computation and a comparison with \(1\) decide the NP-complete source problem. This establishes NP-hardness of the requested function computation. The prover correctly does not claim NP-completeness for the general function problem.
Since \(\tau=1\), \(d=2\), and the remaining parameters are polynomially bounded, the claimed consequence for an algorithm polynomial in \(m,\tau,d,L\) follows.
The outcome count is
\[
K=\prod_{i=1}^{m}|D_i|\leq d^m.
\]
Each outcome has at most \(m(d-1)\) candidate flips. Reading the applicable explicitly listed preference row and checking strict improvement takes polynomial time in \(L\).
A graph search with visited outcomes therefore takes \(O(Kmd\operatorname{poly}(L))\) time per type. Its edges are exactly the allowed improving flips, so its reachability test computes the required dominance relation. Distinctness of \(\alpha\) and \(\beta\) ensures that successful reachability uses a nonempty path.
Multiplication by \(\tau\) yields the stated bound \(O(\tau m d^{m+1}\operatorname{poly}(L))\). Singleton domains cause no difficulty; distinct valid outcomes ensure that some domain has at least two values.
Every denominator \(b_t\) divides \(B=\prod_t b_t\), so each summand defining \(A\) is an integer and \(A/B\) is exactly the selected mass sum.
The bit length of \(B\) is bounded by the total denominator encoding length, up to a constant. Positivity and normalization give \(0\leq A\leq B\), including when no type satisfies dominance. Thus both output integers have \(O(L)\) bits, and the stated integer arithmetic and optional fraction reduction take polynomial time.
No additional clarification is needed. The argument resolves the explicit-support problem without transferring a hardness result from an implicitly represented distribution.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.