Answer: \(\mathrm{NP}\text{-hard}\)
Corollary 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet (G, ◦) be an InfNet. Finding a stable update sequence σ with |{v ∈V (G) | ◦[G, σ](v) = 0}| ≥1 is NP- hard and W[2]-hard with respect to |σ|. Finally, using a reduction from MAX 2-SAT we show that 3-OPT-SEQ remain hard even if every node has degree three.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many roles \(R\), rational masses \(p_r\) summing to \(1\), an initial distribution \(x_{r,a}\) over \(a\in\{b,w,g\}\), a symmetric rational interaction matrix \(W\), and a rational target \(q>0\), does there exist a finite legal mass-transfer schedule ending in a stable state with total black mass at least \(q\)? A transfer of mass \(\delta\) from opinion \(a\) to \(a'\) in role \(r\) is legal when \(a'\)'s exposure \(E_{r,a'}(x)=\sum_s W_{rs}x_{s,a'}\) exceeds half the total exposure \(D_r=\sum_s W_{rs}p_s\) throughout the transfer; stability requires no occupied role-opinion cell to have another opinion above that threshold.
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts supported types, not possible types.
The opinions are \(A=\{b,w,g\}\). Input also specifies initial opinions \(o_t\in A\), a symmetric binary-rational matrix \(P\in[0,1]^{T\times T}\), a binary-rational threshold \(q\in[0,1]\), and a binary-encoded integer \(K\geq0\).
Require the graph with edges \(\{t,u\}\) for distinct types satisfying \(P_{tu}>0\) to be connected; let \(m\) be its number of edges. Diagonal entries represent interactions within a type and may be positive; no row normalization is imposed.
A state has rational masses \(z_{t,a}\geq0\) satisfying \(\sum_{a\in A}z_{t,a}=\mu_t\), initially \(z_{t,o_t}=\mu_t\) and all other entries zero. Write \(H_{t,a}=\sum_{u\in T}P_{tu}z_{u,a}\).
One move chooses \(t\in T\), distinct \(i,j\in A\), and rational \(0<\delta\leq z_{t,i}\), then transfers \(\delta\) from \(z_{t,i}\) to \(z_{t,j}\), provided \(H_{t,j}>\frac12\sum_{a\in A}H_{t,a}\) immediately before the move. Each transfer counts as one step, regardless of its mass; equality permits no move.
A state is stable if, for every \(z_{t,i}>0\) and every \(j\neq i\), \(H_{t,j}\leq\frac12\sum_{a\in A}H_{t,a}\). Acceptance requires reaching such a state in at most \(K\) moves with \(\sum_{t\in T}z_{t,b}\geq q\); the empty sequence is allowed.
Let \(L\) be the total input bit length. State running times in \(m,\tau,L,K\), accounting for the binary encoding of \(K\).
Is this continuous reachability problem solvable in polynomial time in the input bit length, or is it \(\mathrm{NP}\)-hard?
For finite agents on connected simple undirected graphs, strict-majority stable reachability with a black-count threshold is \(\mathrm{NP}\)-hard and \(\mathrm{W}[2]\)-hard parameterized by sequence length, even with two initially black agents and three initially unstable agents. [Verified discrete result](https://www.ijcai.org/proceedings/2020/0225.pdf)
No result settling the exact rational-mass problem above was located in the literature search.
The problem is \(\mathrm{NP}\)-hard, even when \(K\leq\tau\) and all masses, matrix entries, and the threshold are dyadic rationals. The reduction below allows arbitrary partial transfers; its reverse direction does not assume that types remain monochromatic.
Consequently, a polynomial-time algorithm in the total input bit length would imply \(\mathrm{P}=\mathrm{NP}\).
We reduce from Set Cover, whose NP-completeness is classical. [Karp’s original theorem](https://doi.org/10.1007/978-1-4684-2001-2_9)
An instance consists of a universe \(U=\{u_1,\ldots,u_\ell\}\), sets \(S_1,\ldots,S_n\subseteq U\), and a budget \(h\). The question is whether at most \(h\) sets cover \(U\).
We may restrict to instances satisfying
\[ \ell\geq1,\qquad n\geq1,\qquad \bigcup_{j=1}^{n}S_j=U,\qquad 0\leq h\leq n. \]
Indeed, an empty universe and an uncovered element can be handled directly, mapping respectively to fixed yes- and no-instances satisfying these restrictions; replacing \(h\) by \(\min(h,n)\) preserves the answer.
Write \(d_i=|\{j:u_i\in S_j\}|\), so \(1\leq d_i\leq n\), and let \(I=\sum_i d_i\).
For any society state, define the constant row total
\[ M_t=\sum_{v\in T}P_{tv}\mu_v. \]
Because each type retains its total mass, \(M_t=\sum_{a\in A}H_{t,a}\) throughout every sequence. Thus a transfer into opinion \(a\) requires \(2H_{t,a}>M_t\).
Choose
\[ r=\left\lceil\log_2(16(n+2))\right\rceil,\qquad s=\left\lceil\log_2(4\ell)\right\rceil,\qquad e=2^{-r},\qquad f=2^{-(r+s)}. \]
Put \(\varepsilon=(n+2)e+\ell f\). These choices give
\[ (n+2)e\leq\frac1{16},\qquad \ell f\leq\frac e4,\qquad \varepsilon<\frac18. \]
Create the following supported types:
| Types | Mass of each type | Initial opinion |
|---|---:|---|
| \(x_j\), one for each \(S_j\) | \(e\) | \(w\) |
| \(y_i\), one for each \(u_i\) | \(f\) | \(b\) |
| \(W\) | \(1/4\) | \(w\) |
| \(G\) | \(1/4\) | \(g\) |
| \(B\) | \(1/4\) | \(b\) |
| \(R\) | \(1/4-\varepsilon\) | \(w\) |
| \(C\) | \(e\) | \(g\) |
| \(D\) | \(e\) | \(w\) |
All masses are positive and their sum is \(1\). The types \(C,D\) serve as clocks.
Set \(P_{tt}=1\) for every \(x_j\) and for \(W,G,B,R\). All other diagonal entries are zero. Specify the nonzero off-diagonal entries symmetrically as follows:
| Unordered pair | Entry |
|---|---:|
| \(\{x_j,C\}\), \(\{x_j,D\}\), for every \(j\) | \(1\) |
| \(\{y_i,x_j\}\), whenever \(u_i\in S_j\) | \(1\) |
| \(\{C,W\}\), \(\{D,G\}\), \(\{W,R\}\) | \(1\) |
| \(\{y_i,W\}\), for every \(i\) | \(4e\) |
| \(\{y_i,B\}\), for every \(i\) | \(4d_i e\) |
Every unspecified entry is zero. Since \(d_i\leq n\) and \(e\leq1/(16(n+2))\), all entries lie in \([0,1]\).
Finally, set
\[ q=\frac14+\ell f,\qquad K=h+2. \]
The threshold \(q\) is exactly the initial total black mass.
The support graph is connected. Every \(x_j\) joins both clocks, \(W\) joins \(C\), \(G\) joins \(D\), and \(R\) joins \(W\). Each \(y_i\) has a neighboring \(x_j\), because \(d_i\geq1\), and \(B\) joins every \(y_i\).
Suppose there were a first move at one of \(W,G,B,R\).
Immediately before that move, these four types still have their initial opinions. At each of \(W,G,B\), the diagonal contributes \(1/4\) to its current opinion. Its neighbors outside the four anchors have total mass at most \(\varepsilon<1/8\). The only interaction between distinct anchors is \(\{W,R\}\), and both have opinion \(w\).
Consequently, at \(W,G,B\), any different opinion has field strictly smaller than the current opinion’s field. It therefore cannot have a strict majority. At \(R\), its only distinct neighbor is \(W\), so every interaction supports its current opinion \(w\).
The purported first move is impossible. Hence all four anchors remain unchanged.
Suppose there were a first transfer into \(b\). Before it, every \(x_j,C,D\) has zero black mass; the monitors \(y_i\) may have lost black mass.
Let \(a_j=|\{i:u_i\in S_j\}|\), the number of monitor neighbors of \(x_j\). At \(x_j\),
\[ H_{x_j,b}\leq a_j f\leq\ell f\leq\frac e4, \qquad M_{x_j}=3e+a_jf\geq3e. \]
Thus black cannot have a strict majority there.
At either clock, the black field is zero: its neighbors are set types and its nonblack anchor.
At a monitor \(y_i\), its only black contribution is from the fixed anchor \(B\). Therefore
\[ H_{y_i,b}=d_i e,\qquad M_{y_i}=(2d_i+1)e, \]
so again \(2H_{y_i,b}<M_{y_i}\). The anchors cannot move by the preceding lemma.
This excludes every possible location of the first transfer into black. Therefore no such transfer occurs, and total black mass is nonincreasing.
Since its initial value equals \(q\), an accepting sequence cannot lose any black mass. In particular, every monitor \(y_i\) remains entirely black throughout an accepting sequence.
The neighbors of \(C\) are \(W\) and the \(n\) set types. At every state,
\[ H_{C,w}\geq\frac14,\qquad H_{C,g}+H_{C,b}\leq ne<\frac14. \]
Thus \(w\) always has a strict majority at \(C\). Stability forces all of \(C\)’s mass to have opinion \(w\).
Likewise, \(g\) always has a strict majority at \(D\), and stability forces \(D\) to be entirely gray.
Because \(C\) starts gray and \(D\) starts white, any sequence reaching a stable state contains at least one move at each clock.
Suppose \(J\subseteq\{1,\ldots,n\}\) indexes a cover with \(|J|\leq h\). Perform these moves:
Both clock moves are legal by Section 3.3.
During the set-type moves, both clocks are entirely gray. Immediately before the move at \(x_j\), that type is still entirely white, and all its monitor neighbors are black. Hence
\[ H_{x_j,g}=2e,\qquad H_{x_j,w}=e,\qquad H_{x_j,b}=a_jf. \]
Since \(a_jf\leq e/4\),
\[ 2H_{x_j,g}=4e>3e+a_jf=M_{x_j}, \]
so the move is legal.
We now verify stability of the resulting state.
The anchors remain stable, and both clocks have their permanently favored opinions. At every set type, one clock is white and the other is gray. Its current opinion receives \(2e\): \(e\) from its diagonal and \(e\) from the matching clock. The other nonblack opinion receives \(e\), and black receives at most \(e/4\). Thus its current opinion has a strict majority, and the type is stable.
For a monitor \(y_i\), let
\[ c_i=|\{j\in J:u_i\in S_j\}|. \]
Because \(J\) covers \(U\), \(1\leq c_i\leq d_i\). Its final fields are
\[ H_{y_i,w}=(d_i-c_i+1)e,\qquad H_{y_i,g}=c_i e,\qquad H_{y_i,b}=d_i e. \]
Each is at most \(d_i e\), whereas
\[ \frac{M_{y_i}}2=\left(d_i+\frac12\right)e. \]
No opinion has a strict majority at the monitor, so its retained black mass is stable.
The final black mass is exactly \(q\), and the sequence has \(|J|+2\leq h+2=K\) moves. It is accepting.
Suppose an accepting sequence has at most \(h+2\) moves. By Section 3.2, every monitor retains all its black mass. By Section 3.3, at least two moves occur at the clocks.
Let \(J\) be the indices of set types at which at least one move occurs. Each distinct such type consumes a move, so
\[ |J|\leq h. \]
We claim that these sets cover \(U\).
Otherwise, choose an element \(u_i\) belonging to no set indexed by \(J\). Every set-type neighbor of \(y_i\) was untouched and remains entirely white. At the final state,
\[ H_{y_i,w}=(d_i+1)e,\qquad H_{y_i,g}=0,\qquad H_{y_i,b}=d_i e. \]
Therefore
\[ 2H_{y_i,w}=2(d_i+1)e>(2d_i+1)e=M_{y_i}. \]
The monitor has positive black mass and a strict white majority, contradicting final stability.
Thus \(J\) indexes a cover of size at most \(h\). This argument applies to arbitrary rational transfer amounts, including sequences that split a type’s mass or revisit a type.
The constructed society has
\[ \tau=n+\ell+6,\qquad m=I+2n+2\ell+3,\qquad K=h+2\leq n+2\leq\tau. \]
All numerical entries have \(O(\log\tau)\)-bit dyadic encodings. With an explicitly written matrix, the output length satisfies \(L=O(\tau^2\log\tau)\). After reading the source instance, the construction takes \(O(\tau^2\operatorname{poly}(\log\tau))\) bit operations. It is therefore a polynomial-time many-one reduction.
For completeness, the general problem also admits the following exact decision procedure:
\[ 4^\tau(6\tau)^K\operatorname{poly}(m+\tau,L,K) \]
bit operations. Here the dependence is on the numerical value of \(K\), not its encoding length.
To justify this bound, fix a length \(k\leq K\) and a sequence of move labels \((t,i,j)\). There are \((6\tau)^k\) possibilities. Introduce variables for the transfer amounts and intermediate states; all transition equations and mass constraints are linear.
For final stability, independently choose one of four modes at every type:
These modes describe exactly the stable states: if a strict majority exists, stability forces the type to be entirely of that majority opinion; otherwise the first mode applies.
For each resulting branch, replace every strict move constraint by a common positive margin \(\eta\):
\[ \delta_r\geq\eta,\qquad 2H_{t_r,j_r}^{\,r-1}-M_{t_r}\geq\eta,\qquad 0\leq\eta\leq1, \]
and maximize \(\eta\), retaining the source-mass bounds, transitions, and terminal threshold. A legal sequence exists in that branch exactly when the optimum is positive. The linear program has encoding length polynomial in \(m+\tau,L,k\); exact rational linear programming decides it in polynomial time. Its bounded rational feasible region also ensures that a positive optimum supplies rational transfer amounts.
Summing over \(k\leq K\) gives the stated bound. Since binary encoding permits \(K\) to be exponential in \(L\), this is not an input-polynomial algorithm.
The same linear-programming argument gives polynomial-size rational certificates whenever \(K\) is polynomially bounded in \(L\). In particular, the restriction \(K\leq\tau\) is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed \(\mathrm{NP}\)-hardness for the exact rational-mass problem. The reduction respects all input restrictions, and its reverse direction remains valid for arbitrary partial transfers. I found no mathematical errors or gaps requiring repair. The additional decision procedure and the \(\mathrm{NP}\)-completeness claim for \(K\leq\tau\) also check out.
The stated decision version of Set Cover is the standard \(\mathrm{NP}\)-complete problem cited by the prover. [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf)
Restricting to nonempty universes, nonempty set families, covered universes, and \(0\leq h\leq n\) preserves hardness as described: the excluded trivial cases can be decided directly and mapped to fixed instances satisfying the restrictions. Capping the budget at \(n\) preserves the answer.
Consequently, \(1\leq d_i\leq n\) is justified. The identity \(M_t=\sum_a H_{t,a}\) follows from conservation of each type’s total mass. It correctly converts the move condition into \(2H_{t,a}>M_t\).
The choices of \(r\) and \(s\) imply \(e\leq 1/(16(n+2))\) and \(\ell f\leq e/4\). These bounds imply the asserted \(\varepsilon<1/8\), so the mass of \(R\) is positive.
The mass sum is correct: the four anchor masses sum to \(1-\varepsilon\), while all remaining masses sum to \((n+2)e+\ell f=\varepsilon\). Every supported type therefore has positive mass, and the total is \(1\).
Every matrix entry lies in \([0,1]\). In particular, \(4d_i e\leq 4ne<1\). The off-diagonal entries are explicitly symmetric; the permitted diagonal entries cause no conflict with the task.
The connectivity argument includes every type, including set types corresponding to empty sets. Such types still connect to both clocks. The assumption \(d_i\geq1\) connects every monitor to a set type, and the positive monitor–\(B\) entries connect \(B\).
The threshold satisfies \(0<q<1\) and equals the initial black mass.
The first-move argument is valid for arbitrary earlier transfers at other types.
Immediately before a first anchor move, the diagonal contribution to the current opinion at each of \(W,G,B\) is \(1/4\). The total contribution from nonanchor types to any competing opinion is at most \(\varepsilon<1/8\), because all matrix entries are at most \(1\). The only additional anchor interaction is between \(W\) and \(R\), whose opinions agree.
Thus a competing opinion cannot have a strict majority at these anchors. At \(R\), all interacting mass supports white. This excludes a first anchor move and establishes the invariant.
Before a purported first transfer into black, the set types and clocks have no black mass. Monitors may have lost black mass, but this only decreases their black contributions.
At \(x_j\), the asserted bounds \(H_{x_j,b}\leq a_jf\leq e/4\) and \(M_{x_j}=3e+a_jf\) are correct. They exclude a black majority.
At either clock, the black field is zero. At a monitor, the absence of a diagonal entry means its retained black mass contributes nothing to its own field. Its only black contribution is therefore from \(B\), giving \(H_{y_i,b}=d_i e\) and \(M_{y_i}=(2d_i+1)e\). These values also exclude a black majority.
Together with anchor invariance, this exhausts all possible destinations of a first transfer into black.
The resulting conclusion about accepting sequences is justified: every transfer out of black strictly decreases total black mass, and no transfer can restore it. Since the initial mass equals \(q\), an accepting sequence cannot contain any transfer out of black. Every monitor consequently remains entirely black throughout such a sequence.
At \(C\), the fixed white anchor contributes \(1/4\), while the total contribution to other opinions is at most \(ne<1/4\). White therefore always has a strict majority. The analogous assertion for gray at \(D\) is correct.
Stability consequently requires \(C\) to be entirely white and \(D\) entirely gray. Their initial opinions differ from these required final opinions, so every stable-reaching sequence contains at least one move at each clock. This remains true when transfers are partial or clocks are revisited.
Moving \(D\) first leaves both clocks entirely gray during all selected set moves.
Immediately before the prescribed move at \(x_j\), its white diagonal contribution is \(e\), its gray clock contribution is \(2e\), and its black monitor contribution is \(a_jf\). The calculation \(4e>3e+a_jf\) is correct and strictly satisfies the required pre-move majority condition. The full transfer also satisfies the source-mass bound.
The final move at \(C\) is legal by the permanent clock majority.
Final stability is correctly checked for every category:
The final black mass equals \(q\), and the move count is \(|J|+2\leq K\). The forward implication is established.
An accepting sequence preserves every monitor’s black mass and uses at least two clock moves. Hence the number of distinct set types that move is at most \(h\).
If an element is absent from all sets indexed by these moved types, every neighboring set type remains entirely white. The monitor’s final fields are then exactly those stated in the output. In particular, \(2(d_i+1)e>(2d_i+1)e\), so white has a strict majority while the monitor retains positive black mass. This contradicts stability.
The argument uses only whether a set type ever moves. It makes no assumption about the transfer amounts, intermediate monochromaticity, or repeated moves. Thus the continuous model is fully addressed.
The counts \(\tau=n+\ell+6\) and \(m=I+2n+2\ell+3\) are correct. Also, \(K=h+2\leq n+2\leq\tau\).
Since \(r+s=O(\log\tau)\), all constructed numerical values have the claimed dyadic encoding size. The explicitly written matrix has length \(O(\tau^2\log\tau)\), and the stated construction time is polynomial in the source input length. The many-one reduction is valid.
There are correctly \(6\tau\) possible move labels per step. Fixing these labels makes the transitions, fields, source-mass bounds, and terminal threshold linear.
The four terminal modes exactly describe stability. If there is no strict majority, the first mode applies. If there is a strict majority, stability requires all mass at that type to have that opinion. Conversely, each stated mode guarantees stability.
For a fixed finite sequence, all required strict inequalities hold exactly when some common positive margin \(\eta\) satisfies the displayed constraints. The cap \(\eta\leq1\) does not affect this equivalence.
The resulting programs have rational coefficients, polynomial encoding length, and bounded variables. The asserted exact rational linear-programming theorem therefore applies. A positive optimum supplies rational transfers, as required by the task.
The enumeration includes \(k=0\). For this branch there are no move-margin constraints, so a feasible terminal state permits \(\eta=1\), correctly handling the empty sequence and \(K=0\).
Summing the branches gives the stated \(4^\tau(6\tau)^K\operatorname{poly}(m+\tau,L,K)\) bound, with dependence on the numerical value of \(K\). The output correctly distinguishes this from polynomial time in its binary encoding.
Polynomial-size rational certificates follow when \(K\) is polynomially bounded in \(L\). Combined with the reduction, this establishes \(\mathrm{NP}\)-completeness for \(K\leq\tau\). The output does not overclaim membership in \(\mathrm{NP}\) for unrestricted binary-encoded \(K\).
No additional clarification is needed to verify the claimed results.
⟨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.