Answer: —
Theorem 2 (DRC) — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe doubly robust estimator (10) is unbiased and its variance is: 1 m2 m X i=1 1 πi Var[Si(y, ℓi)] + 1 πi −1 E[Si(y, ℓi) −Si(y, ˆℓi)]2 .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a population of \(N\) workers, type masses \(\mu_t\), per-type annotation costs \(c_t\), DRC moment bounds \(V_{t,y}\) and \(D_{t,y}\), and tolerance \(\varepsilon\), choose query rates \(q_t\in[0,1]\) to minimize \(N\sum_t\mu_t c_tq_t\), subject for each label \(y\) to \(\frac{1}{N}\sum_t\mu_t\left(\frac{V_{t,y}}{q_t}+\left(\frac{1}{q_t}-1\right)D_{t,y}\right)\le\varepsilon^2\). Rates are applied independently to workers of each type, and a zero rate is permitted only when the direct estimate is exact for every label.
For one fixed item, there are \(m\ge 1\) labels and a population scale \(N\ge 1\), encoded as a binary integer. A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. No integrality of \(N\mu_t\) is required.
For each type and label, a worker's real-valued score \(Z_{t,y}\) has finite variance, and its direct estimate \(a_{t,y}\) is deterministic. The input gives nonnegative binary-rational bounds \(V_{t,y}\ge\operatorname{Var}(Z_{t,y})\) and \(D_{t,y}\ge(\mathbb E Z_{t,y}-a_{t,y})^2\), nonnegative binary-rational annotation costs \(c_t\), tolerance \(\varepsilon>0\), and budget \(B\ge0\).
Worker annotations are mutually independent conditional on the fixed item. Query indicators are independent of annotations and of one another; type \(t\) is queried with real probability \(q_t\in[0,1]\). For positive rates, doubly robust estimation uses the score contribution \(a_{t,y}+I_t(Z_{t,y}-a_{t,y})/q_t\).
A zero rate is admissible precisely when \(V_{t,y}=D_{t,y}=0\) for every label; its contribution to each variance bound is defined as zero. Otherwise all rates must be positive.
The cost minimization problem minimizes \(N\sum_t\mu_t c_tq_t\) subject to \(\frac1N\sum_t\mu_t\bigl(V_{t,y}/q_t+(1/q_t-1)D_{t,y}\bigr)\le\varepsilon^2\) for every label \(y\). Its decision version asks whether admissible rates exist with cost at most \(B\); inequalities are exact, and \(L\) is the total binary input length.
Is this decision problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For a finite list of workers, doubly robust estimation is unbiased and has variance equal to the sum of the worker variance and squared mean-discrepancy terms above, divided by the squared population size; this is a statistical identity, not a complexity classification ([source](https://arxiv.org/pdf/1906.08591)).
No result settling the exact support-encoded decision problem was identified in the literature search.
I do not establish either a uniform polynomial-time algorithm or $\mathrm{NP}$-hardness. The following strengthened partial results are proved below:
The first, third, and fourth statements strengthen the results in the supplied notes. All arguments used here are included.
I use the intended finite encoding: $\varepsilon$ and $B$ are binary-encoded rationals, and their encoding lengths are included in $L$. Without a specified finite encoding for these quantities, a Turing-machine complexity classification is not defined.
Call a type inactive if $V_{t,y}=D_{t,y}=0$ for every label. Assigning an inactive type rate zero minimizes its nonnegative cost and contributes zero to every constraint. Delete these types. If none remain, the answer is yes.
For every remaining type, put
$$
A_{t,y}=\mu_t(V_{t,y}+D_{t,y}),\qquad
b_t=N\mu_tc_t,
$$
and, for each label, put
$$
h_y=N\varepsilon^2+\sum_t\mu_tD_{t,y}.
$$
The decision inequalities become
$$
0<q_t\le1,\qquad
\sum_t\frac{A_{t,y}}{q_t}\le h_y\quad\text{for every }y,
\qquad
\sum_tb_tq_t\le B.
$$
Every $A_{t,y}$ is nonnegative, every $h_y$ is positive, and every remaining type has a positive coefficient for some label.
These coefficients have polynomial total encoding length. In particular, multiplying by binary-encoded $N$ requires arithmetic on its encoding, without expanding a population of $N$ workers.
The variance constraints are feasible if and only if
$$
\sum_tA_{t,y}\le h_y\quad\text{for every }y.
$$
Indeed, $q_t\le1$ implies $A_{t,y}/q_t\ge A_{t,y}$, and setting every rate to one simultaneously minimizes all the left-hand sides. Equivalently, the criterion is
$$
\sum_t\mu_tV_{t,y}\le N\varepsilon^2\quad\text{for every }y.
$$
Suppose this criterion holds. Define
$$
\delta_t=\max_y\frac{A_{t,y}}{h_y}>0.
$$
Every feasible rate satisfies $q_t\ge\delta_t$, because each nonnegative summand $A_{t,y}/q_t$ is at most $h_y$. Consequently, the variance-feasible set is a closed subset of
$$
\prod_t[\delta_t,1].
$$
It is compact, and the continuous linear cost attains its minimum. Thus prohibited zero rates cannot arise as limits needed to attain the optimum.
This preprocessing will justify the exact dual certificate in Section 3.
First check the variance-feasibility criterion. If it fails, reject.
A label is tight at one if
$$
\sum_tA_{t,y}=h_y.
$$
For such a label, every type with $A_{t,y}>0$ must have rate one in every feasible solution: any smaller rate would make that label’s left-hand side strictly larger than $h_y$.
Also, any remaining type with $b_t=0$ may be assigned rate one. This leaves its cost unchanged and decreases every variance expression.
Let $E$ consist of these two classes of types. Fix their rates to one, and define
$$
C_0=\sum_{t\in E}b_t,\qquad
\widehat B=B-C_0,\qquad
\widehat h_y=h_y-\sum_{t\in E}A_{t,y}.
$$
For a label tight at one, all its positive coefficients have been removed and its residual constraint is $0\le0$. Delete that constraint. Delete any other residual constraint having no positive coefficient.
Renaming the remaining coefficients, the residual optimization problem is
$$
C=\min\left\{
\sum_{i=1}^kb_iq_i:
0<q_i\le1,\
\sum_{i=1}^k\frac{a_{i,y}}{q_i}\le h_y
\text{ for every remaining }y
\right\}.
$$
Here $b_i>0$, each coordinate has a positive coefficient somewhere, and
$$
h_y>\sum_{i=1}^ka_{i,y}
$$
for every remaining label. The strict inequality follows because removing fixed coordinates subtracts the same quantity from the right-hand side and from the sum of coefficients.
If $k=0$, compare $C_0$ with $B$ directly. Otherwise, at least one label remains. Set
$$
d=\min_y\left(1-\frac{\sum_i a_{i,y}}{h_y}\right)>0,
\qquad
\bar q_i=1-\frac d2.
$$
Then $0<\bar q_i<1$, and
$$
\frac{\sum_i a_{i,y}}{h_y\bar q_i}
\le
\frac{1-d}{1-d/2}<1.
$$
Thus every residual variance inequality and every upper-rate inequality is strict at $\bar q$.
For completeness, the residual optimizer is unique. Under $x_i=1/q_i$, the feasible set becomes the compact convex polytope
$$
x_i\ge1,\qquad
\sum_i a_{i,y}x_i\le h_y,
$$
and its objective is $\sum_i b_i/x_i$. Its Hessian is diagonal with entries $2b_i/x_i^3>0$, so the objective is strictly convex. Two distinct minimizers would have a midpoint with strictly smaller objective.
Let $\exists\mathbb R$ denote the class of decision problems polynomial-time many-one reducible to feasibility of existential polynomial equalities and inequalities over the reals. Membership in $\operatorname{co}\exists\mathbb R$ means that the complement has such a reduction.
For each retained type, introduce $s_t$ and impose
$$
0\le q_t\le1,\qquad s_t\ge0,\qquad q_ts_t\ge1,
$$
together with
$$
\sum_tA_{t,y}s_t\le h_y\quad\text{for every }y,
\qquad
\sum_tb_tq_t\le B.
$$
This system is equivalent to the decision problem.
Given feasible rates, choose $s_t=1/q_t$. Conversely, the product inequality forces $q_t>0$ and $s_t\ge1/q_t$; nonnegativity of $A_{t,y}$ then implies the original variance inequalities.
All constraints have degree at most two and polynomial encoding length after clearing positive denominators. Hence the problem belongs to $\exists\mathbb R$.
The product constraint also has the rational second-order cone representation
$$
\left\|(2,q_t-s_t)\right\|_2\le q_t+s_t.
$$
Under $q_t,s_t\ge0$, squaring gives exactly $q_ts_t\ge1$.
Consider the strictly feasible residual problem from Section 2. For nonnegative multipliers $\lambda_y$ and $\eta_i$, write
$$
z_i=\sum_y\lambda_ya_{i,y}.
$$
Its Lagrangian, with domain $(0,\infty)^k$, is
$$
\mathcal L(q)
=
\sum_i\left((b_i+\eta_i)q_i+\frac{z_i}{q_i}\right)
-\sum_y\lambda_yh_y-\sum_i\eta_i.
$$
For every feasible $q$,
$$
\mathcal L(q)\le\sum_i b_iq_i.
$$
For $u>0$ and $z\ge0$,
$$
\inf_{q>0}\left(uq+\frac zq\right)=2\sqrt{uz}.
$$
For $z>0$, this follows from
$$
uq+\frac zq-2\sqrt{uz}
=
\left(\sqrt{uq}-\sqrt{z/q}\right)^2,
$$
with equality at $q=\sqrt{z/u}$. For $z=0$, the infimum is zero as $q$ tends to zero.
Therefore every nonnegative multiplier pair gives the lower bound
$$
D(\lambda,\eta)
=
2\sum_i\sqrt{(b_i+\eta_i)z_i}
-\sum_y\lambda_yh_y-\sum_i\eta_i
\le C.
$$
Here is a separation argument establishing the required strong duality.
List all residual constraint functions as $f_1,\ldots,f_r$, including both the variance residuals
$$
\sum_i a_{i,y}/q_i-h_y
$$
and the upper-rate residuals $q_i-1$. They are convex on $(0,\infty)^k$. Define
$$
U=
\left\{
(u,v):
\text{there exists }q\in(0,\infty)^k
\text{ with }f_j(q)<u_j\text{ for every }j,
\quad \sum_i b_iq_i<v
\right\}.
$$
This set is nonempty and open. It is convex: convex combinations of witnessing rates remain positive, convexity bounds each constraint function, and the cost is linear.
The point $(0,C)$ does not belong to $U$, since its membership would give a feasible rate vector of cost below $C$.
The finite-dimensional separation theorem for an open convex set and a point outside it gives a nonzero vector $(\alpha,\beta)$ satisfying
$$
\alpha\cdot u+\beta v\ge\beta C
\quad\text{for every }(u,v)\in U.
$$
The set $U$ remains unchanged under arbitrary positive increases of any coordinate. Consequently, every component of $\alpha$, and also $\beta$, is nonnegative; a negative coefficient would violate the displayed lower bound under such increases.
Moreover, $\beta>0$. Otherwise $\alpha\ne0$, and the strictly feasible point $\bar q$ from Section 2 permits a vector $u$ with every component negative and $f_j(\bar q)<u_j$. This would give $\alpha\cdot u<0$, contradicting the separation inequality.
Divide by $\beta$. By choosing $u_j$ decreasing to $f_j(q)$ and $v$ decreasing to the cost, we obtain nonnegative constraint multipliers such that
$$
\mathcal L(q)\ge C
\quad\text{for every }q\in(0,\infty)^k.
$$
Let $q^*$ be an attained optimum. Its feasibility gives $\mathcal L(q^*)\le C$, so
$$
\mathcal L(q^*)=C=\inf_{q>0}\mathcal L(q).
$$
The coordinatewise infimum calculation above now proves
$$
D(\lambda,\eta)=C.
$$
Thus the dual maximum is attained and equals the primal minimum.
For a nontrivial residual instance, the original answer is no exactly when $C>\widehat B$.
Consider the following existential system:
$$
\lambda_y\ge0,\qquad \eta_i\ge0,\qquad z_i\ge0,\qquad w_i\ge0,
$$
$$
z_i=\sum_y\lambda_ya_{i,y},
\qquad
w_i^2\le(b_i+\eta_i)z_i,
$$
$$
2\sum_iw_i-\sum_y\lambda_yh_y-\sum_i\eta_i>\widehat B.
$$
A solution supplies a dual lower bound exceeding $\widehat B$, because
$$
w_i\le\sqrt{(b_i+\eta_i)z_i}.
$$
Conversely, if $C>\widehat B$, use attaining dual multipliers and choose
$$
w_i=\sqrt{(b_i+\eta_i)z_i}.
$$
They satisfy the system.
This is a polynomial-size existential system of degree at most two. The preliminary rationally decidable cases can be mapped to fixed true or false existential formulas. Hence the complement belongs to $\exists\mathbb R$, proving
$$
\boxed{\text{the decision problem belongs to }
\exists\mathbb R\cap\operatorname{co}\exists\mathbb R.}
$$
The existential theory of the reals is decidable in polynomial space, so the problem also belongs to $\mathrm{PSPACE}$. The hypotheses are met by the polynomial-size integer-coefficient formulas obtained above. See [Canny, *Some Algebraic and Geometric Computations in PSPACE*](https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html).
These are certificates using real variables; no polynomial bound on rational certificate length has been proved.
The acceptance formulation uses at most $2\tau$ variables, degree at most two, and $m+O(\tau)$ constraints.
The fixed-dimensional real-algebraic decision theorem states that, for fixed numbers of variables and fixed degree, feasibility of polynomial equalities and inequalities with integer coefficients is decidable in time polynomial in the number of constraints, formula length, and coefficient bit length. This is a consequence of the decision algorithms and intermediate bit-size bounds in [Basu, Pollack, and Roy, *On the Combinatorial and Algebraic Complexity of Quantifier Elimination*](https://www.researchgate.net/publication/221499271_On_the_combinatorial_and_algebraic_complexity_of_quantifier_elimination).
Fix any constant $\tau_0$. For instances with $\tau\le\tau_0$, the formulation has at most $2\tau_0$ variables and degree two. Clearing denominators preserves polynomial encoding length. The theorem therefore gives an exact algorithm polynomial in $m$ and $L$.
The polynomial’s exponent may depend on $\tau_0$. This does not establish the uniform polynomial bound requested when $\tau$ is unbounded.
Define square-root-sum comparison to ask, for positive binary integers $d_1,\ldots,d_n$ and a nonnegative binary integer $K$, whether
$$
S=\sum_{i=1}^n\sqrt{d_i}\le K.
$$
This is the classical exact-arithmetic comparison problem discussed in [Allender and coauthors, *On the Complexity of Numerical Analysis*](https://eccc.weizmann.ac.il/report/2005/037/revision/1/download). The reduction below uses no assumed classification of it.
Let $M$ be the least power of two at least $n$. Pad the radicands with ones:
$$
e_i=d_i\quad(i\le n),\qquad e_i=1\quad(n<i\le M).
$$
Set
$$
K'=K+M-n,\qquad
S'=\sum_{i=1}^M\sqrt{e_i}=S+M-n.
$$
Thus $S\le K$ exactly when $S'\le K'$.
Let $d_{\max}=\max_i e_i$. Choose a positive integer $r$ with $2^r>Md_{\max}$ and put $H=2^{2r}$. Construct
$$
m=N=1,\qquad \tau=M,\qquad \mu_i=\frac1M,
$$
$$
c_i=M,\qquad V_{i,1}=Me_i,\qquad D_{i,1}=0,
\qquad
\varepsilon=2^r,\qquad B=\frac{(K')^2}{H}.
$$
All quantities are integers or dyadic rationals. The normalized inequalities are
$$
\sum_i\frac{e_i}{q_i}\le H,\qquad
\sum_iq_i\le\frac{(K')^2}{H},
\qquad 0<q_i\le1.
$$
If rates are feasible, Cauchy–Schwarz gives
$$
(S')^2
=
\left(\sum_i\sqrt{e_i/q_i}\sqrt{q_i}\right)^2
\le
\left(\sum_i e_i/q_i\right)\left(\sum_iq_i\right)
\le(K')^2.
$$
Since both sides’ square roots are nonnegative, $S'\le K'$.
Conversely, if $S'\le K'$, choose
$$
q_i=\frac{S'\sqrt{e_i}}H.
$$
These rates are positive and satisfy the caps, since
$$
S'\sqrt{e_i}\le Md_{\max}<H.
$$
Furthermore,
$$
\sum_i\frac{e_i}{q_i}=H,\qquad
\sum_iq_i=\frac{(S')^2}{H}\le B.
$$
The construction has polynomial size: $M\le2n$, and $r$ can be chosen proportional to the binary length of $Md_{\max}$. It proves a polynomial-time many-one reduction to the one-label restriction.
Assume each active type has a positive coefficient $A_{t,y}$ for exactly one label. Apply Sections 1 and 2. The residual variables partition into disjoint groups $G_y$, and the variance constraints become
$$
\sum_{i\in G_y}\frac{a_i}{q_i}\le h_y.
$$
The minimum total cost is the sum of the group minima, plus the fixed cost $C_0$.
For a nonempty group, the residual problem is
$$
\min\sum_{i=1}^{\ell}b_iq_i
\quad\text{subject to}\quad
\sum_{i=1}^{\ell}\frac{a_i}{q_i}\le h,\qquad 0<q_i\le1,
$$
where $a_i,b_i>0$ and $h>\sum_i a_i$.
Maintain a set $T$ of capped coordinates and its complement $F$. Define
$$
R=h-\sum_{i\in T}a_i,\qquad
S_F=\sum_{i\in F}\sqrt{a_ib_i},\qquad
x=\frac{S_F}{R}.
$$
Initially $T$ is empty. Always,
$$
R>\sum_{i\in F}a_i>0
$$
while $F$ is nonempty.
Choose $j\in F$ minimizing the rational threshold
$$
\rho_j=\frac{b_j}{a_j}.
$$
Test whether
$$
x^2\le\rho_j.
$$
This is equivalent to the radical comparison
$$
\sum_{i\in F}\sqrt{\frac{a_ib_i}{\rho_j}}\le R.
$$
If the test succeeds, stop. Otherwise move $j$ to $T$.
To verify this update, let $x'$ be the subsequent value. Direct subtraction gives
$$
x'-x
=
\frac{a_jx-\sqrt{a_jb_j}}{R-a_j}>0.
$$
The denominator is positive by the invariant; the numerator is positive because the failed test gives $x>\sqrt{b_j/a_j}$. Thus every previously capped threshold remains below subsequent values of $x^2$.
The procedure stops before $F$ becomes empty. With one coordinate $i$ remaining, $R>a_i$ implies
$$
x=\frac{\sqrt{a_ib_i}}R<\sqrt{\frac{b_i}{a_i}},
$$
so its test succeeds. There are at most $\ell$ tests.
At termination, define
$$
q_i^*=1\quad(i\in T),\qquad
q_i^*=x\sqrt{a_i/b_i}\quad(i\in F).
$$
The successful minimum-threshold test ensures all free rates are at most one. The update argument gives $x^2\ge b_i/a_i$ for capped coordinates.
For each $i$, differentiation shows that the strictly convex function
$$
b_iq+x^2a_i/q
$$
has its minimum over $0<q\le1$ at
$$
\min\{1,x\sqrt{a_i/b_i}\}=q_i^*.
$$
Also,
$$
\sum_i\frac{a_i}{q_i^*}
=
\sum_{i\in T}a_i+\frac{S_F}{x}
=h.
$$
For any feasible $q$, coordinatewise minimization therefore gives
$$
\sum_i b_iq_i
\ge
\sum_i b_iq_i+x^2\left(\sum_i a_i/q_i-h\right)
\ge
\sum_i b_iq_i^*.
$$
The group minimum is consequently
$$
C_y=C_{T_y}+\frac{S_{F_y}^2}{R_y},
\qquad
C_{T_y}=\sum_{i\in T_y}b_i.
$$
Put $v_i=a_ib_i$. Expanding each square yields
$$
C_y
=
C_{T_y}
+\frac{\sum_{i\in F_y}v_i}{R_y}
+\sum_{\substack{i<j\\i,j\in F_y}}
\sqrt{\frac{4v_iv_j}{R_y^2}}.
$$
Hence the overall minimum has the form
$$
\operatorname{OPT}
=
C_{\mathrm{rat}}+\sum_{\nu=1}^p\sqrt{r_\nu},
$$
where $C_{\mathrm{rat}}$ is rational, every $r_\nu$ is a positive rational, and
$$
p\le\binom{k}{2}.
$$
All these rational quantities have polynomial encoding length.
If $B-C_{\mathrm{rat}}<0$, reject. Otherwise the budget question is one rational-radical comparison:
$$
\sum_{\nu=1}^p\sqrt{r_\nu}\le B-C_{\mathrm{rat}}.
$$
An empty radical list is handled by rational comparison.
For a comparison
$$
\sum_{\nu=1}^p\sqrt{p_\nu/d_\nu}\le u/v,
$$
where $p_\nu,d_\nu,v$ are positive integers and $u\ge0$, set
$$
Q=\prod_{\nu=1}^p d_\nu,\qquad
z_\nu=\frac{p_\nu Q^2}{d_\nu}.
$$
Every $z_\nu$ is an integer, and the comparison is equivalent to
$$
\sum_{\nu=1}^p\sqrt{v^2z_\nu}\le uQ.
$$
The binary length of $Q$ is at most the sum of the denominator lengths, so this transformation has polynomial size.
The group algorithms use at most $k$ threshold queries in total, followed by at most one final budget query. Thus this restriction is polynomial-time decidable with a square-root-sum oracle.
The one-label reduction in Section 5 lies within this restriction. Therefore:
$$
\boxed{\text{When each active type affects only one label, the problem is
polynomial-time Turing equivalent to square-root-sum comparison.}}
$$
The same statement holds for the one-label restriction.
The preceding lower bound can be strengthened to instances in which every label involves exactly two active types.
Given $d_1,\ldots,d_n,K$, let $M$ be the least power of two at least $2n$. Use $M$ types of equal mass $1/M$, with
$$
N=1,\qquad c_t=M,\qquad D_{t,y}=0.
$$
For label $i$, set
$$
V_{2i-1,i}=Md_i,\qquad V_{2i,i}=M,
$$
and set all other variance bounds to zero. Types beyond $2n$ are inactive.
Let $d_{\max}=\max_i d_i$. Choose $r$ with $2^r>2d_{\max}$ and set
$$
H=2^{2r},\qquad
\varepsilon=2^r,\qquad
B=\frac{\sum_i d_i+n+2K}{H}.
$$
For each label, the normalized constraint is
$$
\frac{d_i}{q_{2i-1}}+\frac1{q_{2i}}\le H.
$$
Cauchy–Schwarz gives
$$
q_{2i-1}+q_{2i}\ge\frac{(\sqrt{d_i}+1)^2}{H}.
$$
This bound is attained by
$$
q_{2i-1}=\frac{d_i+\sqrt{d_i}}H,\qquad
q_{2i}=\frac{\sqrt{d_i}+1}H.
$$
Both rates are positive and below one: their numerators are at most $2d_{\max}$, whereas $H>2d_{\max}$.
Set inactive rates to zero. Since the pairs are disjoint, the exact optimum is
$$
\operatorname{OPT}
=
\frac{\sum_i d_i+n+2\sum_i\sqrt{d_i}}H.
$$
Thus $\operatorname{OPT}\le B$ if and only if $\sum_i\sqrt{d_i}\le K$.
All data are integers or dyadic rationals of polynomial encoding length, and $M<4n$. This proves a polynomial-time many-one reduction even with two active types per label and one affected label per active type. Section 6 supplies the matching oracle upper bound for this restriction.
The general classification remains unresolved in this argument.
The exact conic formulation and the attained dual establish real-algebraic upper bounds; they do not provide a uniform polynomial bit-complexity algorithm. The fixed-support algorithm allows an exponent depending on the support bound.
Likewise, the reductions prove square-root-sum hardness, without proving $\mathrm{NP}$-hardness. A polynomial-time algorithm for the full problem would, by Section 5, give a polynomial-time algorithm for square-root-sum comparison.
For arbitrarily overlapping label supports and unbounded support size, neither requested classification has been established.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial, rigorous partial results. I found no false mathematical step in those results. It does not resolve the requested classification for unbounded support size and arbitrary overlapping label supports, and it correctly acknowledges this limitation.
The appropriate overall status is partial. The issue preventing completion is the missing general classification, not a defect in the arguments presented.
The assumption that $\varepsilon$ and $B$ have binary rational encodings is an explicitly stated, natural interpretation of the task’s finite-input setting. The conclusions are conditional on that interpretation.
Removing inactive types is valid: setting their rates to zero is admissible, contributes zero variance, and minimizes their nonnegative costs. The remaining masses need not be renormalized; the output correctly keeps their original values.
Multiplying the variance inequality by $N$ and collecting discrepancy terms gives precisely
$$
\sum_t\frac{\mu_t(V_{t,y}+D_{t,y})}{q_t}
\le N\varepsilon^2+\sum_t\mu_tD_{t,y}.
$$
Thus the definitions of $A_{t,y}$, $b_t$, and $h_y$ are correct. All normalized coefficients have polynomial encoding length, including when $N$ is large but binary encoded.
For every positive admissible rate,
$$
\frac{A_{t,y}}{q_t}\ge A_{t,y}.
$$
Consequently, the stated feasibility criterion is necessary, and taking all retained rates equal to one proves sufficiency. Cancelling discrepancy terms gives the equivalent criterion involving only $V_{t,y}$.
Each retained type has some positive coefficient, so $\delta_t>0$. Every feasible rate satisfies the claimed lower bound, since the summands in each variance constraint are nonnegative. Under the feasibility criterion, $\delta_t\le1$.
The variance expressions are continuous on the resulting closed box, which stays away from zero in every coordinate. The feasible set is therefore compact, and the cost minimum is attained. This correctly handles the otherwise potentially troublesome exclusion of zero rates.
A label tight at one forces every coordinate with a positive coefficient in that label to have rate one. The argument uses nonnegativity correctly: decreasing any such rate strictly increases that label’s sum.
Assigning rate one to a zero-cost type preserves cost and can only improve variance feasibility. This is a valid optimization-preserving restriction.
Subtracting fixed-coordinate contributions gives the stated residual budget and constraints. For every surviving label, its slack at the all-ones vector is unchanged and strictly positive. A removed constraint with no positive coefficient has a nonnegative residual right-hand side, by the preceding feasibility check.
The construction of $\bar q$ is valid. In a nontrivial residual instance, each surviving label has positive coefficient sum, so
$$
0<d<1.
$$
The displayed bound proves strict variance feasibility, and $\bar q_i<1$ proves strict upper-rate feasibility.
The uniqueness claim also checks out: the reciprocal transformation produces a bounded convex polytope because each coordinate occurs positively in some constraint. With $b_i>0$, the stated Hessian is positive definite throughout its domain.
The constraints
$$
q_ts_t\ge1,\qquad q_t,s_t\ge0
$$
force both variables to be positive and imply $s_t\ge1/q_t$. Nonnegative variance coefficients then give the required reverse implication. Choosing $s_t=1/q_t$ proves the forward implication.
The system has polynomial size and degree at most two. Clearing positive rational denominators preserves both inequality directions and polynomial encoding length.
Squaring the stated cone inequality gives
$$
4+(q_t-s_t)^2\le(q_t+s_t)^2,
$$
which is equivalent to $q_ts_t\ge1$ under the imposed nonnegativity conditions. The cone representation is exact. The output appropriately makes no claim that this representation alone yields an exact polynomial-time algorithm.
The Lagrangian signs are correct. For feasible rates, all multiplier-weighted constraint residuals are nonpositive, so the Lagrangian is at most the primal cost.
The coordinate infimum formula is valid for $u>0$ and $z\ge0$, including the separate case $z=0$. Here $u=b_i+\eta_i>0$, as required.
The separation argument satisfies the hypotheses of its stated theorem:
Taking limits toward the constraint values gives the asserted global Lagrangian lower bound. Evaluating at an attained primal optimum yields equality, proving dual attainment. There is no unsupported assumption of dual attainment here.
The rejection formula is also equivalent to rejection. Its auxiliary inequalities imply
$$
w_i\le\sqrt{(b_i+\eta_i)z_i}.
$$
Thus any witness gives a valid dual bound exceeding $\widehat B$. Conversely, attaining multipliers supply a witness whenever $C>\widehat B$.
The strict final inequality correctly treats the boundary case: if $C=\widehat B$, the original decision answer is yes and the rejection formula is infeasible.
These arguments establish membership in $\exists\mathbb R\cap\operatorname{co}\exists\mathbb R$. The subsequent polynomial-space implication is supported by the cited [Canny report](https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html), which establishes polynomial-space decidability of the existential theory of the reals. The polynomial-size integer-coefficient formulas meet the required input conditions.
The acceptance system has at most $2\tau$ variables and degree at most two. Fixing $\tau_0$ fixes the dimension and degree while allowing the number of constraints and coefficient lengths to grow.
The cited [Basu–Pollack–Roy paper](https://www.researchgate.net/publication/221499271_On_the_combinatorial_and_algebraic_complexity_of_quantifier_elimination) supplies existential decision bounds and intermediate integer bit-size bounds sufficient for the stated fixed-dimension consequence. The hypotheses are satisfied after denominator clearing.
The output correctly distinguishes this result from a uniform polynomial-time algorithm: the exponent may depend on $\tau_0$.
Padding by ones preserves comparison because both the radical sum and threshold increase by $M-n$. The masses are positive dyadic rationals summing to one, and the constructed normalized coefficients are exactly $e_i$ and unit costs.
The Cauchy–Schwarz calculation gives the forward implication. Since $K'\ge0$, passing from
$$
(S')^2\le(K')^2
$$
to $S'\le K'$ is legitimate.
For the converse, the proposed rates satisfy
$$
S'\sqrt{e_i}\le Md_{\max}<H,
$$
so they are positive and below one. Direct substitution gives variance sum $H$ and cost $(S')^2/H$, exactly as claimed.
Padding adds only linearly many types, and $H$ has polynomial binary length. This is a valid polynomial-time many-one reduction. It establishes square-root-sum hardness, without establishing $\mathrm{NP}$-hardness.
When each active type affects exactly one label, the feasible set decomposes into independent groups and the minimum cost is additive.
For each group, the invariant
$$
R>\sum_{i\in F}a_i>0
$$
follows directly from $h>\sum_i a_i$. The threshold comparison is algebraically equivalent to the displayed radical comparison.
The update formula for $x'-x$ is correct. A failed test makes its numerator positive, so previously capped coordinates remain capped as $x$ increases. The single-coordinate calculation proves termination before the free set becomes empty.
At termination, all proposed rates satisfy their caps, and the variance constraint holds with equality. The coordinatewise minimization argument proves optimality with the correct inequality directions. Equality in a threshold test causes no problem.
Expanding $S_F^2/R$ gives precisely the stated rational part and positive radical terms. There are at most quadratically many terms, each with polynomial encoding length.
The conversion of rational-radical queries to integer-radicand queries is correct:
$$
\sqrt{v^2z_\nu}=vQ\sqrt{p_\nu/d_\nu}.
$$
The denominator product has polynomial binary length. Negative rational thresholds and empty radical lists are handled explicitly.
The resulting polynomial-time oracle algorithm, together with the one-label reduction, establishes the claimed polynomial-time Turing equivalences.
Each pair has normalized variance coefficients $d_i$ and $1$, and both active types have unit normalized cost. Cauchy–Schwarz gives the stated lower bound on the pair’s cost.
The proposed rates attain that bound and make the pair’s variance sum exactly $H$. Their numerators are at most $2d_{\max}$, so the chosen $H$ makes both rates strictly below one.
Independent pairs allow their minima to be summed. The resulting optimum and budget comparison are exactly equivalent to the original square-root-sum comparison. Inactive padding types are valid and may receive rate zero.
The support size and full coefficient table remain polynomial in the source input size. This strengthens the square-root-sum reduction as claimed.
None of the established results proves a running time polynomial in $m,\tau,L$ for arbitrary instances, or proves $\mathrm{NP}$-hardness.
This is not a false claim by the prover: the output expressly disclaims resolution. Nevertheless, it leaves the principal assignment unfinished.
Minimum additional requirement: provide either a complete uniform exact polynomial-time algorithm with its bit-complexity analysis, or a complete polynomial-time reduction establishing $\mathrm{NP}$-hardness. Further clarification of the existing arguments alone cannot settle the target.
⟨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.