Answer: \(\mathrm{NP\text{-}complete}\)
Theorem 2.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 w.h.p. achieves approximation ratio of 1 −1 𝑒−𝜖 in time O(𝑘𝑅𝑛𝑚𝑇), where 𝑇= 𝐷Δ+.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational positive type masses \(\mu\), a row-stochastic type-transition matrix \(P\), blue masses \(\beta\), a seed budget \(\kappa\), accuracy parameters \(\varepsilon,\delta,\zeta\), and a certified horizon \(H\), choose mass \(a_t\) with \(0\le a_t\le\mu_t-\beta_t\) and \(\sum_t a_t\le\kappa\). Starting from \(r_t^0=a_t\), \(b_t^0=\beta_t\), and \(u_t^0=\mu_t-\beta_t-a_t\), evolve the block-exchangeable Random Pick recursion \(r_t^{\ell+1}=r_t^\ell+u_t^\ell\sum_uP_{tu}r_u^\ell/\mu_u\), \(b_t^{\ell+1}=b_t^\ell+u_t^\ell\sum_uP_{tu}b_u^\ell/\mu_u\), and \(u_t^{\ell+1}=u_t^\ell\sum_uP_{tu}u_u^\ell/\mu_u\). Let \(R_\infty(a)=\sum_t\lim_{\ell\to\infty}r_t^\ell\) and \(\operatorname{OPT}=\max_aR_\infty(a)\); output a feasible \(a\) with \(R_\infty(a)\ge(1-\frac{1}{e}-\varepsilon)\operatorname{OPT}-\zeta\) with probability at least \(1-\delta\), using the promise that \(\sum_tu_t^H\le\zeta\).
An instance has a finite type set \(\Theta\), positive rational masses \(\mu_\theta\), a rational \(\kappa\) with \(0\le\kappa\le\sum_\theta\mu_\theta\), and a rational row-stochastic kernel \(P\) satisfying \(P_{\theta\theta'}>0\) iff \(P_{\theta'\theta}>0\).
Choose colored masses \(c_\theta\) with \(0\le c_\theta\le\mu_\theta\) and \(\sum_\theta c_\theta=\kappa\). Let \(u_\theta^0=\mu_\theta-c_\theta\) and \(u_\theta^1=u_\theta^0\sum_{\theta'}P_{\theta\theta'}u_{\theta'}^0/\mu_{\theta'}\).
The decision problem asks whether a feasible choice satisfies \(\sum_\theta u_\theta^1=0\).
Is this mass-input one-round convergence problem solvable in polynomial time, or is it NP-hard?
For finite undirected graphs, deciding whether there is an initial state with exactly \(k\) colored vertices whose Random Pick process has expected convergence time \(1\) is NP-hard.
No result for the exact finite-type mass formulation above has been verified.
The mass-input one-round convergence problem is \( \mathrm{NP\text{-}complete} \) under polynomial-time many-one reductions.
This holds even when every type has unit mass and the kernel has zero diagonal. Consequently, the problem is not polynomial-time solvable unless \( \mathrm{P}=\mathrm{NP} \).
Let
\[ x_\theta:=u_\theta^0=\mu_\theta-c_\theta \]
be the uncolored mass of type \( \theta \). If
\[ M:=\sum_{\theta\in\Theta}\mu_\theta, \qquad U:=M-\kappa, \]
then feasibility of \(c\) is equivalent to
\[ 0\le x_\theta\le\mu_\theta \quad\text{for every }\theta, \qquad \sum_{\theta\in\Theta}x_\theta=U. \]
The total uncolored mass after one round is
\[ \begin{aligned} \sum_{\theta\in\Theta}u_\theta^1 &= \sum_{\theta\in\Theta} x_\theta \sum_{\theta'\in\Theta} P_{\theta\theta'} \frac{x_{\theta'}}{\mu_{\theta'}}\\ &= \sum_{\theta,\theta'\in\Theta} P_{\theta\theta'} \frac{x_\theta x_{\theta'}}{\mu_{\theta'}}. \end{aligned} \]
Every summand is nonnegative because \(P_{\theta\theta'}\ge 0\), \(x_\theta\ge 0\), and \(\mu_{\theta'}>0\). Therefore,
\[ \sum_\theta u_\theta^1=0 \]
if and only if
\[ x_\theta x_{\theta'}=0 \quad\text{whenever}\quad P_{\theta\theta'}>0. \tag{1} \]
There can be no cancellation between different terms.
Construct a simple graph \(G_P\) as follows:
The symmetric-support hypothesis ensures that this adjacency relation is undirected.
Give vertex \( \theta \) weight \( \mu_\theta \), and write
\[ \alpha_\mu(G_P) := \max\left\{ \sum_{\theta\in I}\mu_\theta: I\text{ is an independent set of }G_P \right\}. \]
A feasible one-round-convergent choice exists if and only if
\[ U\le \alpha_\mu(G_P). \tag{2} \]
Suppose a feasible vector \(x\) satisfies the zero condition. Let
\[ I:=\{\theta:x_\theta>0\}. \]
If \(P_{\theta\theta}>0\), condition (1) applied to \((\theta,\theta)\) gives \(x_\theta^2=0\), so \(\theta\notin I\). For distinct \(\theta,\theta'\in I\), condition (1) implies \(P_{\theta\theta'}=0\). Thus \(I\) is an independent set of \(G_P\). Hence
\[ U = \sum_{\theta\in I}x_\theta \le \sum_{\theta\in I}\mu_\theta \le \alpha_\mu(G_P). \]
Conversely, suppose \(I\) is an independent set with
\[ \sum_{\theta\in I}\mu_\theta\ge U. \]
Distribute exactly \(U\) units of uncolored mass among the vertices of \(I\), subject to their capacities. Explicitly, after ordering \(I=\{\theta_1,\ldots,\theta_r\}\), set successively
\[ x_{\theta_i} = \min\left\{ \mu_{\theta_i}, U-\sum_{j<i}x_{\theta_j} \right\}, \]
until the remaining mass is zero, and set every other coordinate to zero. The capacity inequality ensures that this construction assigns total mass \(U\).
Because \(I\) contains no looped vertex and no adjacent pair, condition (1) holds. Defining \(c_\theta=\mu_\theta-x_\theta\) therefore gives a feasible colored-mass vector satisfying
\[ \sum_\theta u_\theta^1=0. \]
This proves the lemma.
An independent set \(I\subseteq V(G_P)\) is a polynomial-size certificate. A verifier checks:
All calculations are exact operations on binary-encoded rationals and take polynomial time. By the lemma, such a certificate exists exactly for the yes-instances. Hence the problem belongs to \( \mathrm{NP} \).
We reduce from the standard \( \mathrm{NP} \)-complete Independent Set problem.
Let \(H=(V,E)\) be a finite simple graph without isolated vertices, and let \(k\) be a positive integer. The restriction to graphs without isolated vertices remains \( \mathrm{NP} \)-hard: given an arbitrary graph \(G\), remove its set \(Z\) of isolated vertices and replace the target \(k\) by \(k-|Z|\), handling the immediately true case \(k\le |Z|\) separately.
Construct a mass instance with
\[ \Theta:=V, \qquad \mu_v:=1 \quad\text{for every }v\in V, \]
and
\[ P_{vw} := \begin{cases} \dfrac{1}{\deg_H(v)},&\text{if }\{v,w\}\in E,\\[6pt] 0,&\text{otherwise}. \end{cases} \]
Because \(H\) has no isolated vertices, every denominator is positive. Moreover,
\[ \sum_{w\in V}P_{vw} = \deg_H(v)\frac{1}{\deg_H(v)} = 1, \]
so \(P\) is row-stochastic. Also,
\[ P_{vw}>0 \quad\Longleftrightarrow\quad \{v,w\}\in E \quad\Longleftrightarrow\quad P_{wv}>0. \]
Thus the symmetric-support requirement holds. Since \(H\) is simple,
\[ P_{vv}=0 \quad\text{for every }v. \]
Finally, set
\[ \kappa:=|V|-k. \]
The required total uncolored mass is then
\[ U=\sum_{v\in V}\mu_v-\kappa =|V|-(|V|-k) =k. \]
For this instance, \(G_P\) is exactly \(H\), and all its vertex weights are \(1\). The characterization in Section 2 gives
\[ \begin{aligned} \text{mass instance is a yes-instance} &\Longleftrightarrow k\le\alpha_\mu(G_P)\\ &\Longleftrightarrow k\le\alpha(H)\\ &\Longleftrightarrow H\text{ has an independent set of size at least }k. \end{aligned} \]
The construction has polynomial size and is computable in polynomial time. Therefore the mass-input problem is \( \mathrm{NP} \)-hard.
The continuous freedom to split masses does not remove the combinatorial obstruction. Requiring the nonnegative quadratic expression to be exactly zero forces the positive uncolored support to be an independent set. The problem is precisely a vertex-weighted independent-set threshold problem on the support graph of \(P\), after excluding vertices with positive diagonal entries.
Thus the target problem is \( \mathrm{NP\text{-}complete} \).
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces the zero-convergence condition to a weighted independent-set threshold and establishes NP-hardness using unit masses and a zero-diagonal kernel. The central mathematical argument is sound.
There is one minor boundary-case omission in the reduction: the construction requires \(0\le \kappa=|V|-k\), but the write-up does not explicitly restrict source instances to \(k\le |V|\) or specify the fixed output instances used when preprocessing immediately decidable cases. This is a routine clarification rather than a substantive gap.
The substitution \(x_\theta=\mu_\theta-c_\theta\) is correct. The original constraints translate exactly into
\[ 0\le x_\theta\le\mu_\theta, \qquad \sum_\theta x_\theta=\sum_\theta\mu_\theta-\kappa=U. \]
Because \(0\le\kappa\le\sum_\theta\mu_\theta\), one has \(0\le U\le\sum_\theta\mu_\theta\).
The expansion
\[ \sum_\theta u_\theta^1 = \sum_{\theta,\theta'} P_{\theta\theta'}\frac{x_\theta x_{\theta'}}{\mu_{\theta'}} \]
is correct. Every term is nonnegative because \(P_{\theta\theta'}\ge0\), \(x_\theta,x_{\theta'}\ge0\), and \(\mu_{\theta'}>0\).
Consequently, the sum is zero exactly when every term with positive coefficient vanishes, namely
\[ x_\theta x_{\theta'}=0 \quad\text{whenever}\quad P_{\theta\theta'}>0. \]
This equivalence is rigorous; finiteness of \(\Theta\) ensures that a finite sum of nonnegative terms is zero precisely when every term is zero.
The graph \(G_P\) is well-defined. Excluding vertices with \(P_{\theta\theta}>0\) correctly accounts for the diagonal constraints \(x_\theta^2=0\). The symmetric-support assumption ensures that adjacency between distinct types is undirected.
For a zero-convergent feasible vector, its positive support \(I=\{\theta:x_\theta>0\}\):
Thus \(I\) is an independent set in \(G_P\), and
\[ U=\sum_{\theta\in I}x_\theta \le\sum_{\theta\in I}\mu_\theta \le\alpha_\mu(G_P). \]
This direction is correct.
Conversely, if an independent set has total capacity at least \(U\), the stated greedy allocation produces coordinates satisfying \(0\le x_\theta\le\mu_\theta\) and total mass \(U\). Since its positive support lies in \(I\), and \(I\) has neither looped vertices nor adjacent pairs, the zero condition holds.
The edge case \(U=0\), including \(I=\varnothing\), is implicit but valid.
Therefore the equivalence
\[ \text{a feasible zero-convergent choice exists} \quad\Longleftrightarrow\quad U\le\alpha_\mu(G_P) \]
is established.
An independent set \(I\) is a polynomial-size certificate. The listed checks establish exactly that \(I\) is an independent set of eligible vertices and has capacity at least \(U\).
Exact comparisons and additions of binary-encoded rational numbers are polynomial-time operations. Hence membership in NP is correctly established.
For a graph \(H\) without isolated vertices, the kernel
\[ P_{vw}= \begin{cases} 1/\deg_H(v),&\{v,w\}\in E,\\ 0,&\text{otherwise} \end{cases} \]
is rational and row-stochastic. Its support is symmetric, and its diagonal is zero because \(H\) is simple. The binary encoding of every denominator has polynomial length.
With unit masses and \(\kappa=|V|-k\), one obtains \(U=k\). The support graph \(G_P\) is exactly \(H\), so the proved characterization yields equivalence with the existence of an independent set of size at least \(k\).
The transformation eliminating isolated vertices preserves the threshold because every isolated vertex may be included in an independent set. However, the many-one reduction is not completely specified for the immediately decidable branches, and validity of \(\kappa\) requires the normalization \(k\le |V|\). The prover should explicitly state either the conventional restriction \(1\le k\le |V|\) and identify the fixed yes-instance used when \(k\le |Z|\), or specify fixed valid outputs for all exceptional cases, including \(k>|V|\). No new mathematical idea is needed.
The independent-set characterization, NP membership, and main hardness construction are correct. The only gap is a routine formalization of boundary cases in the many-one reduction.
⟨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.