Answer: —
Theorem 4 — class: algorithmic
Given finitely many weighted rooted network templates \(H\), rational masses \(\mu_{h,a}\) of rooted roles \((h,a)\), regression parameters \(k,\varepsilon\), and \(W_h=L_h+I\), choose per-agent sample intensities \(r_{h,a}\ge k\) minimizing \(S_\infty=\sum_{h,a}\mu_{h,a}r_{h,a}\), subject to \(k\sum_{b\in V_h}[(W_h^{-1})_{ab}]^2/r_{h,b}\le\varepsilon\) for every rooted role \((h,a)\), and output the optimum and an allocation attaining it.
Input consists of a nonempty finite family of explicitly listed finite network templates \(H_h=(V_h,E_h)\), with nonnegative binary-rational symmetric influence weights \(v^h_{ab}=v^h_{ba}\), zero off edges and on the diagonal. Define \((W_h)_{aa}=1+\sum_{b\ne a}v^h_{ab}\) and \((W_h)_{ab}=-v^h_{ab}\) for \(a\ne b\).
A type is a rooted role \((h,a)\), where \(a\in V_h\). Every vertex of each listed template has a supported role. A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses \(\mu_{h,a}\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Given an integer \(k\ge1\) and a positive binary-rational \(\varepsilon\), choose real intensities \(r_{h,a}\ge k\) minimizing \(S_\infty=\sum_{h,a}\mu_{h,a}r_{h,a}\), subject to \(k\sum_{b\in V_h}[(W_h^{-1})_{ab}]^2/r_{h,b}\le\varepsilon\) for every supported role. Denote the minimum by \(S_\infty^*\); the optimization problem asks for this value and an attaining allocation.
Let \(m=\max_h|V_h|\) and \(L\) be the total binary input length, including a nonnegative rational threshold \(B\). State running times in \(m,\tau,L\), and \(k\).
Is deciding whether \(S_\infty^*\le B\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite networks, Liu et al. establish \(\mathrm{TSC}=\Theta(\sum_i m_i^*+nk)\), where \(m^*\) minimizes their reciprocal-constraint allocation program, and give a polynomial-time estimation framework. [Source](https://arxiv.org/html/2311.02349v3)
They also give an SOCP formulation for that real allocation program; this does not itself establish an exact rational-threshold complexity classification for the distribution-over-role problem above. [Source](https://arxiv.org/html/2311.02349v3)
I do not settle whether the general exact threshold problem is in $\mathrm{P}$ or is $\mathrm{NP}$-hard. The following results are proved below.
$$ (\tau+1)^{O(\tau)}\operatorname{poly}(m,L,\log(k+1)). $$
These statements concern exact comparison, including equality at $B$.
Enumerate all supported roles by $i=1,\ldots,\tau$. Since every vertex of every listed template is supported, all variables have positive objective coefficients, and
$$
\sum_h |V_h|=\tau.
$$
Empty templates, if permitted, can be discarded.
Write
$$
P_h=W_h^{-1},
\qquad
C^h_{ab}=(P_h)_{ab}^{2},
$$
and let $C$ be the block diagonal matrix with blocks $C^h$.
For every nonzero real vector $z$ indexed by $V_h$,
$$
z^{\mathsf T}W_hz
=
\sum_a z_a^2+
\sum_{\{a,b\}\subseteq V_h}v^h_{ab}(z_a-z_b)^2
>0.
$$
Thus $W_h$ is positive definite and invertible. Its inverse has rational entries.
Moreover, $P_h$ is entrywise nonnegative. To prove this, take any $b\ge0$ and write $z=W_h^{-1}b$. If some coordinate of $z$ were negative, choose a coordinate $a$ attaining its minimum. Then
$$
b_a=(W_hz)_a
=
z_a+\sum_{c\ne a}v^h_{ac}(z_a-z_c)
\le z_a<0,
$$
contradicting $b\ge0$. Applying this argument to each coordinate vector $b$ proves $P_h\ge0$.
Since $W_h\mathbf1=\mathbf1$, we also have $P_h\mathbf1=\mathbf1$. Therefore
$$
\sum_b C^h_{ab}
=
\sum_b(P_h)_{ab}^2
\le
\left(\sum_b(P_h)_{ab}\right)^2
=1.
$$
Set $r_i=kx_i$. The normalized problem is
$$
F^*=
\min\left\{
\sum_i\mu_i x_i:
x_i\ge1,\quad C(1/x)\le\varepsilon\mathbf1
\right\},
\qquad
S_\infty^*=kF^*,
$$
where $1/x$ denotes coordinatewise reciprocation.
Let
$$
R=\max\{1,1/\varepsilon\}.
$$
The uniform allocation $x_i=R$ is feasible because every row sum of $C$ is at most $1$. Its objective is $R$, using $\sum_i\mu_i=1$.
Every allocation whose normalized objective is at most $R$ satisfies
$$
1\le x_i\le R/\mu_i.
$$
All masses are positive. Hence the feasible set intersected with this objective sublevel is nonempty, closed, and bounded. The objective is continuous, so its minimum is attained. In particular,
$$
k\le S_\infty^*\le kR.
$$
Set $y_i=1/x_i$. The normalized problem becomes
$$
\min_{y\in D} f(y),
\qquad
f(y)=\sum_i\frac{\mu_i}{y_i},
\qquad
D=\{y:0<y_i\le1,\ Cy\le\varepsilon\mathbf1\}.
$$
The domain $D$ is convex. On the positive orthant,
$$
\nabla^2f(y)
=
\operatorname{diag}\left(\frac{2\mu_i}{y_i^3}\right)
$$
is positive definite, because every $\mu_i>0$. Thus $f$ is strictly convex.
If two distinct feasible points both minimized $f$, their midpoint would be feasible and would have strictly smaller objective. This is impossible. Therefore the minimizing $y$, and consequently the minimizing allocation $r_i=k/y_i$, are unique.
Consider a template with two vertices $a,b$ and influence weight $w\ge0$. Let its masses be $u,v>0$. These are their actual society masses; they need not sum to $1$.
When $w=0$, both vertices are isolated. Their optimal normalized intensities are
$$
x_a=x_b=\max\{1,1/\varepsilon\},
$$
with contribution
$$
(u+v)\max\{1,1/\varepsilon\}.
$$
Assume henceforth $w>0$. Direct inversion gives
$$
P=
\begin{pmatrix}
p&q\\
q&p
\end{pmatrix},
\qquad
p=\frac{1+w}{1+2w},
\qquad
q=\frac{w}{1+2w}.
$$
Thus $p>q>0$ and $p+q=1$. Define
$$
A=p^2,\qquad D=q^2,\qquad \rho=A+D.
$$
The normalized reciprocal constraints are
$$
\frac{A}{x_a}+\frac{D}{x_b}\le\varepsilon,
\qquad
\frac{D}{x_a}+\frac{A}{x_b}\le\varepsilon.
$$
If $\varepsilon\ge\rho$, the allocation $x_a=x_b=1$ is feasible and optimal, with contribution $u+v$.
For the remaining case, assume
$$
0<\varepsilon<\rho.
$$
Interchange the vertex labels if necessary so that $u\ge v$, and define
$$
\gamma=A+pq\sqrt{v/u}.
$$
The exact solution is as follows.
| Condition | Optimal $(x_a,x_b)$ | Optimal normalized contribution |
|---|---|---|
| $uD\le vA$ | $\left(\rho/\varepsilon,\rho/\varepsilon\right)$ | $(u+v)\rho/\varepsilon$ |
| $uD>vA$ and $\varepsilon\le\gamma$ | $\left((A+pq\sqrt{v/u})/\varepsilon,(D+pq\sqrt{u/v})/\varepsilon\right)$ | $(Au+Dv+2pq\sqrt{uv})/\varepsilon$ |
| $uD>vA$ and $\varepsilon>\gamma$ | $\left(1,D/(\varepsilon-A)\right)$ | $u+vD/(\varepsilon-A)$ |
The original intensities are $r_a=kx_a$ and $r_b=kx_b$.
Use reciprocal variables $y_a=1/x_a$ and $y_b=1/x_b$.
First, the optimizer satisfies $y_a\ge y_b$. When $u>v$, if $y_a<y_b$, swapping the coordinates preserves feasibility and decreases the objective, since
$$
\left(\frac{u}{y_a}+\frac{v}{y_b}\right)
-
\left(\frac{u}{y_b}+\frac{v}{y_a}\right)
=
(u-v)\left(\frac1{y_a}-\frac1{y_b}\right)>0.
$$
When $u=v$, swapping preserves the objective, and uniqueness forces $y_a=y_b$.
For $y_a\ge y_b$, the first constraint is the stronger one, because
$$
(Ay_a+Dy_b)-(Dy_a+Ay_b)
=
(A-D)(y_a-y_b)\ge0.
$$
At the optimizer, this first constraint is tight. Indeed, suppose
$$
Ay_a+Dy_b<\varepsilon.
$$
Move along the segment from $(y_a,y_b)$ toward $(1,1)$. This preserves the coordinate bounds and ordering. The first constraint increases continuously to $\rho>\varepsilon$, so it becomes tight before reaching $(1,1)$. Both coordinates weakly increase, and at least one strictly increases. Consequently the objective strictly decreases, contradicting optimality.
Put $z=y_a$. Tightness gives
$$
y_b=\frac{\varepsilon-Az}{D}.
$$
The ordering and positivity conditions become
$$
z\ge\frac{\varepsilon}{\rho},
\qquad
z\le1,
\qquad
z<\frac{\varepsilon}{A}.
$$
Conversely, these conditions ensure $0<y_b\le z\le1$, and hence feasibility for both constraints.
We therefore minimize
$$
\phi(z)=\frac{u}{z}+\frac{vD}{\varepsilon-Az}
$$
on this interval. Its derivatives are
$$
\phi'(z)
=
-\frac{u}{z^2}
+
\frac{vDA}{(\varepsilon-Az)^2},
$$
$$
\phi''(z)
=
\frac{2u}{z^3}
+
\frac{2vDA^2}{(\varepsilon-Az)^3}
>0.
$$
The unique unconstrained critical point is
$$
z_0
=
\frac{\varepsilon}{A+\sqrt{AD}\sqrt{v/u}}
=
\frac{\varepsilon}{\gamma}.
$$
It always satisfies $z_0<\varepsilon/A$.
The position of $z_0$ relative to the remaining endpoints determines the optimizer:
$$
z_0\le\frac{\varepsilon}{\rho}
\quad\Longleftrightarrow\quad
A+pq\sqrt{v/u}\ge A+D
\quad\Longleftrightarrow\quad
vA\ge uD.
$$
Strict convexity then makes the left endpoint optimal, giving the first row of the table.
$$ u\frac{A+pq\sqrt{v/u}}{\varepsilon} + v\frac{D+pq\sqrt{u/v}}{\varepsilon} = \frac{Au+Dv+2pq\sqrt{uv}}{\varepsilon}. $$
$$
0<\frac{\varepsilon-A}{D}<1.
$$
This gives the third row.
This proves every case, including the equality boundaries.
All parameters except $\gamma$ are rational. Comparing $\varepsilon$ with $\gamma$ also reduces to rational arithmetic.
If $\varepsilon\le A$, then automatically $\varepsilon\le\gamma$. If $\varepsilon>A$, both sides of
$$
\varepsilon-A\le pq\sqrt{v/u}
$$
are nonnegative, so squaring is reversible:
$$
\varepsilon\le\gamma
\quad\Longleftrightarrow\quad
u(\varepsilon-A)^2\le ADv.
$$
Thus the applicable formula can be selected in polynomial time using exact rational arithmetic, without approximate square-root comparisons.
Define the square-root-sum decision problem, abbreviated $\mathrm{SRS}$, as follows: given positive binary integers $d_1,\ldots,d_n$ and a nonnegative binary integer $K$, decide whether
$$
\sum_{i=1}^n\sqrt{d_i}\le K.
$$
The exact comparison issue is discussed in [Cheng et al., *On the Sum of Square Roots of Polynomials and Related Problems*](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Sum20of20Square20Roots20ToCT.pdf).
Different templates have disjoint variables and constraints. Every allocation costs at least the sum of the individual template minima, and combining their individual minimizers attains this sum. Therefore their optimal contributions add exactly.
For $m\le2$, the formulas in Section 2 express the normalized optimum as
$$
F^*=R_0+\sum_{j=1}^J\sqrt{z_j},
$$
where $R_0$ is rational, every $z_j$ is a positive rational, and $J\le\tau$.
Specifically, each interior two-vertex case contributes
$$
\frac{Au+Dv}{\varepsilon}
+
\sqrt{\left(\frac{2pq}{\varepsilon}\right)^2uv}.
$$
All other cases contribute only rational terms. Singleton templates contribute
$$
\mu_i\max\{1,1/\varepsilon\}.
$$
The case selection and construction of $R_0,z_1,\ldots,z_J$ take
$$
\operatorname{poly}(\tau,L,\log(k+1))
$$
bit operations. Rational additions and products preserve polynomial encoding length: the bit length of a product is at most the sum of its factors’ bit lengths, and common denominators can be formed by products.
Set
$$
t=B/k-R_0.
$$
If $t<0$, the answer is no. If $J=0$, rational comparison decides the answer. In these cases, output a fixed yes or no instance of $\mathrm{SRS}$, respectively $(d_1,K)=(1,1)$ or $(1,0)$.
Otherwise, write
$$
z_j=a_j/b_j,
\qquad
t=c/e,
$$
with positive integers $a_j,b_j,e$ and a nonnegative integer $c$. Define
$$
Q=e\prod_{j=1}^J b_j,
\qquad
d_j=a_jb_j(Q/b_j)^2,
\qquad
K=Qt.
$$
All $d_j$ are positive integers, and $K$ is a nonnegative integer. Moreover,
$$
\sqrt{d_j}=Q\sqrt{z_j}.
$$
Since $Q>0$,
$$
S_\infty^*\le B
\quad\Longleftrightarrow\quad
\sum_{j=1}^J\sqrt{d_j}\le K.
$$
The binary length of $Q$ is the sum of polynomially bounded denominator lengths. The output therefore has polynomial length and is computable in polynomial time. This proves a polynomial-time many-one reduction to $\mathrm{SRS}$.
The same computation outputs the unique allocation as polynomial-length radical expressions. This symbolic output does not itself decide their sum’s comparison with a rational threshold.
Here is a complete reduction in the other direction, including the construction from the notes.
Take an $\mathrm{SRS}$ instance $d_1,\ldots,d_n,K$, with $n\ge1$. Set
$$
D_0=\sum_{i=1}^n d_i,
\qquad
N=9D_0+n,
$$
and choose a power of two $T>N$.
For each $i$, introduce a separately labelled two-vertex template with edge weight $1/2$, assigning masses
$$
u_i=\frac{9d_i}{T},
\qquad
v_i=\frac1T.
$$
Add a singleton template with mass
$$
\frac{T-N}{T}.
$$
Every mass is positive, and their sum is $1$. The template labels distinguish the roles even though the two-vertex structures are identical.
Set
$$
k=1,
\qquad
\varepsilon=\frac14.
$$
For every pair,
$$
p=\frac34,\qquad q=\frac14,
\qquad A=\frac9{16},\qquad D=\frac1{16},
\qquad \rho=\frac58.
$$
If $d_i=1$, then $u_iD=v_iA$, so the first case of Section 2 applies. If $d_i>1$, then $u_iD>v_iA$, and $\varepsilon<A<\gamma$, so the interior case applies. In both cases the pair’s exact contribution is
$$
\frac{81d_i+1+18\sqrt{d_i}}{4T}.
$$
For $d_i=1$, this expression equals $25/T$, matching the uniform-case contribution.
The corresponding normalized intensities, valid for every $d_i\ge1$, are
$$
x_{i,a}=\frac94+\frac1{4\sqrt{d_i}},
\qquad
x_{i,b}=\frac{9\sqrt{d_i}+1}{4}.
$$
Their feasibility and optimality follow from the proved cases in Section 2.
The singleton’s optimal intensity is $4$. Adding contributions gives
$$
S_\infty^*
=
\frac{
16(T-N)+81D_0+n+18\sum_{i=1}^n\sqrt{d_i}
}{4T}.
$$
Choose
$$
B=
\frac{16(T-N)+81D_0+n+18K}{4T}.
$$
Then
$$
S_\infty^*\le B
\quad\Longleftrightarrow\quad
\sum_{i=1}^n\sqrt{d_i}\le K.
$$
All masses and the threshold are dyadic, so the reduction remains valid if “binary-rational” is restricted to finite binary expansions. It has
$$
m=2,\qquad \tau=2n+1.
$$
If the source input length is $\ell$, the quantities $D_0,N,T$ have $O(\ell)$ bits, and the constructed input has $O(\ell^2)$ length. The reduction is therefore polynomial-time.
Proved conclusion: exact allocation decision restricted to $m\le2$ is polynomial-time many-one equivalent to $\mathrm{SRS}$. Neither direction establishes $\mathrm{NP}$-hardness.
For a template of size $n_h$, clear the denominators of its influence weights. A common denominator obtained by multiplying their denominators has polynomial binary length. The resulting integer matrix representing $W_h$ has entries of polynomial binary length.
The determinant expansion bounds determinant and cofactor lengths by a polynomial in $n_h,L$: a determinant has at most $n_h!$ terms, each a product of $n_h$ entries. The adjugate formula therefore bounds the rational entry lengths of $W_h^{-1}$ by a polynomial in $m,L$.
The inverses can be computed using exact elimination in
$$
O\left(\sum_h n_h^3\right)
\le O(\tau m^2)
$$
rational arithmetic operations. Fraction-free elimination gives polynomial bit complexity. Squaring inverse entries to obtain $C$, and clearing positive denominators in the formulas below, preserves polynomial encoding length.
The condition $S_\infty^*\le B$ is equivalent to the existence of real vectors $x,t$ satisfying
$$
x_i\ge1,\qquad t_i\ge0,\qquad x_it_i\ge1,
$$
$$
Ct\le\varepsilon\mathbf1,
\qquad
k\sum_i\mu_i x_i\le B.
$$
Indeed, an original feasible allocation meeting the threshold gives such a point by taking $x_i=r_i/k$ and $t_i=1/x_i$.
Conversely, these inequalities imply $t_i\ge1/x_i$. Since $C\ge0$,
$$
C(1/x)\le Ct\le\varepsilon\mathbf1.
$$
Thus $r_i=kx_i$ is feasible and meets the threshold. Attainment from Section 1 ensures equivalence with the optimum comparison, including equality.
After denominator clearing, this formula has $2\tau$ variables, $4\tau+1$ inequalities, degree at most two, and polynomially bounded integer coefficient lengths. Hence the decision problem belongs to $\exists\mathbb R$.
There is also a polynomial-size existential formula certifying the opposite answer.
Consider again
$$
f(y)=\sum_i\frac{\mu_i}{y_i},
\qquad
0<y_i\le1,
\qquad
Cy\le\varepsilon\mathbf1.
$$
This is a differentiable convex program on the open positive orthant. It attains its minimum.
It has a strictly feasible point. Set
$$
\delta=\frac12\min\{1,\varepsilon\},
\qquad
y=\delta\mathbf1.
$$
Then $0<\delta<1$ and, using the row-sum bound,
$$
Cy\le\delta\mathbf1<\varepsilon\mathbf1.
$$
The convex KKT theorem states that, for such a differentiable convex program with an attained minimum and a strictly feasible point, nonnegative multipliers satisfying stationarity and complementary slackness exist at every minimizer. Its hypotheses have just been checked. See [Boyd and Vandenberghe, *Convex Optimization*, Section 5.5.3](https://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf).
Thus a feasible $y$ is optimal precisely when there exist $\lambda_a,\nu_i\ge0$ satisfying
$$
\mu_i
=
y_i^2\left(\sum_a C_{ai}\lambda_a+\nu_i\right),
$$
$$
\lambda_a\bigl((Cy)_a-\varepsilon\bigr)=0,
\qquad
\nu_i(y_i-1)=0.
$$
Here $\lambda_a$ corresponds to a row constraint, and $\nu_i$ to $y_i\le1$.
For completeness, sufficiency follows directly. Stationarity says
$$
\nabla f(y)=-C^{\mathsf T}\lambda-\nu.
$$
For any feasible $z$, convexity gives
$$
f(z)\ge f(y)+\nabla f(y)^{\mathsf T}(z-y).
$$
Complementary slackness and feasibility imply
$$
-\lambda^{\mathsf T}C(z-y)\ge0,
\qquad
-\nu^{\mathsf T}(z-y)\ge0.
$$
For example, whenever $\lambda_a>0$, complementary slackness gives $(Cy)_a=\varepsilon$, while $(Cz)_a\le\varepsilon$. The coordinate inequality is justified identically. Hence $f(z)\ge f(y)$.
Introduce $x_i$ with $x_iy_i=1$. Let $\mathcal M(x,y,\lambda,\nu)$ denote the following system:
$$
0<y_i\le1,\qquad x_iy_i=1,
\qquad Cy\le\varepsilon\mathbf1,
$$
$$
\lambda_a\ge0,\qquad \nu_i\ge0,
$$
$$
\mu_i=y_i^2\left(\sum_a C_{ai}\lambda_a+\nu_i\right),
$$
$$
\lambda_a\bigl((Cy)_a-\varepsilon\bigr)=0,
\qquad
\nu_i(y_i-1)=0.
$$
Its solutions have exactly the optimal $x,y$, though the multipliers need not be unique.
Consequently,
$$
S_\infty^*>B
$$
is equivalent to
$$
\exists x,y,\lambda,\nu:
\quad
\mathcal M(x,y,\lambda,\nu)
\quad\text{and}\quad
k\sum_i\mu_i x_i>B.
$$
This formula has $4\tau$ variables, $O(\tau)$ polynomial conditions, degree at most three, and polynomial coefficient lengths.
Therefore both the decision problem and its complement reduce to existential real feasibility:
$$
\boxed{\text{Exact threshold decision belongs to }
\exists\mathbb R\cap\mathrm{co}\text{-}\exists\mathbb R.}
$$
This does not assert membership in $\mathrm{NP}$: the existential witnesses are real numbers, without a proved polynomial-size discrete certificate.
Existential real formulas with integer polynomial coefficients are decidable in polynomial space. This yields membership in $\mathrm{PSPACE}$; see [Canny, *Some Algebraic and Geometric Computations in PSPACE*](https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html).
The one-block real quantifier-elimination bounds give decision time
$$
(sd)^{O(q)}\operatorname{poly}(H)
$$
for $q$ quantified variables, $s$ polynomial conditions, degree bound $d$, and integer coefficient bit bound $H$. Applying these bounds to Section 4.2, with
$$
q=2\tau,\qquad s=4\tau+1,\qquad d=2,
$$
gives
$$
(\tau+1)^{O(\tau)}
\operatorname{poly}(m,L,\log(k+1)).
$$
The relevant quantifier-elimination and intermediate coefficient bounds are stated in [Basu, *Algorithms in Real Algebraic Geometry: A Survey*, Theorem 2.27](https://arxiv.org/html/1409.1534#S2.SS5.SSS2).
An exact output representation is necessary because optimal coordinates need not be rational. Use the following representation for each output number:
The represented number is that root. The polynomial need not be minimal.
For an allocation coordinate, keep $x_i$ free in $\mathcal M$ and existentially quantify all other variables. By existence and uniqueness, the resulting formula defines exactly the singleton
$$
\{x_i^*\}.
$$
For the optimum value, introduce a free variable $s$, impose
$$
s=k\sum_i\mu_i x_i,
$$
and quantify all variables of $\mathcal M$. This defines exactly
$$
\{S_\infty^*\}.
$$
Each formula has one free variable, $O(\tau)$ quantified variables and conditions, degree at most three, and polynomial coefficient lengths. One-block quantifier elimination therefore computes an equivalent univariate formula within
$$
(\tau+1)^{O(\tau)}
\operatorname{poly}(m,L,\log(k+1))
$$
time, with output degree and coefficient lengths bounded within the same asymptotic bound.
To see why this yields algebraic numbers, consider any such singleton formula after quantifier elimination. Some nonzero polynomial in the formula must vanish at the singleton point. Otherwise every polynomial sign would be constant on a sufficiently small neighborhood of that point, making the Boolean formula true on an interval. That would contradict its defining a singleton.
Univariate real-root isolation and sign evaluation select the unique root satisfying the formula. These operations take polynomial time in the univariate formula’s total length, degrees, and coefficient lengths. Performing this for all coordinates and for the value preserves the displayed singly exponential bound. Multiplication by $k$ produces the original intensities $r_i^*=kx_i^*$.
Thus the general optimization problem is exactly computable, with the stated representation and running time. In particular, both exact decision and exact optimization are polynomial-time solvable for fixed $\tau$.
For edgeless templates, $W_h=P_h=I$, so every role independently requires
$$
r_i\ge k,
\qquad
r_i\ge k/\varepsilon.
$$
Because every mass is positive, its smallest feasible intensity is optimal:
$$
r_i^*=k\max\{1,1/\varepsilon\},
\qquad
S_\infty^*=k\max\{1,1/\varepsilon\}.
$$
The allocation and rational threshold comparison take
$$
\operatorname{poly}(\tau,L,\log(k+1))
$$
time. This includes $m=1$.
The general rational SOCP formulation is also valid. Under $x_i\ge1$ and $t_i\ge0$,
$$
x_it_i\ge1
\quad\Longleftrightarrow\quad
\left\|(2,x_i-t_i)\right\|_2\le x_i+t_i.
$$
Indeed, the right-hand side is positive, and squaring gives exactly
$$
4+(x_i-t_i)^2\le(x_i+t_i)^2
\quad\Longleftrightarrow\quad
x_it_i\ge1.
$$
This matches the reciprocal-variable formulation in [Liu et al., Lemma 20](https://arxiv.org/html/2311.02349v3#Sx2.SS2).
It does not prove a polynomial-time exact threshold algorithm. Such an algorithm would, by Section 3.2, decide square-root-sum comparison in polynomial time.
The strengthened partial result identifies the exact comparison problem for all two-vertex templates: it is polynomial-time equivalent to square-root-sum comparison, and its optimum and allocation have explicit radical formulas.
For larger templates, both threshold answers have polynomial-size existential-real formulations, and exact algebraic output is available in singly exponential time.
None of these arguments supplies a polynomial-time exact algorithm for unrestricted $\tau$, or a reduction establishing $\mathrm{NP}$-hardness. The requested general classification therefore remains unresolved here.
⟨structured verdict parsed — rendered above⟩
Assessment: partial, mathematically sound progress. The subsidiary results check out. The output does not resolve the requested general classification: it proves neither membership in $\mathrm{P}$ nor $\mathrm{NP}$-hardness. It explicitly acknowledges this limitation, so there is no false claim of a complete solution.
I found no false central step or substantive gap in the partial results.
Verified.
$$ \sum_b C^h_{ab}\le1. $$
No missing boundary case affects these arguments. A valid society necessarily has $\tau\ge1$, since its positive masses sum to $1$.
Verified, including all equality boundaries.
The inverse matrix, the definitions $A=p^2$, $D=q^2$, and $\rho=A+D$ are correct. The cases $w=0$ and $\varepsilon\ge\rho$ are handled correctly.
For $w>0$ and $0<\varepsilon<\rho$:
$$
z_0=\frac{\varepsilon}{A+pq\sqrt{v/u}}
$$
is correct and lies below the excluded positivity endpoint.
$$ z_0\le\frac{\varepsilon}{\rho} \quad\Longleftrightarrow\quad vA\ge uD. $$
At $uD=vA$, the critical point coincides with the left endpoint. At $\varepsilon=\gamma$, it coincides with the endpoint $z=1$. Thus the table’s treatment of equality is consistent.
The rational case-selection test also checks out. Squaring is used only after establishing that both compared quantities are nonnegative.
Both polynomial-time many-one reductions are valid.
Allocation decision to square-root-sum. Independent template minima add because their variables and constraints are disjoint and their minima are attained. Every radical contribution has a positive rational radicand, and all remaining contributions are rational.
The denominator-clearing construction satisfies
$$
\sqrt{a_jb_j(Q/b_j)^2}=Q\sqrt{a_j/b_j}.
$$
The constructed threshold $K=Qt$ is an integer because $Q$ contains the denominator of $t$. The product of denominators has polynomial binary length; its magnitude need not be polynomial. The separately handled negative-threshold and radical-free cases are correct.
Square-root-sum to allocation decision. The construction satisfies all task restrictions:
The constants and pair contributions check out:
$$
\frac{81d_i+1+18\sqrt{d_i}}{4T}.
$$
For $d_i=1$, this equals $25/T$, as required by the uniform case. The displayed intensities agree with the applicable two-vertex formulas.
The singleton contribution and final threshold therefore give exactly the asserted comparison equivalence. The stated output-length bound is valid.
This establishes square-root-sum equivalence for $m\le2$. It supplies no reduction from a problem established here to be $\mathrm{NP}$-hard.
Verified.
The denominator, determinant, and cofactor bounds establish polynomial encoding lengths for $W_h^{-1}$ and $C$. Exact matrix inversion has the stated polynomial arithmetic-operation bound, and fraction-free elimination supports polynomial bit complexity.
The threshold formula is equivalent to the original problem in both directions. In particular, $x_i\ge1$ and $x_it_i\ge1$ imply $t_i\ge1/x_i$, and nonnegativity of $C$ makes the replacement sound. The count of $2\tau$ variables and $4\tau+1$ inequalities is correct.
Thus membership in $\exists\mathbb R$ is established.
Verified; the cited theorem’s hypotheses are satisfied.
The program has a differentiable convex objective on the open positive orthant and affine inequality constraints. Attainment was already proved. The proposed point $\delta\mathbf1$ lies in the objective’s domain and satisfies every inequality strictly.
The necessary-and-sufficient KKT theorem under Slater’s condition applies as stated. [Boyd and Vandenberghe, Section 5.5.3](https://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)
The stationarity equation has the correct sign:
$$
\frac{\mu_i}{y_i^2}
=
\sum_a C_{ai}\lambda_a+\nu_i.
$$
Multiplication by $y_i^2$ is reversible because $y_i>0$. The complementary-slackness equations and the direct sufficiency argument are also correct.
Adding $x_iy_i=1$ and the strict objective comparison consequently characterizes $S_\infty^*>B$. The claimed variable count, cubic degree bound, and polynomial coefficient lengths are valid.
Hence membership in $\exists\mathbb R\cap\mathrm{co}\text{-}\exists\mathbb R$ follows. The output correctly distinguishes real witnesses from polynomial-size discrete certificates.
Verified.
The stated $\mathrm{PSPACE}$ upper bound follows from the existential-real formulation and the cited existential-theory decision theorem. [Canny](https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html)
The cited quantifier-elimination theorem provides arithmetic complexity and intermediate coefficient-size bounds. With one quantified block and either zero or one free variable, its specialization supports
$$
(\tau+1)^{O(\tau)}
\operatorname{poly}(m,L,\log(k+1)).
$$
The polynomial conditions here have constant degree and polynomial encoding length. Unbounded multiplier sets do not violate the theorem’s hypotheses. [Basu, Theorem 2.27](https://arxiv.org/html/1409.1534#S2.SS5.SSS2)
Existence and uniqueness make the projected coordinate and value sets singletons. The argument that a nonzero output polynomial must vanish at each singleton is valid. Standard univariate root isolation and sign determination then provide the specified algebraic representations within the claimed bound.
The distinction between polynomial-length radical expressions for individual two-vertex allocations and exact comparison of their summed objective is maintained correctly.
Verified.
For edgeless templates, each reciprocal constraint independently gives $r_i\ge k/\varepsilon$. Combining this with $r_i\ge k$ yields the displayed optimal allocation and value. The rational computations have polynomial bit complexity.
The displayed second-order-cone identity is correct under the stated sign restrictions. Its algebraic equivalence can be checked directly, so this step does not depend on an unstated theorem from Liu et al.
The output correctly refrains from inferring polynomial-time exact rational-threshold decision from the SOCP formulation.
Major issue — incomplete resolution of the assigned target. Sections 3–7 establish useful special-case equivalence, upper bounds, and exact algorithms, but no general $\mathrm{P}$ algorithm or $\mathrm{NP}$-hardness result.
This is an acknowledged limitation, not an erroneous inference. No clarification or expositional repair can complete the requested classification. A further mathematical or complexity result establishing one of the requested alternatives is needed. The existing partial results require no substantive repair.
⟨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.