Answer: \(\mathrm{NP}\text{-hard}\), already for \(\tau=1\) and \(\mu_1=1\)
Proposition 12 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate≻-comparison and ▷◁-comparison are NP-hard for the language of fully acyclic CP-nets, and tractable for polytree CP-nets. ∼-comparison is easy for 1-CP ̸⟳lex. Comparing theories. Checking if two theories yield the same preorder can be useful during the compilation process. We say that two formulas φ and φ′ are equivalent if they represent the same preorder, that is, if ⪰φ and ⪰φ′ are identical; we then write φ ≡φ′. eqivalence Given two formulas φ and φ′, are they equivalent? Consider a formula φ ∈CP, two alternatives o,o′, and let φ′ = φ ∪{o ≥o′}: clearly o ⪰φ′ o′, thus φ ≡φ′ if and only if o ⪰φ o′.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite alternative space \(X\), two alternatives \(o,o'\), and an explicit support of \(\tau\) fully acyclic CP-nets \(\phi_t\) with binary-rational masses \(\mu_t\ge 0\) summing to one, compute the exact population masses for which \(o\) is strictly preferred to \(o'\), \(o'\) is strictly preferred to \(o\), they are indifferent, or they are incomparable.
Let \(X=\prod_{i=1}^{m}D_i\), where the finite attribute domains \(D_i\) are explicitly listed and \(|D_i|\ge 2\); the product is represented implicitly. Input alternatives \(o,o'\in X\) must be distinct.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type \(\phi_t\) is a CP-net with an acyclic dependency graph and explicit, complete conditional preference tables specifying strict linear orders on attribute values for every parent assignment.
A worsening flip changes exactly one attribute to a locally less preferred value under its current parent assignment, fixing every other attribute. Let \(\succeq_t\) be the reflexive transitive closure of these flips, directed from better to worse outcomes; let \(\succ_t\), \(\sim_t\), and \(\bowtie_t\) denote its strict preference, indifference, and incomparability relations.
Compute exactly the four rational masses \(\sum_{t:o\succ_t o'}\mu_t\), \(\sum_{t:o'\succ_t o}\mu_t\), \(\sum_{t:o\sim_t o'}\mu_t\), and \(\sum_{t:o\bowtie_t o'}\mu_t\). Let \(L\) be the total input bit length, including domains, graphs, tables, alternatives, and masses; state running times in \(m,\tau,L\).
Is computing this exact four-mass vector possible in polynomial time in \(m,\tau,L\), or is it NP-hard?
For individual fully acyclic CP-nets, strict-preference and incomparability comparison are NP-hard; both are polynomial-time solvable for polytree CP-nets. These results are retained in the [extended compilation map](https://arxiv.org/pdf/2102.04107).
No result for exactly this explicit-support, rational-mass computation was identified in the literature search.
Computing the exact four-mass vector is \(\mathrm{NP}\)-hard, already when \(\tau=1\) and the sole mass is \(1\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The proof uses the individual strict-preference hardness result supplied in the question. No separate hardness theorem for societies is needed.
Fix one supported type. Relabel its attributes in a topological order \(1,\ldots,m\), so every parent of attribute \(i\) precedes \(i\).
For an outcome \(x\), let \(r_i(x)\) be the position of \(x_i\) in the strict local preference order specified by the parent assignment in \(x\), with position \(0\) best. Define
\[ R(x)=(r_1(x),\ldots,r_m(x)). \]
Suppose a worsening flip changes attribute \(i\), producing \(y\) from \(x\). For every \(j<i\), neither attribute \(j\) nor any of its parents changes, hence \(r_j(y)=r_j(x)\). The parents of \(i\) also remain fixed, so the definition of a worsening flip gives \(r_i(y)>r_i(x)\). Therefore \(R(y)\) is strictly larger than \(R(x)\) in lexicographic order.
Thus every nonempty worsening path strictly increases \(R\). There cannot be a directed cycle, or worsening paths in both directions between distinct outcomes. The reflexive transitive closure is consequently antisymmetric.
It follows that, for the distinct input alternatives, every type satisfies exactly one of
\[ o\succ_t o',\qquad o'\succ_t o,\qquad o\bowtie_t o'. \]
In particular, the indifference mass is always \(0\).
Use the following known result: deciding \(a\succ_\phi b\) for an acyclic CP-net with complete conditional preference tables is \(\mathrm{NP}\)-hard. This is the premise supplied in the question and is recorded in Proposition 11 of the [extended compilation map](https://arxiv.org/pdf/2102.04107); its Section 3.4 specifies complete tables containing linear orders.
The distinct-alternative restriction does not obstruct this hardness result. An instance with \(a=b\) is automatically negative and can be replaced by a fixed negative instance with distinct alternatives: one binary attribute preferring \(1\) to \(0\), queried in the direction \(0\succ 1\).
Given an individual comparison instance \((\phi,a,b)\) with \(a\ne b\), construct the society
\[ \tau=1,\qquad \phi_1=\phi,\qquad \mu_1=1, \]
and set \(o=a\), \(o'=b\). All required hypotheses hold: the mass is positive and rational, the masses sum to \(1\), and the domains, graph, tables, and alternatives are copied unchanged. The construction takes linear time and adds only constant encoding overhead.
Let \(F_1\) denote the first coordinate of the computed vector. Then
\[ F_1= \begin{cases} 1,&a\succ_\phi b,\\ 0,&\text{otherwise}. \end{cases} \]
Hence one exact-vector computation, followed by testing whether \(F_1=1\), decides the individual comparison instance.
More formally, the decision problem “is the first coordinate equal to \(1\)?” is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. The exact-vector function is therefore \(\mathrm{NP}\)-hard under a polynomial-time reduction using one function evaluation.
Let \(T(m,\ell)\) bound the time for one individual strict-preference comparison on an encoding of length at most \(\ell\).
For each supported type, test both \(o\succ_t o'\) and \(o'\succ_t o\). By Section 1, both cannot hold. If neither holds, classify the type as incomparable. This requires at most \(2\tau\) comparisons.
Write the binary-encoded rational masses as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\), and form the common denominator
\[ Q=\prod_{t=1}^{\tau}b_t. \]
Its bit length is at most the sum of the denominator bit lengths, hence \(O(L)\). For each of the three possible categories \(C\), form
\[ A_C=\sum_{t\in C}a_t\frac{Q}{b_t}. \]
Each summand is an integer. Because the masses are positive and sum to \(1\), every partial sum lies between \(0\) and \(Q\). Thus all arithmetic operands have \(O(L)\) bits.
Using schoolbook integer multiplication and division, constructing \(Q\) and the category numerators takes \(O(\tau L^2)\) bit operations. Unreduced fractions already give exact rational outputs. The vector is
\[ \left(\frac{A_+}{Q},\frac{A_-}{Q},0,\frac{A_{\bowtie}}{Q}\right). \]
The resulting running-time bound is
\[ O\!\left(\tau T(m,L)+\tau L^2\right). \]
In particular, under the polytree tractability premise supplied in the question, societies supported entirely on polytree CP-nets admit polynomial-time exact computation.
Set \(N=|X|=\prod_i|D_i|\). For each type, enumerate the outcomes and construct its worsening-flip graph by checking every ordered pair. A pair is an edge precisely when it differs on one attribute and the corresponding table row ranks the source value above the target value.
Scanning the explicit encoding gives a conservative \(O(mL^2)\) bit-operation bound per pair. After constructing the graph, two reachability searches classify the alternatives. Including rational arithmetic, this gives the bound
\[ O\!\left(\tau N^2mL^2+\tau L^2\right). \]
Since the domains are explicitly listed, \(\log_2 N=\sum_i\log_2|D_i|=O(L)\). Therefore this is also a bound of the form
\[ \tau\,\operatorname{poly}(m,L)\,2^{O(L)}. \]
The target question is thus settled: exact computation is \(\mathrm{NP}\)-hard despite explicit support and polynomial-size rational outputs.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: computing the exact four-mass vector is \(\mathrm{NP}\)-hard, already for a society with one supported type of mass \(1\). The argument resolves the assigned question. No major or minor mathematical issues were found.
The topological ordering exists because each dependency graph is acyclic. In that ordering, every parent of attribute \(i\) has index smaller than \(i\).
The rank \(r_i(x)\) is well-defined: the conditional preference table is complete, and its applicable row specifies a strict linear order.
For a worsening flip at attribute \(i\):
Ranks at later attributes may change, but this does not affect the lexicographic comparison. Thus the claimed strict increase of \(R\) is valid.
Strict lexicographic increase along every edge excludes directed cycles and paths in both directions between distinct outcomes. Consequently, the reflexive transitive closure is antisymmetric. The classification into the two strict-preference directions and incomparability is exhaustive and mutually exclusive for the required distinct alternatives. The indifference mass is therefore exactly \(0\).
The cited theorem is stated accurately. Proposition 11 establishes strict-preference comparison hardness for acyclic CP-nets. Section 3.4 defines CP-nets using complete conditional preference tables containing linear orders, and Section 2.1 requires finite attribute domains of size at least two. These hypotheses match the task. The paper’s worsening-swap closure also matches the preference semantics used here; its encoding through consecutive local comparisons generates the same reachability relation. See the [extended compilation map, Sections 2.1 and 3.4 and Proposition 11](https://arxiv.org/pdf/2102.04107).
The proof appropriately treats individual comparison hardness as the supplied premise. It does not need a separate theorem about societies.
The distinct-alternative restriction is handled correctly. Strict preference is irreflexive, so an instance with equal alternatives is negative. The proposed replacement is a valid negative instance with distinct alternatives: in the binary one-attribute net preferring \(1\) to \(0\), the query \(0\succ 1\) is false.
For a distinct comparison instance, copying its CP-net into a one-type society preserves every domain, graph, table, and alternative requirement. The mass \(1\) is a valid positive binary-encoded rational, and normalization holds.
With only this type, the first coordinate is exactly \(1\) when the original strict-preference query is true and exactly \(0\) otherwise. Therefore the reduction preserves both positive and negative instances.
The prover also distinguishes the reduction notions correctly: the associated decision problem is hard under polynomial-time many-one reductions, and the vector function permits solving it with one function evaluation. A polynomial-time exact-vector algorithm would consequently imply \(\mathrm{P}=\mathrm{NP}\).
Two strict-preference comparisons per type suffice. Antisymmetry excludes simultaneous positive answers; two negative answers establish incomparability.
The arithmetic bounds are valid:
Unreduced fractions are legitimate exact rational outputs. Hence the bound
\[
O\!\left(\tau T(m,L)+\tau L^2\right)
\]
is justified. The conditional polynomial-time conclusion for societies consisting entirely of polytree CP-nets follows from the supplied tractability premise.
Enumerating all outcomes and checking every ordered pair constructs precisely the worsening-flip graph. Comparing outcomes and scanning the explicit tables fits within the conservative per-pair bound \(O(mL^2)\). Two reachability searches are absorbed by the graph-construction bound.
Explicit domain listings imply \(\log_2 N=O(L)\), so both the stated bound
\[
O\!\left(\tau N^2mL^2+\tau L^2\right)
\]
and its exponential-in-\(L\) reformulation are valid.
No additional clarification or repair 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.