Answer: \(\mathrm{NP}\text{-hard}\) under polynomial-time one-query reductions, even for \(\tau=2\), equal masses, and dependency graphs of depth one and maximum indegree two; exact rationals are encoded by binary numerators and denominators.
Proposition 3.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven two CP-netsA and B deciding ifKTD(A, B) = 0 cannot be computed in polynomial time unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of complete acyclic CP-net types \(N_t\) over a shared feature set \(F\), with binary-rational masses \(\mu_t\) summing to \(1\), compute the exact rational value of \(D(\mu)=\sum_{t,u}\mu_t\mu_u\,\mathrm{KTD}(N_t,N_u)\), using the paper’s normalized KTD with \(p=1/2\).
A society is given by its support: a list of \(\tau\) distinct complete acyclic CP-net types \(N_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
All types share \(m\geq1\) features with domain \(\{0,1\}\). Each type explicitly lists its dependency graph and a strict local preference for every assignment to each feature's parents. Every dependency is genuine: changing that parent alone changes the local preference in some context.
The outcomes are \(U=\{0,1\}^m\). Write \(x\succ_t y\) when a sequence of worsening single-feature flips leads from \(x\) to \(y\), using the local preference at each current parent assignment; otherwise distinct outcomes are incomparable if neither dominates the other.
For each unordered pair \(\{x,y\}\), let \(k_{tu}(x,y)\) be \(0\) when the two types agree on its orientation or both leave it incomparable, \(1\) when their orientations oppose, and \(1/2\) when exactly one type compares it.
Let \(c_{tu}\) count unordered outcome pairs comparable in at least one of the two types, and define \(\mathrm{KTD}(N_t,N_u)=\bigl(\sum_{\{x,y\}\subseteq U}k_{tu}(x,y)\bigr)/c_{tu}\).
The required value is \(D(\mu)=\sum_{t=1}^{\tau}\sum_{u=1}^{\tau}\mu_t\mu_u\,\mathrm{KTD}(N_t,N_u)\), returned as an exact binary rational. Let \(L\) be the total input bit length, including all explicitly listed conditional preference tables and masses; state running times in \(m,\tau,L\).
Can \(D(\mu)\) be computed exactly in time polynomial in \(m,\tau,L\), or is this computation NP-hard?
For two discrete CP-nets, a published result asserts that deciding \(\mathrm{KTD}(A,B)=0\) has no polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\). [Source](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p955.pdf)
No result settling the exact mass-weighted computation defined above was located in the literature search.
Exact computation is \(\mathrm{NP}\)-hard, even when \(\tau=2\), both masses are \(\frac12\), and both dependency graphs have depth one and maximum indegree two. The reduction uses one exact evaluation followed by polynomial-time arithmetic. Consequently, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
I interpret “exact binary rational” as a rational represented by a binary numerator and denominator. Requiring a terminating binary expansion would make the output requirement impossible: two equally weighted, separable four-feature types that disagree on exactly one feature give \(D=\frac{9}{56}\). The proof below establishes hardness for the intended exact-rational interpretation.
For an acyclic binary CP-net \(N\) on \(M\) features, let \(C(N)\) be its number of comparable unordered outcome pairs, and put \(Q=2^M\).
Acyclicity of the dependency graph ensures acyclicity of the worsening-flip graph. Indeed, recursively ordering outcomes lexicographically along a topological feature order, using each feature’s conditional preference, gives a total order that strictly decreases on every worsening flip. Thus each comparable unordered pair has exactly one dominance orientation.
Construct two types \(A,B\) by adjoining an isolated feature \(Z\) to \(N\). In \(A\), its preference is \(1\succ0\); in \(B\), it is \(0\succ1\). All other preferences coincide with \(N\). These are distinct valid types.
Because \(Z\) is isolated, dominance in each extended net is the product of dominance in \(N\) and the corresponding order on \(Z\): projecting a worsening sequence gives sequences in the two components, and component sequences can conversely be concatenated.
Write \(C=C(N)\). Classify unordered pairs of extended outcomes:
| Base outcomes and \(Z\)-values | Number | Contribution to numerator | Contribution to denominator |
|---|---:|---:|---:|
| Comparable distinct base outcomes, equal \(Z\) | \(2C\) | \(0\) | \(2C\) |
| Equal base outcomes, different \(Z\) | \(Q\) | \(Q\) | \(Q\) |
| Comparable distinct base outcomes, different \(Z\) | \(2C\) | \(C\) | \(2C\) |
| Incomparable base outcomes | — | \(0\) | \(0\) |
For the third row, each comparable base pair produces two cross-layer pairs. Each is comparable in exactly one extended net, so each contributes \(\frac12\).
Therefore
\(\mathrm{KTD}(A,B)=\frac{Q+C}{Q+4C}.\)
Give these two types mass \(\frac12\) each. The diagonal distances vanish and the distance is symmetric, so
\(D=\frac{Q+C}{2(Q+4C)}.\)
Consequently,
\(C=Q\frac{1-2D}{8D-1}.\)
The denominator is positive because
\(8D-1=\frac{3Q}{Q+4C}>0.\)
Thus one exact evaluation of \(D\) recovers \(C(N)\), and hence also the number of reflexively reachable ordered pairs
\(R(N)=Q+C(N).\)
The construction preserves completeness, acyclicity, and every genuine dependency.
Consider a CP-net with root features and leaf features only. Every root prefers \(1\) to \(0\). Each leaf has one or two root parents, and its preferred value is the conjunction of its parents’ values.
Every dependency is genuine: changing any parent changes the conjunction when all other parents equal \(1\). Every conditional preference table has at most four rows.
Fix initial and final root assignments \(a,b\). A worsening sequence can connect them exactly when \(b\leq a\) coordinatewise: roots can only change from \(1\) to \(0\), and any required root changes are allowed.
Along such a sequence, each leaf’s preferred value is nonincreasing.
These choices are simultaneously realizable for all leaves: perform the required early leaf flips, then the root flips, then the required late leaf flips. Leaves do not affect other preferences.
If there are \(q\) leaves and \(\Delta(a,b)\) of them have different preferred values at the two root assignments, this proves
\(R(N)=\sum_{b\leq a}3^{q-\Delta(a,b)}4^{\Delta(a,b)}.\)
This identity counts reachable endpoint pairs, rather than sequences; the simultaneous construction proves existence for every counted pair.
We reduce from the classical \(\mathrm{NP}\)-complete Independent Set problem: given an explicitly represented simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether it has an independent set of size at least \(k\). We may restrict to \(n=|V|\geq1\) and \(1\leq k\leq n\).
Write \(e=|E|\), and define
\(u=e+1,\qquad v=(e+1)(n+1),\qquad W=(e+1)(n+1)^2,\qquad s=4(n+2).\)
Construct a CP-net \(N_G\) with roots \(X_1,\ldots,X_n,A\), each preferring \(1\) to \(0\), and the following distinct leaf features:
| Leaf preferred value | Number of copies |
|---|---:|
| \(X_i\wedge X_j\), for each edge \(\{i,j\}\) | \(s\) |
| \(X_i\), for each vertex \(i\) | \(su\) |
| \(A\wedge X_i\), for each vertex \(i\) | \(sv\) |
| \(A\) | \(sW\) |
The total number of leaves is
\(q=se+sun+svn+sW=s(2W-1),\)
where the last equality follows from \(e+un+vn=W-1\).
For a reachable ordered root pair, each vertex root has one of three endpoint patterns. Let
\(D=\{i:(X_i^{\mathrm{initial}},X_i^{\mathrm{final}})=(1,0)\},\)
\(T=\{i:(X_i^{\mathrm{initial}},X_i^{\mathrm{final}})=(1,1)\}.\)
All remaining vertex roots have pattern \((0,0)\). Put \(d=|D|\), \(t=|T|\), and define
\(b(D,T)=|\{\{i,j\}\in E:i,j\in D\cup T,\ \{i,j\}\cap D\neq\varnothing\}|.\)
The edge-conjunction leaves change preferred value exactly on these edges. The singleton vertex leaves change exactly for vertices in \(D\).
For the anchor-dependent leaves, there are three cases:
| Anchor endpoint pattern | Vertices whose \(A\wedge X_i\) leaves change | Do the \(A\)-leaves change? |
|---|---|---|
| \((0,0)\) | None | No |
| \((1,1)\) | \(D\) | No |
| \((1,0)\) | \(D\cup T\) | Yes |
It follows that \(\Delta=sj\), where
\(j=b(D,T)+ud\quad\text{if the anchor pattern is }(0,0),\)
\(j=b(D,T)+ud+vd\quad\text{if the anchor pattern is }(1,1),\)
\(j=W+b(D,T)+ud+v(d+t)\quad\text{if the anchor pattern is }(1,0).\)
Since \(b(D,T)\leq e\), \(d\leq n\), and \(d+t\leq n\), every exponent satisfies \(0\leq j\leq2W-1\). The first two cases have \(j<W\).
Let \(a_j\) count the root endpoint patterns producing exponent \(j\). There are exactly \(3^{n+1}\) root endpoint patterns, so
\(\sum_{j=0}^{2W-1}a_j=3^{n+1}.\)
The counting identity now gives
\(R(N_G)=\sum_{j=0}^{2W-1}a_j\,3^{q-sj}4^{sj}.\)
Set \(B=(\frac43)^s\). Since \((\frac43)^4>3\),
\(B>3^{n+2}>3^{n+1}.\)
Thus
\(\frac{R(N_G)}{3^q}=\sum_{j=0}^{2W-1}a_jB^j\)
has uniquely recoverable nonnegative integer coefficients. Although \(B\) need not be an integer, coefficient recovery is exact.
After coefficients above \(j\) have been subtracted, divide the residual by \(B^j\). The contribution from lower coefficients satisfies
\(0\leq\sum_{i<j}a_iB^{i-j}\leq\frac{\sum_{i<j}a_i}{B}\leq\frac{3^{n+1}}{B}<1.\)
Taking the floor therefore gives precisely \(a_j\), proving recovery inductively from the largest exponent downwards.
An entirely integer implementation uses the weights
\(T_j=3^{q-sj}4^{sj}.\)
Starting with residual \(R(N_G)\), compute \(a_j\) by integer division by \(T_j\), then subtract \(a_jT_j\). The same inequality proves every division returns the correct coefficient.
Consider
\(J=W+uk+vk.\)
Because \(J\geq W\), only anchor pattern \((1,0)\) can contribute. Its exponent equation is
\(J=W+b(D,T)+ud+v(d+t).\)
The representation \(b+ud+vz\), with
\(0\leq b\leq e,\qquad0\leq d,z\leq n,\)
is unique: reduction modulo \(u=e+1\) determines \(b\), and division by \(u\), followed by reduction modulo \(n+1\), determines \(d\) and then \(z\).
Consequently, contributing patterns must satisfy
\(b(D,T)=0,\qquad d=k,\qquad d+t=k.\)
Hence \(T=\varnothing\), and \(b(D,\varnothing)=0\) says exactly that \(D\) contains no edge. Conversely, every independent set \(D\) of size \(k\), with \(T=\varnothing\) and anchor pattern \((1,0)\), contributes once.
Therefore
\(a_J=|\{D\subseteq V:|D|=k,\ D\text{ is independent}\}|.\)
A graph has an independent set of size at least \(k\) exactly when it has one of size \(k\). Thus the Independent Set instance is positive exactly when \(a_J>0\).
Applying Section 1 to \(N_G\) produces two equally weighted types. One exact evaluation of their \(D\) recovers \(R(N_G)\); Sections 4–5 then decide Independent Set. This completes the hardness reduction.
The reduction produces
\(m=n+2+q=O((e+1)(n+1)^3),\qquad\tau=2.\)
Each feature has at most two parents and at most four explicitly listed table rows. Consequently, the constructed input has \(L=O(m\log m)\) under ordinary indexed-feature encoding. Since \(e\leq\binom n2\), construction size is polynomial in the Independent Set input size.
All coefficient-recovery integers have \(O(m)\) bits. Recovery uses \(O(W)\) integer divisions and multiplications, and can be implemented in \(O(Wm^2)\) bit operations using schoolbook arithmetic. Recovering \(C(N_G)\) from \(D\) also requires only polynomial-time arithmetic on \(O(m)\)-bit integers. Hence this is a polynomial-time, one-query reduction.
For arbitrary inputs, an exact exhaustive algorithm takes
\(4^m\,\operatorname{poly}(m,\tau,L)\)
time: enumerate the worsening-flip graph for each type, compute reachability from every outcome, scan outcome pairs for every type pair, and sum the resulting rational distances.
Output size is polynomial. Each distance has denominator at most \(2\binom{2^m}{2}\) before reduction. A common denominator for the weighted sum therefore has \(O(L+\tau^2m)\) bits, using the squared product of input mass denominators and the product of pairwise distance denominators.
Thus hardness is not caused by an inherently exponential output representation.
[Proposition 3.2 of the cited paper](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p955.pdf) asserts hardness of deciding zero distance. Under the hypotheses here, however, zero distance is polynomial-time decidable.
To see this, consider outcomes differing only at feature \(X\). Along any worsening path between them, no ancestor of \(X\) can change. Prove this inductively in topological order over those ancestors: once a feature’s parents remain fixed, its strict binary preference remains fixed, so it can undergo at most one worsening flip; equal endpoint values then force no flip.
Therefore \(X\)’s parent context remains fixed, and the orientation of this adjacent pair is exactly its listed local preference.
It follows that two nets have zero distance exactly when their local preference functions agree everywhere. For each feature, compare all pairs of rows from the two tables whose contexts agree on shared parents. Such contexts extend to a common assignment, so their preferred values must agree; checking every compatible row pair is also sufficient. This takes \(O(mL^2)\) time for two explicitly represented nets.
With genuine dependencies, equal local functions have equal parent sets, because the parents are precisely the essential arguments of those functions. Hence distinct types in the present support have positive pairwise distance.
The hardness proof above establishes hardness of exact values independently of the zero-distance assertion.
⟨structured verdict parsed — rendered above⟩
The argument establishes NP-hardness under a polynomial-time, one-query reduction, even for two equally weighted types with dependency graphs of depth one and maximum indegree two. I found no mathematical gaps or false steps.
This verdict uses the prover’s explicitly stated output convention: an exact rational encoded by binary numerator and denominator. The distinction from a terminating binary expansion is correctly identified and supported by the example given.
The argument that an acyclic dependency graph yields an acyclic worsening-flip graph is valid. In the described conditional lexicographic order, a worsening flip leaves all earlier features unchanged, including the flipped feature’s parents, and strictly decreases the outcome at the first changed feature. Consequently, a comparable pair has a unique orientation.
The isolated-feature construction is valid. Projecting a path onto either component preserves reachability, allowing zero-length projected paths. Conversely, component paths can be concatenated because the components do not affect each other’s preferences.
The pair classification is exhaustive and its counts are correct:
Thus the numerator and denominator are respectively \(Q+C\) and \(Q+4C\), and
\[
\mathrm{KTD}(A,B)=\frac{Q+C}{Q+4C}.
\]
With equal masses, the two off-diagonal terms give
\[
D=\frac{Q+C}{2(Q+4C)}.
\]
The inversion
\[
C=Q\frac{1-2D}{8D-1}
\]
is algebraically correct. Its denominator cannot vanish because
\[
8D-1=\frac{3Q}{Q+4C}>0.
\]
Finally, \(R(N)=Q+C(N)\) correctly counts reflexively reachable ordered pairs: each outcome contributes its reflexive pair, and each comparable unordered pair contributes exactly one directed pair.
Assessment: Correct.
The root endpoint condition \(b\leq a\) is necessary and sufficient for root reachability, since every root can only worsen from \(1\) to \(0\).
Conjunction preferences are nonincreasing along every root path. Therefore:
The simultaneous scheduling argument is sufficient: leaves influence no other preferences, so required early flips, root flips, and required late flips can be performed in those three phases without interference.
The resulting identity
\[
R(N)=\sum_{b\leq a}3^{q-\Delta(a,b)}4^{\Delta(a,b)}
\]
counts endpoint pairs rather than paths. Different root endpoint pairs are disjoint counting categories, and the product within each category counts independent leaf endpoint choices.
Assessment: Correct, including the cases of unchanged roots and unchanged leaf endpoints.
The source decision problem is stated precisely. Restricting to \(n\geq1\) and \(1\leq k\leq n\) excludes only trivial cases and does not affect hardness.
Every constructed dependency is genuine. For a conjunction leaf, fixing all other parents to \(1\) makes changing the remaining parent change the preferred value. Singleton leaves also depend genuinely on their sole parent. The graph is acyclic, has depth one, and has maximum indegree two.
The leaf-count arithmetic is correct:
\[
e+un+vn=W-1,
\qquad
q=s(e+un+vn+W)=s(2W-1).
\]
The sets \(D\) and \(T\) represent disjoint root endpoint patterns. The quantity \(b(D,T)\) correctly counts edge conjunctions that start at \(1\) and finish at \(0\): both endpoints must initially be \(1\), and at least one must fall to \(0\).
All three anchor cases are correctly enumerated. Their exponents are exactly those stated. The bounds follow from
\[
b(D,T)\leq e,\qquad d\leq n,\qquad d+t\leq n.
\]
In particular, the first two cases satisfy \(j<W\), and every case satisfies \(0\leq j\leq2W-1\).
There are precisely \(3^{n+1}\) root endpoint patterns, so the coefficient sum and the expression for \(R(N_G)\) are correct.
Assessment: Correct.
The noninteger base causes no gap.
With \(s=4(n+2)\), the inequality
\[
\left(\frac43\right)^4>3
\]
indeed implies
\[
B=\left(\frac43\right)^s>3^{n+2}>3^{n+1}.
\]
After higher coefficients have been removed, dividing by \(B^j\) leaves \(a_j\) plus a nonnegative lower-order contribution strictly below \(1\). The bound uses the established total coefficient count, so taking the floor recovers \(a_j\) exactly. At \(j=0\), the lower-order sum is empty.
The integer implementation is equivalent because
\[
T_j=3^qB^j=3^{q-sj}4^{sj}
\]
is an integer throughout the stated index range. Integer division therefore implements the same floor operation.
Assessment: Correct. No integrality assumption on \(B\) is needed.
The target index
\[
J=W+uk+vk
\]
lies within the available coefficient range for \(1\leq k\leq n\). Since \(J\geq W\), only the falling-anchor case can contribute.
The mixed-radix uniqueness argument is valid:
Matching the target index therefore forces
\[
b(D,T)=0,\qquad d=k,\qquad d+t=k.
\]
Hence \(T=\varnothing\), and \(b(D,\varnothing)=0\) is exactly the condition that \(D\) is independent.
Each independent set of size \(k\) contributes once, so the asserted interpretation of \(a_J\) is correct. The equivalence between having an independent set of size at least \(k\) and having one of size exactly \(k\) is valid.
Assessment: Correct. This completes the claimed one-query hardness reduction.
The constructed feature count
\[
m=n+2+q=O((e+1)(n+1)^3)
\]
is correct. Each feature has a constant-size preference table and at most two indexed parents, giving \(L=O(m\log m)\) under the stated ordinary encoding. The masses are valid positive binary rationals, and the two support types are distinct.
The arithmetic bounds are justified:
The exhaustive upper bound
\[
4^m\,\operatorname{poly}(m,\tau,L)
\]
is consistent with computing reachability from every outcome in each worsening-flip graph and then scanning outcome pairs for all type pairs.
The output-size argument is also correct. Each distance admits a denominator bounded by
\[
2\binom{2^m}{2},
\]
and the proposed common denominator has \(O(L+\tau^2m)\) bits. Since the weighted value lies between \(0\) and \(1\), its numerator has a corresponding polynomial bit bound.
Assessment: Correct. The reduction is polynomial in the explicitly represented input size, and hardness does not arise from exponentially long output.
The claimed example is correct. For the two separable four-feature types, the disagreement numerator is \(27\) and the comparable-pair union has size \(84\). Equal weighting therefore gives
\[
D=\frac{27}{2\cdot84}=\frac9{56}.
\]
This fraction has no terminating binary expansion. The prover explicitly states the numerator-and-denominator interpretation needed for the exact-output task; this is not a hidden assumption.
The cited [Proposition 3.2](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p955.pdf) does assert zero-distance hardness. The prover accurately reports that assertion.
Its independent zero-distance argument is nevertheless valid under the present hypotheses. For adjacent outcomes differing only at \(X\), the induction over ancestors correctly prevents any ancestor from changing along a worsening path. Thus \(X\)’s parent context stays fixed, and the adjacent pair’s orientation is exactly its local preference.
Consequently, equality of all local preference functions is necessary for zero distance. It is sufficient because equal local functions give identical worsening-flip graphs. Comparing compatible table rows checks equality without expanding assignments to the union of parent sets, and the stated polynomial bound is valid.
The final claim about genuine dependencies is also correct: the parent set is exactly the set of essential arguments of the local preference function.
Assessment: Correct. There is a genuine conflict with the published assertion, but the exact-value hardness reduction does not use it, and the prover supplies a sufficient argument for its own zero-distance claim.
No major or minor issues require repair. The conclusion should retain its stated reduction type and exact-rational encoding convention, as the prover already does.
⟨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.