Answer: —
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe solution function described by Algorithm 1 pro- duces a solution M(v), which for any v that is monotone with v∅= 0, fulfills R1 to R5, as well as F1 to F5. Sketch of proof: For each of the axioms, we will give a sketch of the proof that it is fulfilled by Algorithm 1. The detailed proofs are given in the supplementary material [7]. Due to interdependencies of the proofs, we start by proving F5 and R2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational capacities \(\mu_t\) summing to \(1\), standalone values \(b_t\), and a rational coordinatewise-monotone polynomial \(V\) on \(\prod_{t\in T}[0,\mu_t]\) with \(V(0)=0\) and \(V(x)\ge b_t\) whenever \(x_t>0\), together with a degree bound \(D\), determine whether there is a unique tuple of degree-at-most-\(D\) polynomial reward fields \(\rho_t(x)\) with an exact algebraic description, and output it if so. Require \(b_t\le\rho_t(x)\le V(x)\) for active types, \(\max_{t:x_t>0}\rho_t(x)=V(x)\), outsider rewards \(b_t\), and \(\frac{\partial \rho_t}{\partial x_s}(x)=\frac{\partial \rho_s}{\partial x_t}(x)\) for distinct active types.
A society is given by its support: a nonempty list \(T\) of \(\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.
Let \(m=\tau\) be the number of mass coordinates, \(B=\prod_{t\in T}[0,\mu_t]\), and \(A(x)=\{t:x_t>0\}\). Input also includes nonnegative rational standalone values \(b_t\), a rational polynomial \(V\) represented by its nonzero monomials with binary exponents, and a nonnegative integer degree bound \(D\) encoded in binary. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,D\).
Promise that \(V\) is coordinatewise monotone on \(B\), \(V(0)=0\), and \(V(x)\ge b_t\) whenever \(t\in A(x)\).
An admissible tuple consists of global polynomials \(\rho_t\in\mathbb R[x_1,\ldots,x_m]\) of total degree at most \(D\). For every \(x\in B\), require \(b_t\le\rho_t(x)\le V(x)\) for \(t\in A(x)\), and \(\rho_t(x)=b_t\) for \(t\notin A(x)\).
For every nonzero \(x\in B\), require \(\max_{t\in A(x)}\rho_t(x)=V(x)\); for all distinct \(s,t\in A(x)\), require \(\frac{\partial\rho_t}{\partial x_s}(x)=\frac{\partial\rho_s}{\partial x_t}(x)\). Uniqueness is among all real coefficient tuples. Exact output means a monomial list with each coefficient described by an integer polynomial and a rational interval isolating its real root.
Is deciding whether there is exactly one admissible tuple in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? What is the complexity of outputting that tuple exactly when it is unique?
For finite monotone coalition games normalized at the empty coalition, a recursive mechanism supplies feasible, individually rational, weakly efficient rewards with standalone outsider rewards and balanced reciprocity; these rewards are unique. Here discrete reciprocity means \(M_i^C-M_i^{C\setminus\{j\}}=M_j^C-M_j^{C\setminus\{i\}}\). [Verified extended result](https://arxiv.org/html/2508.13960v1).
A later result establishes a unique discrete mechanism using scaled balanced reciprocity, a different axiom. [Verified publication](https://doi.org/10.1016/j.ic.2026.105427). No result settling the precise polynomial-field problem above was located.
I use polynomial-time many-one reductions unless explicitly stated otherwise.
The following results are proved below:
Thus a polynomial-time decision algorithm would imply $\mathrm P=\mathrm{NP}$, and the problem is $\mathrm{NP}$-hard under polynomial-time Turing reductions. The conventional many-one $\mathrm{NP}$-hardness question remains unresolved here. In fact, the classification below makes it equivalent to the inclusion
$$
\mathrm{coNP}\subseteq\exists\mathbb R.
$$
Throughout, $m=\tau$, and all claims concern inputs satisfying the stated promises.
Index the support by $\{1,\ldots,m\}$.
For each $t$ and each $0<\varepsilon\leq\mu_t$, the standalone-value promise gives
$$
0\leq b_t\leq V(\varepsilon e_t).
$$
Taking $\varepsilon\to0$ and using continuity and $V(0)=0$ proves
$$
b_t=0\qquad(1\leq t\leq m).
$$
Coordinatewise monotonicity also gives $V(x)\geq0$ throughout $B$.
We use the following polynomial identity principle: a real polynomial vanishing on a nonempty open subset of $\mathbb R^m$ is identically zero. To prove it, choose an open rectangle inside that subset. Regard the polynomial as a univariate polynomial in the last variable; its vanishing on an interval forces every coefficient polynomial to vanish on the remaining rectangle. Induction on the number of variables completes the proof.
If $V$ is the zero polynomial, the reward bounds force every $\rho_t$ to vanish on the interior of $B$, hence identically. The zero tuple is admissible and unique for every $D$.
Henceforth assume $V\ne0$.
Let
$$
U=\prod_{t=1}^m(0,\mu_t).
$$
Every type is active on $U$. Efficiency therefore implies
$$
\prod_{t=1}^m\bigl(V(x)-\rho_t(x)\bigr)=0
\qquad(x\in U).
$$
The product is identically zero by the identity principle. The real polynomial ring is an integral domain, so one factor is identically zero. Consequently, there is a fixed index $i$ such that
$$
\rho_i=V.
$$
The outsider condition implies that $V$ vanishes on the face $x_i=0$. For $m>1$, its restriction to that face vanishes on a relatively open rectangle and is the zero polynomial. For $m=1$, this follows from $V(0)=0$. In either case, $x_i$ divides $V$.
Define
$$
J(V)=\{i:x_i\text{ divides }V\}.
$$
Thus existence requires $J(V)\ne\varnothing$.
Suppose $\rho_i=V$. Reciprocity on $U$ and the identity principle give the global identities
$$
\partial_i\rho_j=\partial_jV
\qquad(j\ne i).
$$
The interior reward bounds extend by continuity to all of $B$:
$$
0\leq\rho_j(x)\leq V(x).
$$
On the face $x_i=0$, the right-hand side vanishes, so every reward vanishes there. Integrating the derivative identity in coordinate $i$ therefore yields
$$
\rho_j(x)=
\int_0^{x_i}
\partial_jV(x_1,\ldots,x_{i-1},s,x_{i+1},\ldots,x_m)\,ds
\qquad(j\ne i).
$$
Introduce the polynomial
$$
F(x)=
\int_0^{x_i}
V(x_1,\ldots,x_{i-1},s,x_{i+1},\ldots,x_m)\,ds.
$$
Then the only possible tuple having winner $i$ is
$$
\rho_t=\partial_tF\qquad(1\leq t\leq m).
$$
In particular, its coefficients are rational.
Suppose, towards a contradiction, that $j\ne i$ also belongs to $J(V)$.
The integral defining $F$ shows that $F\geq0$ on $B$. Divisibility of $V$ by $x_j$ implies that $F=0$ on $x_j=0$. Moreover,
$$
\partial_iF=V,\qquad \partial_jF=\rho_j\leq V.
$$
Fix every other coordinate in its interior. Choose $u,v>0$ with
$$
u+v<\mu_i,\qquad v<\mu_j.
$$
The path having coordinates
$$
(x_i,x_j)=(u+s,v-s),\qquad 0\leq s\leq v,
$$
lies in $B$. Along it,
$$
\frac{d}{ds}F(u+s,v-s)
=\partial_iF-\partial_jF
=V-\rho_j\geq0.
$$
Hence
$$
0\leq F(u,v)\leq F(u+v,0)=0.
$$
The permitted choices of $u,v$ and the other coordinates form a nonempty open set. Thus $F$ is identically zero, contradicting $\partial_iF=V\ne0$.
We have proved
$$
\text{existence with }V\ne0
\quad\Longrightarrow\quad
J(V)=\{i\}.
$$
This determines the winner, and Section 3.2 determines the entire tuple.
Therefore every promised input has at most one admissible tuple. Existence and uniqueness are the same decision problem.
Combine repeated input monomials and remove zero coefficients, obtaining
$$
V(x)=\sum_{\alpha}c_\alpha x^\alpha
$$
with distinct exponent vectors and nonzero rational coefficients.
If $V\ne0$ and $J(V)\ne\{i\}$ for any index $i$, no admissible tuple exists.
Otherwise, define the forced candidate by
$$
R_i=V,
$$
and, for $j\ne i$, by
$$
R_j=
\sum_{\alpha:\alpha_j>0}
\frac{c_\alpha\alpha_j}{\alpha_i+1}
x^{\alpha+e_i-e_j}.
$$
Exactly one admissible tuple exists if and only if:
Here is a proof of both directions.
The candidate formula follows from Section 3.2 by integrating and differentiating each monomial. The winner is $V$, so the degree condition is necessary. Each other displayed monomial has unchanged total degree, making that condition sufficient for all degree restrictions.
For a fixed $j$, only terms with $\alpha_j=1$ survive in the restriction $R_j|_{x_j=0}$. Distinct such input terms remain distinct after restriction: the transformation increases coordinate $i$ by one and removes the fixed exponent in coordinate $j$. Their coefficients remain nonzero. Consequently, the restriction vanishes identically exactly when there are no such terms. This establishes the outsider condition.
Monotonicity implies $\partial_jV\geq0$ in the interior of $B$: each derivative is the limit of nonnegative forward difference quotients. Continuity of the derivative extends the inequality to $B$. Thus
$$
R_j(x)=\int_0^{x_i}\partial_jV(\ldots,s,\ldots)\,ds\geq0.
$$
Condition 3 supplies the other reward bound.
The tuple is the gradient of $F$, so equality of mixed polynomial derivatives gives reciprocity. If $x_i>0$, its active reward $R_i$ equals $V$, giving efficiency. If $x_i=0$, then $V=0$. Also, $F$ is divisible by $x_i^2$, because $V$ is divisible by $x_i$; hence every $R_t$ vanishes on that face. Efficiency follows there as well whenever $x\ne0$.
All requirements are therefore satisfied.
The upper-bound condition is substantive even at low degree. For example, take two masses equal to $1/2$ and
$$
V(x_1,x_2)=x_1\left(\frac{x_1^2}{8}+x_2^2\right).
$$
This polynomial satisfies all input promises, has $J(V)=\{1\}$, and passes the outsider test. Its forced second reward is
$$
R_2=x_1^2x_2.
$$
At $x_1=u>0$ and $x_2=u/2$, with $u\leq1/2$,
$$
V-R_2=-\frac{u^3}{8}<0.
$$
Thus no admissible tuple exists, even when $D\geq3$.
Let $s$ be the number of canonical nonzero monomials of $V$.
On an input promised to have a unique admissible tuple, the algorithm proceeds as follows:
No universal inequality test is needed under this additional promise.
There are at most $\tau s$ output monomials. Each nonzero coefficient is obtained from an input coefficient by multiplication by one binary-encoded exponent and division by another exponent plus one. These operations increase coefficient bit lengths only polynomially in $L$. The transformation of exponent vectors likewise requires no expansion of powers.
For a coefficient written in reduced form as $p/q$, with $q>0$, output the integer polynomial
$$
qZ-p
$$
and the rational interval
$$
\left(\frac pq-1,\frac pq+1\right).
$$
The polynomial has exactly one real root, lying strictly inside that interval, so this meets the requested exact representation.
The running time is
$$
\operatorname{poly}(m,\tau,L,\log(D+2)).
$$
An output-length bound is
$$
O\!\left(
\tau+\tau s\bigl(L+m\log(D+2)\bigr)
\right).
$$
Since the encoding of $D$ is included in $L$, both bounds are polynomial in input length.
If an algorithm must also recognize whether a unique tuple exists and report nonexistence otherwise, that recognition task has the decision complexity established below. One decision call followed by the preceding arithmetic suffices.
Define $\exists\mathbb R$ as the class of languages polynomial-time many-one reducible to existential real feasibility, and write
$$
\forall\mathbb R=\mathrm{co}\exists\mathbb R.
$$
The structural and syntactic conditions in Section 4 are polynomial-time checkable. Once they pass, failure of uniqueness is equivalent to
$$
\exists x\in\mathbb R^m:
\left(
\bigwedge_{t=1}^m 0\leq x_t\leq\mu_t
\right)
\land
\left(
\bigvee_{j\ne i}R_j(x)>V(x)
\right).
$$
This formula has polynomial encoding length even with binary exponents. Specifically, compute each power by repeated squaring, introduce an existential variable for each arithmetic gate, and impose its defining polynomial equation. For a fixed $x$, these equations force the correct gate values, so they introduce no spurious witnesses.
Thus the complement has an existential-real description of polynomial size. Formally, there is a language in $\forall\mathbb R$ agreeing with the requested decision problem on every promised input; no efficient promise verification is being assumed.
We invoke the following weakened, single-block form of Renegar’s Theorem 1.1. Given an existential sentence in $n\geq1$ real variables whose quantifier-free formula has propositional length $h$, involves $r\geq1$ densely represented integer polynomials of degree at most $\delta\geq1$, and has coefficient bit lengths at most $H$, its truth can be decided in
$$
(h+1)(H+1)^{O(1)}
\bigl[r(\delta+1)\bigr]^{O(n)}
$$
bit operations. The constants in the exponents are absolute. This formulation includes the cost of evaluating the propositional formula. [Renegar, Part I, Theorem 1.1](https://doi.org/10.1016/S0747-7171(10)80003-3).
For the failure formula above, the parameters are
$$
n=m,\qquad
r=2m+\tau-1,\qquad
h=O(m+\tau),\qquad
\delta=\max(1,D).
$$
The degree statement applies after the degree check has passed.
Clear each polynomial’s rational denominators by multiplying it by their positive product. This preserves every comparison and produces integer coefficients of bit length $\operatorname{poly}(m,\tau,L)$. There are only polynomially many sparse coefficients before this conversion.
If dense representation is required, a polynomial of degree at most $D$ has at most $(D+1)^m$ possible exponent vectors. Filling its coefficient array therefore fits within the displayed singly exponential bound.
Consequently, decision is possible in
$$
\operatorname{poly}(m,\tau,L)
\bigl[(m+\tau)(D+2)\bigr]^{O(m)}.
$$
Assume $\deg V\leq4$. Run the structural, degree, and outsider tests from Section 4. If they fail, reject. Otherwise let $J(V)=\{i\}$.
Every monomial of $V$ has positive exponent in coordinate $i$. The outsider test ensures that every exponent in a different coordinate is either zero or at least two.
A monomial involving two distinct coordinates $j,k\ne i$ would therefore have total degree at least
$$
1+2+2=5.
$$
No such monomial exists. Hence $V$ has the decomposition
$$
V(x)=P(x_i)+\sum_{j\ne i}Q_j(x_i,x_j),
$$
where each $Q_j$ consists of terms involving $x_j$.
The candidate formula now shows that $R_j$ depends only on $x_i,x_j$.
Fix $j\ne i$ and any $x\in B$, and let
$$
x'=x_i e_i+x_j e_j.
$$
Because $x'\leq x$ coordinatewise, monotonicity gives
$$
V(x)\geq V(x').
$$
The dependence just established gives $R_j(x)=R_j(x')$. Therefore
$$
V(x)-R_j(x)\geq V(x')-R_j(x').
$$
It follows that $R_j\leq V$ on the full box if and only if
$$
R_j(ue_i+ve_j)\leq V(ue_i+ve_j)
$$
throughout the rectangle
$$
0\leq u\leq\mu_i,\qquad 0\leq v\leq\mu_j.
$$
Necessity follows because this rectangle is a face of $B$; the preceding inequality proves sufficiency.
Each failure test has two real variables, five atomic predicates, degree at most four, and coefficient bit lengths polynomial in $L$. Renegar’s bound from Section 6 is therefore polynomial in $L$ for each test. There are at most $\tau-1$ tests.
Thus instances with $\deg V\leq4$ are decidable in
$$
\operatorname{poly}(m,\tau,L,\log(D+2))
$$
time, for arbitrary support size.
Let $f$ be a rational polynomial of degree at most four. We construct a promised society for which
$$
f\geq0\text{ on }[0,1]^n
\quad\Longleftrightarrow\quad
\text{exactly one admissible tuple exists}.
$$
Pad the variables to a positive power-of-two number $n$. Introduce coordinates $u,z,y_1,\ldots,y_n$, with masses
$$
\mu_u=\frac12,\qquad
\mu_z=\frac14,\qquad
\mu_{y_j}=\varepsilon=\frac1{4n}.
$$
These are positive dyadic rationals summing to one. All coordinates are support coordinates, so $m=\tau=n+2$.
Write
$$
f(w)=\sum_\alpha c_\alpha w^\alpha,
$$
and set
$$
w_j=\left(\frac{y_j}{\varepsilon}\right)^2,\qquad
S=\max\left(1,\sum_\alpha|c_\alpha|\right),
$$
$$
M=64S,\qquad
Q=16\left(S+\frac{6S}{\varepsilon}+1\right),
$$
$$
q(w)=Q+M\sum_{j=1}^n w_j,
$$
$$
H(z,y)=\left(z^2+\frac1{16}\right)q(w)+f(w),
\qquad
V(u,z,y)=uH(z,y).
$$
Set every standalone value to zero.
The substitution maps the $y$-box onto $[0,1]^n$. It replaces each source monomial by one monomial. The construction therefore has polynomial sparse encoding length and polynomial coefficient bit lengths.
If the source degree is at most $r$, the target degree is at most
$$
\max(5,2r+1).
$$
In particular, degree-four sources permit $D=9$, and degree-two sources permit $D=5$.
On the unit cube,
$$
|f(w)|\leq S,\qquad
|\partial_{w_j}f(w)|\leq4S.
$$
For the derivative bound, differentiate each monomial: its exponent is at most four, and the remaining monomial has absolute value at most one.
Since $0\leq z\leq1/4$,
$$
H\geq\frac Q{16}-S
=\frac{6S}{\varepsilon}+1>0.
$$
Also,
$$
\partial_zH=2zq\geq0.
$$
Using
$$
\frac1{16}\leq z^2+\frac1{16}\leq\frac18,
$$
we obtain
$$
0\leq
\partial_{w_j}H
=\left(z^2+\frac1{16}\right)M+\partial_{w_j}f
\leq12S.
$$
The chain rule and $0\leq y_j\leq\varepsilon$ then give
$$
0\leq\partial_{y_j}H
=\partial_{w_j}H\,\frac{2y_j}{\varepsilon^2}
\leq\frac{24S}{\varepsilon}.
$$
Consequently,
$$
\partial_uV=H>0,\qquad
\partial_zV=u\partial_zH\geq0,\qquad
\partial_{y_j}V=u\partial_{y_j}H\geq0.
$$
Integrating these derivatives along coordinate segments proves coordinatewise monotonicity on the box. Finally, $V(0)=0$ and $V\geq0$. All input promises hold.
The polynomial $V$ is divisible by $u$. Since $H$ is strictly positive everywhere on its box, $V$ does not vanish on any other coordinate face when $u>0$. Thus
$$
J(V)=\{u\}.
$$
The forced tuple is
$$
R_u=uH,\qquad
R_z=u^2zq,\qquad
R_{y_j}=\frac{u^2}{2}\partial_{y_j}H.
$$
These polynomials have the required degrees, are nonnegative, and satisfy reciprocity as the gradient of
$$
F=\frac{u^2}{2}H.
$$
They satisfy the outsider conditions: $R_u$ has a factor $u$, $R_z$ has a factor $z$, and $R_{y_j}$ has a factor $y_j$, because $H$ is a polynomial in the squared variables $y_j$.
For every $y_j$-reward, $u/2\leq1/4$ gives
$$
H-\frac u2\partial_{y_j}H
\geq
\frac{6S}{\varepsilon}+1
-\frac14\frac{24S}{\varepsilon}
=1.
$$
Hence
$$
V-R_{y_j}
=u\left(H-\frac u2\partial_{y_j}H\right)\geq0.
$$
The only remaining upper bound is
$$
V-R_z
=
u\left[
f(w)+
\left(z^2+\frac1{16}-uz\right)q(w)
\right].
$$
Because $u\leq1/2$ and $z\geq0$,
$$
z^2+\frac1{16}-uz
\geq
z^2+\frac1{16}-\frac z2
=
\left(z-\frac14\right)^2
\geq0.
$$
Therefore nonnegativity of $f$ on the unit cube implies every candidate upper bound, and Section 4 proves admissibility.
Conversely, if $f(w^*)<0$ at a cube point, choose
$$
u=\frac12,\qquad z=\frac14,\qquad
y_j=\varepsilon\sqrt{w_j^*}.
$$
These coordinates belong to the box, and
$$
V-R_z=\frac12f(w^*)<0.
$$
The sole candidate fails its upper bound, so no admissible tuple exists. This proves the reduction equivalence.
We use the following external theorem: deciding whether an integer-coefficient biquadratic form is nonnegative everywhere is $\forall\mathbb R$-complete under polynomial-time many-one reductions. A biquadratic form is homogeneous of total degree four, with degree two in each of two variable groups. [Bläser–Dutta–Jindal, Theorem 2.3](https://goravjindal.github.io/assets/pdf/soda26-hn.pdf).
Let $h$ be such a form in $N$ total variables. Homogeneity gives
$$
h\geq0\text{ on }\mathbb R^N
\quad\Longleftrightarrow\quad
h\geq0\text{ on }[-1,1]^N.
$$
Indeed, any negative value can be scaled into the centered cube by multiplying its argument by a positive scalar; its value is multiplied by the fourth power of that scalar.
Define
$$
f(w)=h(2w-\mathbf1).
$$
The affine map sends the unit cube onto the centered cube, so
$$
f\geq0\text{ on }[0,1]^N
\quad\Longleftrightarrow\quad
h\geq0\text{ on }\mathbb R^N.
$$
The polynomial $f$ has degree at most four. Expanding a degree-four monomial under this substitution produces at most
$$
\prod_j(\alpha_j+1)\leq2^{\sum_j\alpha_j}\leq16
$$
terms, so the sparse expansion has polynomial length and coefficient bit size.
Section 8 now supplies a polynomial-time, promise-preserving reduction with $D=9$. Combined with Section 6, this proves $\mathrm{co}\exists\mathbb R$-completeness.
Use the standard NP-completeness theorem for weighted MAX-CUT: given a finite undirected graph with positive integer edge weights and an integer threshold $K$, deciding whether a cut has weight at least $K$ is NP-complete. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let the edge weights be $a_{jk}$, and define
$$
f(w)=
K-\frac12-
\sum_{\{j,k\}\in E}
a_{jk}\bigl(w_j+w_k-2w_jw_k\bigr).
$$
This is a rational, multi-affine polynomial of degree at most two. At a Boolean vertex, the expression in parentheses equals one exactly when the edge crosses the cut. Thus
$$
f(w)=K-\frac12-\text{cut weight}
$$
at every Boolean vertex.
If a cut has weight at least $K$, the corresponding vertex satisfies $f\leq-1/2$.
If no such cut exists, integrality of cut weights gives $f\geq1/2$ at every Boolean vertex. For a multi-affine polynomial, repeated affine interpolation in each coordinate gives
$$
f(w)=
\sum_{v\in\{0,1\}^n}
f(v)
\prod_{j:v_j=1}w_j
\prod_{j:v_j=0}(1-w_j).
$$
The coefficients in this sum are nonnegative and sum to one on the unit cube. Therefore $f\geq1/2$ throughout that cube.
We have proved
$$
\text{no cut has weight at least }K
\quad\Longleftrightarrow\quad
f\geq0\text{ on }[0,1]^n.
$$
Applying Section 8 to this degree-two polynomial gives a promise-preserving reduction from the complement of weighted MAX-CUT to uniqueness with $D=5$. Hence uniqueness is many-one $\mathrm{coNP}$-hard already at degree five.
Negating the answer to one uniqueness-oracle call decides weighted MAX-CUT. This also proves polynomial-time Turing $\mathrm{NP}$-hardness.
The exact-output problem under the uniqueness promise is resolved: the tuple is rational and polynomial-time computable.
For decision, the proved $\mathrm{co}\exists\mathbb R$-completeness characterizes its complexity, but does not itself establish the many-one $\mathrm{NP}$-hardness branch of the requested dichotomy.
More precisely,
$$
\text{uniqueness is many-one }\mathrm{NP}\text{-hard}
\quad\Longleftrightarrow\quad
\mathrm{NP}\subseteq\forall\mathbb R
\quad\Longleftrightarrow\quad
\mathrm{coNP}\subseteq\exists\mathbb R.
$$
For necessity, compose any promise-preserving many-one reduction from an NP language with the agreeing $\forall\mathbb R$ language from Section 6. Closure under polynomial-time preimages places that NP language in $\forall\mathbb R$.
For sufficiency, if $\mathrm{NP}\subseteq\forall\mathbb R$, every NP language reduces to biquadratic nonnegativity by its completeness theorem, and then to promised uniqueness by Section 9.1.
The required inclusion is not proved here. Accordingly, the overall answer remains partial under the conventional many-one interpretation.
⟨structured verdict parsed — rendered above⟩
The output contains substantial, correct progress: its structural characterization, exact-output algorithm, and hardness reductions stand. It also correctly acknowledges that it has not settled the decision question under its stated convention of polynomial-time many-one reductions. The appropriate overall assessment is partial, rather than refuted.
I found no false central step or gap in the mathematics supporting the intermediate results. The outstanding issue is completion of the requested decision classification.
For each support coordinate, the points $\varepsilon e_t$ belong to $B$ and activate type $t$ whenever $0<\varepsilon\leq\mu_t$. Thus the standalone-value promise supplies
$$
0\leq b_t\leq V(\varepsilon e_t).
$$
Continuity at the origin and $V(0)=0$ correctly force $b_t=0$. This uses the positive masses explicitly; there is no missing support assumption.
Coordinatewise monotonicity correctly implies $V(x)\geq V(0)=0$ on $B$.
The stated polynomial identity principle and its induction argument are valid. When $V=0$, the reward bounds force every reward to vanish on the nonempty interior of $B$, and hence globally. The zero tuple satisfies all requirements, including the degree restriction for every $D\geq0$.
On the full-dimensional open box $U$, every coordinate is active. Efficiency therefore makes at least one factor in
$$
\prod_{t=1}^m(V-\rho_t)
$$
zero at each point of $U$. The identity principle makes the product the zero polynomial. Since the real polynomial ring is an integral domain, at least one entire factor is zero.
Consequently, the conclusion that a fixed index $i$ satisfies $\rho_i=V$ is justified. It does not assume that the pointwise maximizing index is initially constant.
The outsider condition then forces the restriction of $V$ to $x_i=0$ to vanish. The argument correctly treats both $m>1$ and $m=1$, establishing $x_i\mid V$.
Reciprocity on $U$ gives the polynomial identities
$$
\partial_i\rho_j=\partial_jV
$$
globally. The interior reward bounds extend to the closed box by continuity. Because $V$ vanishes on $x_i=0$, these bounds force $\rho_j$ to vanish there too.
Therefore the integration formula has the required zero boundary value; there is no undetermined integration term. The polynomial $F$ defined in the output satisfies $\partial_iF=V$, and its other partial derivatives are exactly the forced rewards.
Integration and differentiation of rational polynomial coefficients correctly imply rational coefficients for this candidate.
The path used in Section 3.3 stays inside $B$: its first coordinate runs from $u$ to $u+v<\mu_i$, and its second runs from $v<\mu_j$ to zero.
Along this path, the derivative of $F$ is $V-\rho_j\geq0$. Its terminal value is zero because $x_j\mid F$, while $F$ is nonnegative throughout the box. The resulting conclusion $F(u,v)=0$ has the correct inequality direction.
The allowed choices of $u,v$, together with the interior choices of the remaining coordinates, constitute a nonempty open subset. Thus the identity principle applies and contradicts $\partial_iF=V\ne0$.
This establishes $J(V)=\{i\}$ whenever a nonzero-value instance is feasible. Together with the forced-candidate formula, it proves uniqueness among all real coefficient tuples, as required.
The monomial formula for $R_j$ correctly follows from the written integration formula. Every surviving transformed monomial has the same total degree as its source monomial.
The outsider test is exact after canonicalization. For a fixed $j$, precisely the terms with $\alpha_j=1$ survive on $x_j=0$, and the transformation of their remaining exponent vectors is injective. Consequently, cancellation cannot invalidate the stated test.
Monotonicity correctly gives $\partial_jV\geq0$ on the interior, and continuity extends this to $B$. Hence the forced rewards are nonnegative.
Under the three stated conditions:
For a nonzero point in the last case, the active set is nonempty, so the maximum in the efficiency requirement is defined.
The illustrative counterexample is also computed correctly: at $(x_1,x_2)=(u,u/2)$, the difference is $-u^3/8$.
The additional promise permits the algorithm to output the forced candidate without deciding its universal inequalities. This is a valid distinction between promised output and recognition.
There are at most $\tau s$ output monomials. Binary exponent arithmetic and the coefficient transformations have polynomial bit complexity; no expansion proportional to the numerical degree is required.
For a reduced rational coefficient $p/q$, the polynomial $qZ-p$ and the displayed rational interval correctly isolate its unique real root. Thus the output meets the requested representation.
The running time
$$
\operatorname{poly}(m,\tau,L,\log(D+2))
$$
and the stated polynomial output-length bound are justified. The separate discussion of an algorithm that must also recognize nonexistence correctly retains the decision difficulty.
After the structural and syntactic tests pass, nonexistence is exactly a strict violation of at least one candidate upper bound at a point of the closed box.
The repeated-squaring construction handles binary exponents with polynomially many arithmetic gates. Their defining equations force the gate values, so the existential encoding introduces no spurious witnesses.
The treatment as a promise problem is appropriate: the output explicitly claims an agreeing language in $\forall\mathbb R$, rather than silently assuming efficient verification of monotonicity.
The weakened single-block bound stated in Section 6.2 is supported by Renegar’s Theorem 1.1. The application has one quantified block, integer coefficients after positive denominator clearing, and degree at most $\max(1,D)$. Dense conversion fits within the claimed bound. [Renegar, Part I, full text](https://www.researchgate.net/publication/200018947_On_the_computational_complexity_and_geometry_of_the_first-order_theory_of_the_reals_Part_I_Introduction_Preliminaries_The_geometry_of_semi-algebraic_sets_The_decision_problem_for_the_existential_theor)
The resulting decision running time
$$
\operatorname{poly}(m,\tau,L)\bigl[(m+\tau)(D+2)\bigr]^{O(m)}
$$
follows. The zero-polynomial case is already handled separately; when $m=1$, there are no competing upper-bound tests.
After the outsider test, every nonwinner exponent is either zero or at least two. A monomial involving two nonwinner coordinates would therefore have degree at least five. The stated decomposition and two-coordinate dependence of each $R_j$ follow.
Setting all other coordinates to zero preserves $R_j$ and can only decrease $V$ by monotonicity. The reduction of each full-box inequality to its two-coordinate face therefore has both directions justified.
Each resulting existential test has a fixed number of variables, predicates, and degree. The claimed polynomial running time follows from the cited bound.
The masses are positive dyadic rationals and sum to one. Padding to a power-of-two variable count has polynomial overhead. The squared substitution maps the target box onto the source cube and preserves sparse polynomial encoding size up to polynomial factors.
The bounds on $f$ and its derivatives are valid for degree at most four. The constants $M=64S$ and the displayed $Q$ correctly yield
$$
H\geq\frac{6S}{\varepsilon}+1,\qquad
0\leq\partial_{w_j}H\leq12S,\qquad
0\leq\partial_{y_j}H\leq\frac{24S}{\varepsilon}.
$$
These establish every input promise and every nonnegativity constraint.
Strict positivity of $H$ establishes $J(V)=\{u\}$. The candidate formulas, degrees, reciprocity, and outsider factors are correct.
The upper-bound estimate for every $y_j$ reward leaves the stated margin of one. For the remaining reward, the square calculation has the correct sign:
$$
z^2+\frac1{16}-uz\geq\left(z-\frac14\right)^2.
$$
At $u=1/2$ and $z=1/4$, this extra term vanishes. The specified real coordinates representing a negative source point belong to the box, including boundary source points. Thus both directions of the reduction hold.
The cited biquadratic nonnegativity theorem does state $\forall\mathbb R$-completeness. Its homogeneous quartic inputs meet the requirements of the scaling and affine-substitution argument. The expansion bound of sixteen terms per source monomial is valid. This supports the claimed completeness at $D=9$. [Bläser–Dutta–Jindal, Theorem 2.3](https://goravjindal.github.io/assets/pdf/soda26-hn.pdf)
The weighted MAX-CUT theorem is applicable. The multi-affine polynomial has exactly the stated Boolean values; the half-integer offset correctly separates the two integer cut-weight cases. Its interpolation formula transfers nonnegativity from all vertices to the cube. This establishes many-one $\mathrm{coNP}$-hardness at $D=5$ and, by reversing one oracle answer, Turing $\mathrm{NP}$-hardness. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
The final equivalence between many-one $\mathrm{NP}$-hardness and $\mathrm{coNP}\subseteq\exists\mathbb R$ follows from the established completeness and the agreeing-language treatment of the promise. The output correctly does not claim to prove that inclusion.
Outstanding issue and minimum required follow-up.
The decision branch remains unresolved under the prover’s explicitly chosen many-one convention. This is a major incompleteness relative to the assignment, not a mathematical error in the established results. To claim completion under that convention, the prover must supply the missing many-one hardness result or a polynomial-time decision result. Otherwise, it should retain its explicit partial assessment.
The exact-output question under the uniqueness promise is fully resolved by the written argument.
⟨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.