Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even with \(\tau=3\), fixed masses, and \(|M|=1\).
Theorem 18 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor $\gag^m$, determining \moves of a single iteration of \alg coNP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an agenda \(\mathcal A\), constraint \(\Gamma\), an explicitly supported rational distribution \(\mu\) over complete rational judgments, and an occupied type \(J\), compute the set of best improving destinations \(K\in\operatorname{CH}(\operatorname{supp}\mu)\) with \(d_m(J,K)=1\), rationality, \(D_\mu(K)<D_\mu(J)\), and minimum \(D_\mu(K)=\sum_L\mu_Ld_m(K,L)\) among admissible destinations.
Let \(\mathcal A\) be an agenda of \(m\) propositional variables and \(\Gamma\) a satisfiable propositional formula over them, supplied as a formula rather than an explicit model list. Rational judgments are complete assignments satisfying \(\Gamma\).
The model graph has all rational judgments as vertices. Distinct vertices \(X,Y\) are adjacent exactly when no rational \(Z\notin\{X,Y\}\) agrees with them on every issue on which \(X\) and \(Y\) agree. Let \(d_m\) denote shortest-path distance in this graph, and \(\operatorname{CH}(S)\) the smallest vertex set containing \(S\) and closed under all shortest paths between its vertices.
A society is given by its support: the list \(S\) of the \(\tau\) distinct types with positive mass, each with its mass as a binary rational. Here types are rational judgments, \(\tau=|S|\) is the support size rather than the number of possible judgments, and \(\sum_{X\in S}\mu_X=1\). Let \(L\) be the total input bit length, including \(\Gamma\), judgments, and masses; state running times in \(m,\tau,L\).
Given an occupied type \(J\in S\), set \(D_\mu(K)=\sum_{X\in S}\mu_Xd_m(K,X)\) and \(B=\{K\in\operatorname{CH}(S):K\models\Gamma,\ d_m(J,K)=1,\ D_\mu(K)<D_\mu(J)\}\). Compute \(M=\operatorname*{arg\,min}_{K\in B}D_\mu(K)\), retaining all ties and taking \(M=\varnothing\) when \(B=\varnothing\). The moving individual has zero mass, so the objective includes the entire mass at \(J\).
Can \(M\) be computed in time polynomial in \(m,\tau,L\), or is this computation \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
For finite agent lists, computing a single model-graph iteration's move set is reported \(\mathrm{coNP}\)-hard; testing model-graph adjacency of two supplied rational judgments is reported \(\mathrm{coNP}\)-complete. [Source](https://home.ipipan.waw.pl/w.jamroga/papers/iterativeJA16ecai.pdf)
No result settling this exact distributional destination problem was found in the literature search.
Computing \(M\) is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even when \(\tau=3\), the masses are fixed constants, and \(M\) always contains exactly one judgment.
The proof below directly handles the specified distributional objective, including the entire mass at \(J\). It does not rely on transferring the finite-agent hardness claim from the [cited paper](https://home.ipipan.waw.pl/w.jamroga/papers/iterativeJA16ecai.pdf).
Let \(\varphi(x_1,\ldots,x_n)\) be an instance of propositional satisfiability. Introduce three additional variables \(s,p,q\), giving \(m=n+3\) issues. Write judgments in the coordinate order \((s,p,q,x_1,\ldots,x_n)\).
Define three distinguished judgments:
For each satisfying assignment \(a\) of \(\varphi\), define a witness judgment \(W_a=(0,1,0,a)\). Let \(\mathcal W\) be the set of these witnesses.
Construct the formula
\( \Gamma= (\neg s\land\neg p\land\neg q\land\bigwedge_{i=1}^{n}\neg x_i) \lor (\neg s\land p\land q\land\bigwedge_{i=1}^{n}x_i) \lor (s\land\neg p\land q\land\bigwedge_{i=1}^{n}\neg x_i) \lor (\neg s\land p\land\neg q\land\varphi). \)
The four branches have distinct assignments to \((s,p,q)\). Consequently, the rational judgments are exactly \(\{J,Y,H\}\cup\mathcal W\). In particular, \(\Gamma\) is satisfiable regardless of whether \(\varphi\) is satisfiable.
Set \(S=\{J,Y,H\}\), with masses
\(\mu_J=\frac14\), \(\mu_Y=\frac12\), and \(\mu_H=\frac14\).
The occupied type from which movement is computed is \(J\).
By definition, a third rational judgment blocks an edge precisely when it agrees with the two endpoints on every coordinate on which they agree.
The edges \(JH\) and \(HY\) always exist.
For \(J,H\), the coordinate \(p\) is a shared zero. Every other rational judgment—\(Y\) or a witness—has \(p=1\), so none can block this edge.
For \(H,Y\), the coordinate \(q\) is a shared one. Every other rational judgment—\(J\) or a witness—has \(q=0\), so none can block this edge.
Thus \(d_m(J,H)=d_m(H,Y)=1\).
The edge \(JY\) exists exactly when \(\varphi\) is unsatisfiable.
The only coordinate on which \(J,Y\) agree is \(s=0\). Every witness has \(s=0\), whereas \(H\) has \(s=1\). Therefore a blocking third judgment exists exactly when \(\mathcal W\ne\varnothing\). Hence:
No witness is adjacent to \(H\).
Fix \(W_a\in\mathcal W\). Its first three coordinates all differ from those of \(H\). Among the remaining coordinates, \(H,W_a\) agree exactly where \(a_i=0\). The judgment \(J\) has zero on all these coordinates and is distinct from both endpoints. Thus \(J\) blocks the edge \(HW_a\).
In particular, if \(W_a\) is adjacent to \(J\), then \(d_m(H,W_a)=2\): adjacency to \(H\) is excluded, and \(H,J,W_a\) is a path of length two.
Suppose \(\varphi\) is unsatisfiable. The model graph consists of the triangle on \(J,Y,H\). Since all its vertices belong to \(S\), its convex hull is \(S\).
The objective values, using the full specified mass at \(J\), are
\( D_\mu(J)=\frac12+\frac14=\frac34,\qquad D_\mu(Y)=\frac14+\frac14=\frac12,\qquad D_\mu(H)=\frac14+\frac12=\frac34. \)
Both \(Y,H\) are adjacent to \(J\), but only \(Y\) strictly improves the objective. Therefore \(B=M=\{Y\}\).
Suppose \(\varphi\) is satisfiable. The established distances give
\( D_\mu(J)=\frac12\cdot2+\frac14\cdot1=\frac54, \qquad D_\mu(H)=\frac14\cdot1+\frac12\cdot1=\frac34. \)
Because \(H\in S\subseteq\operatorname{CH}(S)\) and \(H\) is adjacent to \(J\), this strict improvement establishes \(H\in B\).
It remains to exclude every other neighbor of \(J\). The judgment \(Y\) is not adjacent to \(J\), and the only remaining possible neighbors are witnesses.
Let \(W_a\) be any witness adjacent to \(J\). Section 2 proves \(d_m(W_a,H)=2\). Also \(W_a\ne Y\), so \(d_m(W_a,Y)\geq1\). Consequently,
\( D_\mu(W_a) =\frac14\cdot1+\frac12d_m(W_a,Y)+\frac14\cdot2 \geq\frac14+\frac12+\frac12 =\frac54 =D_\mu(J). \)
Thus no witness neighbor strictly improves the objective, whether or not it belongs to the hull. We have proved \(B=M=\{H\}\).
The construction therefore satisfies
\( \varphi\text{ satisfiable}\ \Longleftrightarrow\ M=\{H\}, \qquad \varphi\text{ unsatisfiable}\ \Longleftrightarrow\ M=\{Y\}. \)
With ordinary binary variable identifiers, construction time and resulting input length are \(O(|\varphi|+n\log(n+2))\). The parameters are \(m=n+3\), \(\tau=3\), and \(L=O(|\varphi|+n\log(n+2))\). All masses have constant encoding length, and the output is always one judgment of length \(m\).
A polynomial-time Turing reduction decides satisfiability by constructing this instance, making one call to an algorithm computing \(M\), and checking whether its unique returned judgment is \(H\). Therefore a running time polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
As a computational cross-check, all \(278\) possible witness subsets for \(0\leq n\leq3\) were enumerated; their graphs, hulls, and move sets matched the proved alternatives. The proof above covers arbitrary \(n\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem: computing \(M\) is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even with support size \(\tau=3\), fixed masses, and a singleton output. I found no major or minor issues.
The three distinguished judgments have different \((s,p,q)\) coordinates. Each of the first three branches of \(\Gamma\) specifies exactly its corresponding distinguished judgment. The fourth branch specifies exactly the judgments \(W_a\) for satisfying assignments \(a\) of \(\varphi\).
Thus the claimed model set \(\{J,Y,H\}\cup\mathcal W\) is exact. No witness coincides with a distinguished judgment. In particular, \(\Gamma\) is always satisfiable, and all three supplied support judgments are rational.
The masses are positive binary rationals and sum to one. The designated judgment \(J\) belongs to the support. Hence the reduction produces valid instances under every satisfiability outcome.
Edge \(JH\). Both endpoints have \(p=0\), whereas every other model has \(p=1\). Therefore no third model agrees with the endpoints on every shared coordinate. The edge exists.
Edge \(HY\). Both endpoints have \(q=1\), whereas every other model has \(q=0\). The same reasoning establishes this edge.
Edge \(JY\). Their only shared coordinate is \(s=0\): the coordinates \(p,q\) differ, and each \(x_i\) differs. Every witness has \(s=0\), and \(H\) has \(s=1\). Consequently, a blocker exists exactly when \(\mathcal W\) is nonempty.
It follows that \(d_m(J,Y)=1\) when \(\varphi\) is unsatisfiable. When \(\varphi\) is satisfiable, the missing edge rules out distance one, and the path through \(H\) establishes distance two.
Nonadjacency of \(H,W_a\). Their first three coordinates all differ. They share precisely those remaining coordinates where \(a_i=0\). The judgment \(J\) agrees on every such coordinate and is distinct from both endpoints. Thus it blocks the edge.
This remains valid when there are no shared coordinates: agreement on the empty set is vacuous.
For a witness adjacent to \(J\), the path \(H,J,W_a\), together with nonadjacency to \(H\), proves \(d_m(H,W_a)=2\).
All stated graph properties follow directly from the supplied adjacency definition.
There are exactly three models, and all three pairwise edges exist. Since the support already contains every vertex, its convex hull equals \(S\).
The objective calculations are correct:
\[ D_\mu(J)=\frac34,\qquad D_\mu(Y)=\frac12,\qquad D_\mu(H)=\frac34. \]
Both alternative support judgments are neighbors of \(J\), but only \(Y\) strictly improves the objective. Therefore \(B=M=\{Y\}\). The strict inequality correctly excludes \(H\).
The established distances give
\[ D_\mu(J)=\frac54,\qquad D_\mu(H)=\frac34. \]
Since \(H\) belongs to the support, it belongs to its convex hull. Its adjacency to \(J\) and strict objective improvement establish \(H\in B\).
The enumeration of other possible neighbors is exhaustive: \(Y\) is not adjacent to \(J\), and every remaining model is a witness.
For every witness adjacent to \(J\),
\[ d_m(W_a,J)=1,\qquad d_m(W_a,H)=2,\qquad d_m(W_a,Y)\geq1. \]
The last distance is finite because the established edges give a path from \(W_a\) through \(J,H\) to \(Y\). The witness is distinct from \(Y\), so the lower bound is valid.
Consequently,
\[ D_\mu(W_a) \geq \frac14+\frac12+\frac12 =\frac54 =D_\mu(J). \]
No witness neighbor satisfies the required strict improvement. This exclusion applies regardless of hull membership, so no further characterization of the hull is needed. Thus \(B=M=\{H\}\).
The full mass at \(J\) is included throughout, exactly as the task requires.
The formula construction uses one copy of \(\varphi\) and a linear number of additional literals. The stated bound \(O(|\varphi|+n\log(n+2))\) is valid with ordinary binary variable identifiers. The support has three judgments, masses have constant encoding length, and the output contains exactly one judgment of length \(m=n+3\).
One call to an exact algorithm computing \(M\), followed by comparison with \(H\), decides satisfiability. This is a polynomial-time Turing reduction from propositional SAT. Therefore an algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
The singleton output also eliminates any output-size obstruction as the explanation for this hardness.
The construction works for \(n=0\): the distinguished judgments remain distinct, empty conjunctions have their usual interpretation, and the blocking arguments remain valid.
I independently enumerated all \(278\) witness subsets for \(0\leq n\leq3\), computed adjacency, shortest-path distances, convex hulls, and move sets, and confirmed both claimed singleton outcomes. This supports the reported check; the general conclusion rests on the proof above.
No repair or additional 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.