Answer: \(\mathrm{NP}\text{-hard}\), even for \(\tau=1\), \(\mu_1=1\), and indegree at most three; polynomial-time solvability would imply \(\mathrm{P}=\mathrm{NP}\).
Proposition 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet N be a CP-net and Σ be its associated formulas base as described above and its associated partial order > on sym- bolic levels. Then ∀ω, ω′ ∈Ω, v ≻OP v′ iff ω ≻N ω′, where v (resp. v′) is the vector of satisfaction levels associated to ω (resp. ω′). Example 5 (Example 1 continued) Let us consider again the two alternatives ω : VwPbSrCw and ω′ : VwPwSrCw. We have vω = (α, 1, 1, 1, δ, 1, θ, 1) and vω′ = (α, β, 1, 1, 1, 1, θ, 1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given τ complete CP-net types \(N_t\) with rational masses \(\mu_t\) summing to \(1\), and alternatives \(x,y\), compute \(M(x,y)=\sum_{t:\,x\succ_{N_t}y}\mu_t\) and \(M(y,x)\), and determine whether either exceeds \(1/2\).
Let \(m\geq 1\) be the number of Boolean variables, with alternatives in \(\{0,1\}^m\). Each type \(N_t\) is an acyclic CP-net with an explicitly listed conditional preference table specifying a strict order of the two values for every parent assignment; completeness refers to these tables, not to comparability of all alternatives.
Write \(x\succ_{N_t}y\) when every complete preference ranking satisfying the local ceteris paribus constraints strictly prefers \(x\) to \(y\).
A society is given by its support: the list of the \(\tau\geq 1\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Given alternatives \(x,y\), compute exactly \(M(x,y)=\sum_{t:x\succ_{N_t}y}\mu_t\) and \(M(y,x)\), and report separately whether each exceeds \(1/2\). Incomparable types contribute to neither sum; equality with \(1/2\) does not qualify.
Let \(L\) be the total input bit length, including graphs, tables, masses and alternatives; state running times in \(m,\tau,L\).
Is exact computation of these two masses and their strict-majority decisions polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
The discrete symbolic-priority encoding asserts equality between ordered-Pareto comparison of satisfaction vectors and CP-net dominance ([Kaci–Prade](https://doi.org/10.3233/978-1-58603-891-5-376)); later work identifies discrepancies between these representations ([Dubois–Prade–Touazi](https://link.springer.com/chapter/10.1007/978-3-319-02621-3_12)).
Discrete majority dominance is NP-hard even for a single acyclic binary CP-net of indegree three ([Lukasiewicz–Malizia](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)). No separate rational-mass classification was verified.
The task is \(\mathrm{NP}\text{-hard}\), already when the support size is \(\tau=1\), the sole mass is \(\mu_1=1\), and the CP-net has indegree at most three. Each strict-majority decision is individually \(\mathrm{NP}\text{-hard}\). Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Rational-mass aggregation itself requires only polynomial-time exact arithmetic once the individual dominance relations have been determined.
For a CP-net \(N\), define its improving-flip graph \(G_N\). Its vertices are the alternatives in \(\{0,1\}^m\). There is an edge \(a\to b\) precisely when the alternatives differ in one variable and the conditional preference table, evaluated at their common parent assignment, prefers the value in \(b\).
We first establish that this graph is acyclic. Choose a topological ordering \(X_1,\ldots,X_m\) of the CP-net’s dependency graph. For each alternative \(a\), define \(s_i(a)=1\) when its value of \(X_i\) is locally preferred under its parent assignment, and define \(s_i(a)=0\) otherwise.
An improving flip of \(X_i\) leaves every \(s_j\) with \(j<i\) unchanged: neither \(X_j\) nor any parent of \(X_j\) is \(X_i\). It changes \(s_i\) from zero to one. Consequently, the vector \((s_1(a),\ldots,s_m(a))\) strictly increases lexicographically along every improving edge. A directed cycle is therefore impossible.
A complete preference ranking satisfies the local constraints exactly when it places the endpoint of every improving edge above its starting point. Such rankings exist because the finite graph \(G_N\) is acyclic.
Lemma. For distinct alternatives \(x,y\), one has \(x\succ_N y\) if and only if \(G_N\) contains a directed path from \(y\) to \(x\).
Proof. If such a path exists, every satisfying ranking prefers each successive vertex to its predecessor. Transitivity therefore forces \(x\) above \(y\).
Conversely, suppose no path leads from \(y\) to \(x\). Add the edge \(x\to y\) to \(G_N\). Any resulting cycle would require an original path from \(y\) to \(x\), so the augmented graph is still acyclic. A topological ordering of this graph, interpreted from less preferred to more preferred, gives a complete ranking satisfying all original constraints and placing \(y\) above \(x\). Thus \(x\succ_N y\) does not hold. \(\square\)
If \(x=y\), both strict dominance statements are false, so both requested masses are zero.
Complete tables do not imply comparability of distinct alternatives. For example, with two independent variables each preferring one to zero, \((1,0)\) and \((0,1)\) have no improving path in either direction.
Lukasiewicz and Malizia’s Theorem 3.3 states that deciding whether one outcome dominates another is \(\mathrm{NP}\text{-hard}\), even for acyclic binary CP-nets of indegree at most three. Their Section 2.2 requires strict, complete conditional preference tables explicitly represented in the input, and defines dominance using the universal-ranking semantics in the question. Hence the theorem applies to the present representation. [Source: *Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting*.](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)
The hypotheses match individually: alternatives are Boolean assignments, the dependency graph is acyclic, and every parent assignment has an explicitly listed strict preference. No assumption of total comparability between outcomes is needed.
Take an instance \((N,x,y)\) of the restricted dominance problem from that theorem. Construct the society consisting of the single type \(N_1=N\) with mass \(\mu_1=1\).
This is a valid support representation: its mass is positive, has constant-length rational encoding, and sums to one. The transformation preserves \(m\) and increases input length by only constant overhead.
By the definition of the requested mass,
\(M(x,y)=1\) if \(x\succ_N y\), and \(M(x,y)=0\) otherwise.
Therefore,
\(M(x,y)>\tfrac12\quad\Longleftrightarrow\quad x\succ_N y.\)
This is a polynomial-time many-one reduction to the first strict-majority decision. Swapping the alternatives gives the same reduction to the second decision.
Exact computation is also \(\mathrm{NP}\text{-hard}\) in the function sense: one call to an exact-mass algorithm, followed by a comparison with \(\tfrac12\), solves the source dominance problem. Computing both masses and decisions necessarily solves these individual tasks.
The reduction uses a permitted rational mass directly; no separate hardness theorem for weighted societies is required.
Write each input mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive binary integers. A finite binary-fraction encoding can also be converted to this form in polynomial time.
Define
\(D=\prod_{t=1}^{\tau}b_t,\qquad w_t=a_t(D/b_t).\)
Then \(w_t\) is an integer and \(\mu_t=w_t/D\). The bit length of \(D\) is \(O(L)\), since the bit lengths of all input denominators sum to at most \(L\). Moreover, positivity and normalization give
\(\sum_{t=1}^{\tau}w_t=D.\)
Once both dominance indicators are known for every listed type, compute
\(S_{xy}=\sum_{t:x\succ_{N_t}y}w_t,\qquad S_{yx}=\sum_{t:y\succ_{N_t}x}w_t.\)
The exact answers are \(S_{xy}/D\) and \(S_{yx}/D\). These fractions need not be reduced to specify the masses exactly. Each numerator lies between zero and \(D\), so the output has \(O(L)\) bits.
Using ordinary integer multiplication and division, forming the common denominator and weights and summing them takes \(O(\tau L^2)\) bit operations. The decisions are exactly
\(M(x,y)>\tfrac12\quad\Longleftrightarrow\quad 2S_{xy}>D,\)
and likewise for the reverse direction. Equality fails this test, as required. Incomparable types have both indicators zero and contribute to neither numerator.
More generally, if individual dominance can be decided in time \(T(m,L)\), the entire task can be computed in time
\(O\!\left(\tau T(m,L)+\tau L^2\right).\)
Only the explicitly listed support is processed.
For each type, perform reachability searches from \(y\) and from \(x\) in its improving-flip graph. By the lemma, these searches determine the two required dominance indicators.
Each graph has \(2^m\) vertices and at most \(m2^m\) edges. Its outgoing neighbors can be generated by checking each variable’s explicitly listed table. Using a conservative \(O(L^2)\) bound per check, explicit-state breadth-first search gives the following bound on a random-access machine with bit-operation costs charged:
\(O\!\left(\tau m2^m L^2+\tau L^2\right).\)
Thus there is an exact algorithm exponential in \(m\), with polynomial dependence on the support size and input length.
The hardness proof does not use symbolic-priority comparisons. Any uniformly polynomial-time encoding and comparison procedure that exactly recovered the stated CP-net dominance on all these inputs would, through the single-type reduction, imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The cited hardness theorem applies to the stated input representation, and the single-type reduction establishes hardness for exact mass computation and for each strict-majority decision. I found no major or minor mathematical issues.
The improving-flip graph is defined correctly. Along an edge, exactly one variable changes, and its parents retain their values, so the relevant conditional preference row is unambiguous.
The acyclicity argument is valid:
Consequently, the improving-flip graph has no directed cycle. Since it is finite, it has a topological ordering, yielding a complete ranking satisfying every local constraint.
Both directions of the reachability lemma are correct. A path from \(y\) to \(x\) forces every satisfying ranking to place \(x\) above \(y\), by transitivity. Conversely, when no such path exists, adjoining \(x\to y\) cannot create a cycle: any newly created cycle would require an original path from \(y\) to \(x\). A topological ordering of the augmented graph supplies the required ranking preferring \(y\) to \(x\).
The restriction to distinct alternatives is explicit and necessary. The separate treatment of \(x=y\) correctly gives two zero masses.
The incomparability example is also correct. For independent variables preferring \(1\) to \(0\), neither \((1,0)\) nor \((0,1)\) can reach the other by improving flips.
Finding: Fully verified.
I checked the cited source. Theorem 3.3 establishes NP-hardness of dominance testing for acyclic binary CP-nets, even with the additional restriction of single connectivity and indegree three. Section 2.2 specifies strict rankings for every parent assignment, explicit table representation, and dominance quantified over all satisfying complete rankings. These match the task’s semantics and representation. [Lukasiewicz–Malizia, Section 2.2 and Theorem 3.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)
The prover’s omission of single connectivity from its stated hardness restriction is legitimate: hardness on that narrower subclass implies hardness on the larger class it names. Likewise, hardness for instances of indegree three implies hardness for the permitted class of indegree at most three.
Relabeling the two values of each feature as \(0\) and \(1\) does not change dominance or the relevant representation restrictions.
No total comparability assumption is imported from completeness of the conditional preference tables.
Finding: The theorem is correctly stated for the purpose of the argument, and its hypotheses are satisfied.
The constructed society has exactly one supported type and mass \(1\). It satisfies positivity, rational encoding, and normalization.
For this society, the claimed identity
\[
M(x,y)=
\begin{cases}
1,&x\succ_N y,\\
0,&\text{otherwise}
\end{cases}
\]
follows directly from the task’s definition. Thus the strict threshold test is equivalent to the source dominance question.
The construction is polynomial in the source input length and preserves the number of variables. It introduces no implicit enumeration of possible types.
The first strict-majority decision is therefore NP-hard by a many-one reduction. Swapping the two supplied alternatives correctly establishes hardness of the second decision considered individually.
For exact computation, the prover explicitly supplies the appropriate reduction interpretation: one exact-function call followed by a threshold comparison decides dominance. This establishes the claimed function hardness without asserting an unspecified function-completeness result.
Computing both masses and both decisions includes solving the first decision, so the joint task inherits the hardness.
Finding: Fully verified. A separate theorem about rationally weighted societies is unnecessary.
The arithmetic construction is correct:
The bit-length claim is valid because the logarithm of the product is the sum of the denominator logarithms, bounded by the total input length. Numerators and intermediate weights likewise have \(O(L)\) bits. Unreduced fractions specify the answers exactly.
The stated \(O(\tau L^2)\) arithmetic bound is a valid conservative bound using ordinary multiplication and division on \(O(L)\)-bit integers.
The strict-majority comparisons \(2S_{xy}>D\) and \(2S_{yx}>D\) are exact. Equality is rejected, and incomparable types contribute to neither sum.
The general running-time expression accounts for two dominance tests per type through a constant factor absorbed into the big-\(O\) notation.
Finding: Fully verified.
The graph has exactly \(2^m\) vertices and at most \(m2^m\) directed edges, because each alternative has at most one possible improving flip per variable.
The two reachability searches test the correct directions: searching from \(y\) determines whether \(x\) dominates \(y\), and searching from \(x\) determines the reverse relation.
Checking a variable’s preference by inspecting explicitly listed input tables admits the stated conservative polynomial cost. On the specified random-access model with charged bit costs, the bound
\[
O\!\left(\tau m2^m L^2+\tau L^2\right)
\]
covers neighbor generation, state handling, and exact aggregation.
The conclusion about symbolic-priority procedures is appropriately conditional: any polynomial procedure recovering this exact dominance relation would also solve the established hard subclass. The proof does not rely on the disputed representation equivalence.
Finding: Fully verified.
The argument establishes the requested NP-hardness classification, handles the specified edge cases, and supplies running times in \(m,\tau,L\). It does not overclaim NP membership or NP-completeness.
No repair or additional mathematical clarification is required.
⟨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.