Answer: \(\mathrm{NP}\text{-hard}\), even with binary domains, two distinct supported types, equal masses, and fixed threshold \(q=\frac12\).
Corollary 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet N be a CP-net over variables V . Let o1 and o2 be associated outcomes and D = {X ∈V | o1[X] ̸= o2[X]}. Then, N ⊨o1 ≻o2 =⇒r(o1) −r(o2) ≥ X X∈D L(X) > 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed finite feature set \(V\), a support \(T\) of complete strict acyclic CP-nets \(N_t\) over \(V\), positive rational masses \(\mu_t\) summing to \(1\), two outcomes \(o,o'\), and a rational threshold \(q\in[0,1]\), decide whether \(\sum_{t\in T:\,N_t\models o\succ o'}\mu_t\ge q\).
An instance has a nonempty feature set \(V\), with \(m=|V|\), and explicitly listed finite domains \(D_X\), each of size at least two; these are shared by all types and may vary between instances.
A type is a CP-net whose dependency graph is acyclic and whose explicitly supplied conditional preference table gives a strict total order on \(D_X\) for every assignment to the parents of \(X\).
An outcome belongs to \(\Omega=\prod_{X\in V}D_X\). An improving flip changes exactly one feature to any locally preferred value under the current parent assignment. Write \(N_t\models o\succ o'\) precisely when a sequence of at least one improving flip leads from \(o'\) to \(o\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), satisfying \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible CP-nets.
Given this society, outcomes \(o,o'\in\Omega\), and a binary rational threshold \(q\in[0,1]\), decide whether \(\sum_{t\in T:\,N_t\models o\succ o'}\mu_t\ge q\). Equality meets the threshold; incomparable types contribute zero.
Measure running time in \(m\), \(\tau\), \(d=\max_X|D_X|\), and total input bit length \(L\), including domains, graphs, tables, outcomes, masses, and threshold.
Is this rational-mass dominance-threshold problem solvable in polynomial time in \(m,\tau,d,L\), or is it NP-hard?
Known results: individual dominance admits a computable positive rank-gap lower bound, giving a sound necessary-condition pruning test ([Laing–Thwaites–Gosling](https://doi.org/10.1613/jair.1.11323)); individual dominance is NP-hard even for binary acyclic CP-nets ([Boutilier et al.](https://www2.cs.sfu.ca/CourseCentral/411/jim/CPNets.JAIR04.pdf)).
For finite unweighted societies, strict-majority dominance is NP-complete on polynomially connected acyclic binary CP-nets ([Lukasiewicz–Malizia](https://arxiv.org/pdf/1806.10018)). No classification specifically using the explicit-support rational-mass input above was verified.
The rational-mass dominance-threshold problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even for binary domains and a fixed support size. Therefore, a polynomial-time algorithm in \(m,\tau,d,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
We use the following established theorem: deciding whether an improving-flip sequence leads from \(o'\) to \(o\) is \(\mathrm{NP}\)-hard for binary acyclic CP-nets with fully specified strict conditional preferences. The hardness construction in Theorem 15 and Appendix A of [Boutilier et al.](https://www2.cs.sfu.ca/CourseCentral/411/jim/CPNets.JAIR04.pdf) has at most six parents per feature.
This theorem applies to the encoding in the question. With binary domains and at most six parents, each conditional preference table has at most \(2^6\) rows. Thus the source hardness construction has polynomial size even when every table row is explicitly supplied. Binary flips also coincide exactly with the improving flips allowed here.
Given such an individual dominance instance \((N,o,o')\), construct a society with
\[
\]
\(T=\{t\},\qquad N_t=N,\qquad \mu_t=1,\qquad q=1.\)
Copy the feature set, domains, graph, tables, and queried outcomes unchanged. This is a valid instance: the single mass is positive and sums to one, and the threshold belongs to the permitted interval.
Its supporting mass is exactly
\( \displaystyle \sum_{t:\,N_t\models o\succ o'}\mu_t = \begin{cases} 1,&N\models o\succ o',\\ 0,&N\not\models o\succ o'. \end{cases} \)
Consequently, the supporting mass meets the threshold if and only if the original dominance instance is positive.
The construction copies the source input and adds constant-size data. In particular, \(\tau=1\), \(d=2\), and the output length is polynomial in the source length. Hence an algorithm polynomial in \(m,\tau,d,L\) would solve the source problem in polynomial time. This proves the claimed hardness.
The singleton reduction already settles the question. To show that hardness persists with multiple supported types, we give a second reduction with fixed \(\tau=2\), equal masses, and fixed \(q=\frac12\).
Start with the same source instance \((N,o,o')\). Add a fresh binary feature \(Z\), and define extended outcomes
\(\widehat o=(o,Z=0),\qquad \widehat o'=(o',Z=0).\)
Construct two types on this common feature set and these common domains:
Both graphs are acyclic, and all tables give strict total orders. The types are distinct because their preferences for \(Z\) differ.
Preservation for type \(A\). We claim that
\(N_A\models\widehat o\succ\widehat o' \quad\Longleftrightarrow\quad N\models o\succ o'.\)
For the forward implication, consider a positive-length improving sequence between the extended outcomes. If it flipped \(Z\), that flip would necessarily change \(0\) to \(1\). No improving flip could return \(Z\) to \(0\), contradicting the target assignment. Thus the sequence never flips \(Z\). Every step changes an original feature under exactly its original parent assignment and preference table, so the same positive-length sequence witnesses dominance in \(N\).
For the reverse implication, any improving sequence in \(N\) remains improving in \(N_A\) while \(Z\) stays at \(0\).
No support from type \(B\). At \(\widehat o'\), every feature has its unconditionally preferred value in \(N_B\). Therefore no improving flip is available. Since dominance requires at least one flip,
\(N_B\not\models\widehat o\succ\widehat o'.\)
Now assign \(\mu_A=\mu_B=\frac12\) and set \(q=\frac12\). The supporting mass is \(\frac12\) precisely when the original dominance instance is positive, and is zero otherwise. Because equality meets the threshold, this is another correct many-one reduction.
The construction adds one feature, copies one original CP-net, and supplies only unconditional tables for the second type. Its encoding size is polynomial. Thus hardness holds even with two distinct supported types and equal, constant-size rational masses.
Once the supporting types are known, the rational comparison is polynomial-time computable. Write \(\mu_t=a_t/b_t\) and \(q=c/e\), with positive denominators, and let
\(Q=e\prod_{t\in T}b_t.\)
For any specified subset \(S\subseteq T\), the threshold test is equivalent to the integer comparison
\(\displaystyle \sum_{t\in S}a_t(Q/b_t)\ \ge\ c(Q/e). \)
The bit length of \(Q\) is bounded by the sum of the input denominator lengths, hence by \(O(L)\). All intermediate integers have polynomial bit length, and there are polynomially many arithmetic operations.
The hardness therefore already occurs in determining individual dominance, with constant-size masses and thresholds. A sound necessary-condition pruning test does not change the reduction: deciding whether an unpruned type actually supports the comparison remains necessary.
The proved classification is \(\mathrm{NP}\)-hard. No claim of \(\mathrm{NP}\)-completeness for the unrestricted input class is needed to settle the question.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. Both reductions are valid polynomial-time many-one reductions, and the claimed hardness applies to explicitly supplied conditional preference tables. No mathematical gaps or false steps were found.
Theorem 15 of Boutilier et al. establishes NP-completeness of dominance testing for binary, directed-path singly connected acyclic CP-nets. Its Appendix A construction uses binary features, with parentless variable features and clause features having at most six parents. Preferences specify one strict binary order for every parent assignment, including assignments outside the condition permitting the clause feature’s upward flip. Thus the cited construction satisfies the required completeness and strictness assumptions. [Boutilier et al., Theorem 15 and Appendix A](https://www2.cs.sfu.ca/CourseCentral/411/jim/CPNets.JAIR04.pdf)
The source paper’s hardness proof explicitly characterizes positive instances by an improving-flip sequence from the initial outcome to the target outcome. Its constructed endpoints are distinct, so the task’s requirement of at least one flip causes no mismatch. [Boutilier et al., Appendix A](https://www2.cs.sfu.ca/CourseCentral/411/jim/CPNets.JAIR04.pdf)
The explicit-table encoding argument is correct: binary domains and at most six parents give at most \(2^6=64\) rows per feature. Expanding every table therefore preserves polynomial size. Binary flips have exactly the meaning required by the task.
The construction takes \(T=\{t\}\), copies \(N_t=N\), and sets \(\mu_t=q=1\). This satisfies every society requirement: the support is nonempty, its mass is a positive binary rational, the masses sum to one, and the threshold is permitted. The copied domains, graph, tables, and outcomes retain their validity.
There is exactly one possible contributor. Consequently, the supporting mass is \(1\) when the source dominance query is positive and \(0\) otherwise. Comparison with \(q=1\) therefore preserves both yes-instances and no-instances. Incomparability contributes zero as required.
The construction requires only copying the input and adding constant-size data. With \(\tau=1\) and \(d=2\), an algorithm polynomial in \(m,\tau,d,L\) would run in polynomial time on these reduced instances. Hence the claimed NP-hardness follows.
Both types use the same extended feature set and domains. Adding isolated \(Z\) to type \(A\) preserves acyclicity and complete strict tables. Type \(B\) has an edgeless graph and unconditional strict binary orders.
The types are distinct because their unconditional orders on \(Z\) differ. The phrase “its other domain value” is unambiguous because this reduction starts from binary instances.
An improving flip of \(Z\) can only change \(0\) to \(1\), and no improving flip can restore \(0\). Since both extended endpoints assign \(Z=0\), any successful sequence must leave \(Z\) unchanged throughout.
The remaining steps use exactly the original parent assignments and tables. They therefore yield a positive-length source sequence. Conversely, every source sequence remains improving after extension with \(Z=0\).
The positive-length requirement is preserved explicitly; the argument does not accidentally accept an empty sequence when the queried outcomes coincide.
At \(\widehat o'\), every feature already has its unconditionally preferred value in type \(B\). No first improving flip exists, so no positive-length improving sequence can reach any target.
With \(\mu_A=\mu_B=\frac12\), the supporting mass is exactly \(\frac12\) for positive source instances and zero otherwise. Because equality meets the threshold, \(q=\frac12\) gives the stated equivalence.
The second type requires only one unconditional row per feature. Together with the copied first type and one additional feature, this gives polynomial construction time and output length.
All denominators are positive, and \(Q=e\prod_{t\in T}b_t\) is a positive common multiple. Multiplying the threshold inequality by \(Q\) preserves its direction and gives the displayed integer comparison.
The binary length of this product is bounded by the total denominator encoding length, up to a constant. Numerator products and accumulated sums also have polynomial bit length, and the number of arithmetic operations is polynomial. This establishes efficient comparison for a specified supporting subset; it does not assume that finding that subset is efficient.
The prover establishes NP-hardness, including the stronger restriction to two distinct types with equal masses and a fixed threshold. It correctly avoids claiming NP-completeness for unrestricted instances. The pruning observation does not supply an algorithm or weaken the reduction.
No additional mathematical clarification is needed.
⟨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.