Answer: —
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf k-RUMM over m alternatives is identifiable, and the means of the utility distributions of all alternatives in all RUM components are bounded in close intervals [0, C], then Algorithm 2 is consistent.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For the paper's fixed-variance Gaussian location-family RUM, given \(m\) alternatives, \(k\), rational \(C,\epsilon>0\), and a rational distribution \(\mu\) of mass over \(\tau\) complete rankings, find rational mixture weights \(\alpha\) and component means \(\theta^{(r)}\) with \(\alpha\) in the simplex, \(\sum_i\theta_i^{(r)}=0\), and \(\theta_i^{(r)}\in[-C,C]\), whose objective is within \(\epsilon\) of the global minimum of \(G_\mu(\alpha,\theta)=\sum_{i<j}\left(\sum_{V:a_i\succ_V a_j}\mu_V-\sum_{r=1}^k\alpha_r\Phi((\theta_i^{(r)}-\theta_j^{(r)})/\sqrt{2})\right)^2\). What is the complexity of this task in \(m,k,\tau\), the input bit length, and \(\log(1/\epsilon)\), in the correctly specified, pairwise-identifying regime?
Let \(m\ge2\), \(k\ge1\), and let \(C,\epsilon>0\) be binary rationals. A society \(\mu\) is given by its support: \(\tau\) strict complete rankings with positive binary-rational masses summing to \(1\); \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
An admissible parameter \(x=(\alpha,\theta)\) satisfies \(\alpha_r\ge0\), \(\sum_{r=1}^k\alpha_r=1\), \(\sum_{i=1}^m\theta_i^{(r)}=0\), and \(\theta_i^{(r)}\in[-C,C]\). Its ranking law selects component \(r\) with probability \(\alpha_r\), independently draws utilities \(U_i\sim\mathcal N(\theta_i^{(r)},1)\), and ranks alternatives by decreasing utility; utility ties have probability zero.
Write \(\Phi\) for the standard normal CDF, \(b_{ij}=\sum_{V:a_i\succ_V a_j}\mu_V\), \(p_{ij}(x)=\sum_{r=1}^k\alpha_r\Phi((\theta_i^{(r)}-\theta_j^{(r)})/\sqrt2)\), and \(G_\mu(x)=\sum_{i<j}(b_{ij}-p_{ij}(x))^2\).
Promise: \(\mu\) is the ranking law of an admissible real parameter \(x_*\) having strictly positive weights and pairwise distinct component mean vectors. Moreover, every admissible real \(x\) satisfying \(p_{ij}(x)=b_{ij}\) for all \(i<j\) equals \(x_*\) up to component permutation. No quantitative separation or conditioning bound is promised.
The computational task is to return an admissible rational \(\widehat x\) satisfying \(G_\mu(\widehat x)\le\min_{x\text{ admissible real}}G_\mu(x)+\epsilon\).
Is this promised approximation task solvable in time polynomial in \(m,k,\tau,L\), and \(\max\{0,\log(1/\epsilon)\}\), or is it NP-hard?
For finite ranking samples, a [GMM consistency result](https://ojs.aaai.org/index.php/AAAI/article/download/11727/11586) asserts asymptotic consistency for bounded identifiable mixtures; its proof requires identification by the chosen moments and supplies no polynomial-time guarantee for global minimization.
[Generic identifiability from full ranking distributions](https://ojs.aaai.org/index.php/AAAI/article/download/11727/11586) is established when \(m\ge\max\{4k-2,6\}\); this does not establish identification from pairwise marginals alone.
No result settling the stated rational-input, promised approximation task was located.
The general polynomial-time versus NP-hardness classification remains unresolved.
I prove an additional structural restriction on the promise:
If $m\ge3$ and $k=\binom m2$, every component mean vector of the promised parameter lies on the boundary of the allowed mean set.
The argument establishes a stronger geometric fact: every attainable pairwise-moment vector has a representation using at most $\binom m2$ boundary mean vectors. I also give identifiable boundary mixtures showing that pairwise uniqueness alone does permit multiple components. These examples do not establish the exact rational-input promise.
For completeness, I supply self-contained proofs of the quasipolynomial upper bound, polynomial-time solvability for $k=1$, and a restriction on promise-preserving hardness reductions. The restriction extends to a precisely defined class of adaptive reductions.
Set
$$
n=\binom m2,\qquad
H=\left\{\theta\in\mathbb R^m:\sum_i\theta_i=0\right\},
\qquad
D_C=H\cap[-C,C]^m.
$$
Throughout, the interior and boundary of $D_C$ are taken relative to $H$.
Define
$$
h(d)=\Phi(d/\sqrt2),
\qquad
F(\theta)=\bigl(h(\theta_i-\theta_j)\bigr)_{i<j}.
$$
The pairwise-moment vector of a parameter is
$$
p(x)=\sum_{r=1}^k\alpha_rF(\theta^{(r)}).
$$
Every component assigns positive probability to every strict ranking. Indeed, its joint Gaussian utility density is positive everywhere, and the utility region defining any fixed strict ranking is a nonempty open subset of $\mathbb R^m$.
Consequently, every promised input satisfies
$$
\tau=m!,
\qquad
0<b_{ij}<1.
$$
Exact realizability also gives
$$
G_\mu(x_*)=0.
$$
Since $G_\mu$ is nonnegative, its minimum is zero. Thus the promised task is to produce an admissible rational parameter with
$$
G_\mu(\widehat x)\le\epsilon.
$$
Write $v_r=F(\theta_*^{(r)})$.
First, $v_1,\ldots,v_k$ are affinely independent. Otherwise there would be nonzero real coefficients $c_r$ with
$$
\sum_rc_r=0,\qquad \sum_rc_rv_r=0.
$$
For sufficiently small nonzero $t$, all weights $\alpha_{*,r}+tc_r$ remain positive. Changing the weights this way preserves their sum and all pairwise moments. Because the mean vectors are distinct and unchanged, the resulting parameter is not a permutation of $x_*$. This contradicts uniqueness.
Hence $k\le n+1$. To exclude $k=n+1$, choose $\gamma\in D_C$ different from $\theta_*^{(1)}$ and replace the first mean vector by
$$
\theta^{(1)}(t)=(1-t)\theta_*^{(1)}+t\gamma.
$$
Let $M(t)$ have columns
$$
(1,F(\theta^{(1)}(t))),\quad (1,v_2),\ldots,(1,v_k).
$$
When $k=n+1$, affine independence makes $M(0)$ invertible. For sufficiently small $t$, the vector
$$
\beta(t)=M(t)^{-1}(1,b)
$$
is well-defined and has positive coordinates, by continuity and positivity of $\alpha_*$. Its defining equation gives weights summing to one and exactly the original moments.
For sufficiently small positive $t$, the perturbed mean differs from every original mean vector. This again contradicts uniqueness. Therefore
$$
k\le n.
$$
The following property is specific to the Gaussian comparison function and yields the new boundary restriction.
The comparison function has the expansion
$$
h(d)=\frac12+\frac1{2\sqrt\pi}
\left(d-\frac{d^3}{12}+\cdots\right).
$$
Suppose, for coefficients $c_{ij}$, that
$$
f(\theta)=\sum_{i<j}c_{ij}h(\theta_i-\theta_j)
$$
is constant on $H$. Its homogeneous cubic Taylor term must vanish, so
$$
\sum_{i<j}c_{ij}(\theta_i-\theta_j)^3=0
\qquad(\theta\in H).
$$
This polynomial depends only on coordinate differences. Subtracting the average coordinate therefore shows that it vanishes on all of $\mathbb R^m$.
For $i<j$, the coefficient of the monomial $\theta_i^2\theta_j$ is $-3c_{ij}$. Thus every $c_{ij}$ is zero.
In particular, the affine hull of $F(D_C)$ is $\mathbb R^n$: an affine relation holding on $D_C$ would hold on a neighborhood of zero in $H$, and its cubic term gives the same conclusion.
Direct differentiation gives
$$
h'(d)=\frac1{2\sqrt\pi}e^{-d^2/4},
\qquad
h''(d)=-\frac d2h'(d).
$$
For $d=\theta_i-\theta_j$,
$$
\Delta_{\mathbb R^m}h(d)=2h''(d)=-dh'(d),
$$
whereas
$$
\theta\cdot\nabla h(d)=dh'(d).
$$
Hence every linear functional $f$ as above satisfies
$$
\Delta_Hf+\theta\cdot\nabla_Hf=0.
$$
The restriction to $H$ is valid because $f$ is invariant under adding a common constant to all coordinates. Its first and second derivatives in the direction orthogonal to $H$ therefore vanish.
Lemma. For $m\ge3$, every nonzero linear functional of $F$ has no local maximum or local minimum anywhere in $H$.
Proof. The function $f$ is real analytic and nonconstant by Section 2.1. At any $\theta_0\in H$, its Taylor expansion therefore has a first nonzero homogeneous term after its constant term.
Suppose $\theta_0$ were a local extremum. Its gradient would vanish, so this first term, denoted $Q_\ell$, would have degree $\ell\ge2$. In coordinates $y$ centered at $\theta_0$, the differential identity becomes
$$
\Delta_Hf(\theta_0+y)+(\theta_0+y)\cdot\nabla_Hf(\theta_0+y)=0.
$$
The term of degree $\ell-2$ is exactly $\Delta_HQ_\ell$. Thus
$$
\Delta_HQ_\ell=0.
$$
Let $S$ be the unit sphere in $H$. The divergence theorem and homogeneity imply
$$
0=\int_{\{\|y\|\le1\}}\Delta_HQ_\ell(y)\,dy
=\int_S\nabla_HQ_\ell(y)\cdot y\,dS(y)
=\ell\int_SQ_\ell(y)\,dS(y).
$$
At a local minimum, the Taylor expansion along every ray would give $Q_\ell(y)\ge0$ on $S$. Since $Q_\ell$ is nonzero and continuous, its integral would then be strictly positive. At a local maximum it would be strictly negative. Both contradict the displayed identity. $\square$
Proposition. If $m\ge3$, then
$$
\operatorname{conv}F(D_C)
=
\operatorname{conv}F(\partial D_C).
$$
Moreover,
$$
F(\operatorname{int}D_C)
\subset
\operatorname{int}\bigl(\operatorname{conv}F(D_C)\bigr),
$$
where the second interior is in $\mathbb R^n$.
Proof. Every nonzero linear functional of $F$ attains its maximum on the compact set $D_C$. By Section 2.3, no maximizer can lie in its interior. Its maximum is therefore attained on $\partial D_C$.
The convex hull of $F(\partial D_C)$ is compact. To justify this, the usual affine-dependence elimination shows that every point in a convex hull in $\mathbb R^n$ uses at most $n+1$ points. The hull in question is consequently the continuous image of a compact set consisting of $n+1$ boundary points and their simplex weights.
If some $F(\theta)$ lay outside this compact convex hull, a separating linear functional would give
$$
c\cdot F(\theta)>
\max_{\eta\in\partial D_C}c\cdot F(\eta),
$$
contradicting the preceding maximum property. This proves equality of the hulls.
The hull has full dimension by Section 2.1. If $\theta$ is interior but $F(\theta)$ lies on its boundary, a supporting hyperplane supplies a nonzero $c$ for which $\theta$ maximizes $c\cdot F$ over $D_C$. This contradicts Section 2.3. $\square$
I use the following elementary refinement of the convex-hull representation bound.
Lemma. If $S\subset\mathbb R^n$ is path connected, every point in $\operatorname{conv}S$ is a convex combination of at most $n$ points of $S$.
Proof. Affine-dependence elimination first gives a representation using at most $n+1$ points. The only remaining case consists of affinely independent points $s_0,\ldots,s_n$ with strictly positive weights.
Choose a continuous path $\gamma:[0,1]\to S$ from $s_0$ to $s_1$. Put
$$
T=\left\{t:b\in\operatorname{conv}
\{\gamma(t),s_1,\ldots,s_n\}\right\}.
$$
The set $T$ is closed: for convergent sequences of parameters, a convergent subsequence of the simplex weights supplies a representation at the limit.
Let $t_*$ be the largest number such that $[0,t_*]\subseteq T$. If $t_*<1$, affine independence and strict positivity of the barycentric weights at $t_*$ would persist in a neighborhood of $t_*$, contradicting maximality. Thus, at $t_*$, either a weight is zero or the points are affinely dependent. If $t_*=1$, the points are dependent because $\gamma(1)=s_1$.
A zero weight removes a point. In the dependent case, choose a nonzero affine dependence and adjust the weights along it until a weight first reaches zero. This preserves nonnegativity, total weight, and the represented point. Either way, at most $n$ points remain. $\square$
The boundary $\partial D_C$ is path connected for $m\ge3$. Indeed, radial projection gives a homeomorphism from the unit sphere of $H$ onto $\partial D_C$:
$$
u\longmapsto \frac{C}{\max_i|u_i|}u.
$$
That sphere has dimension $m-2\ge1$ and is path connected. Its continuous image $F(\partial D_C)$ is therefore path connected.
Combining this fact with Section 3.1 proves:
Boundary representation theorem. Every pairwise-moment vector of an admissible mixture has a representation using at most $n$ means in $\partial D_C$.
Suppose $k=n$ and some component mean of $x_*$ is interior. By the boundary representation theorem, $b$ has a representation using at most $n$ boundary means. Pad it with zero-weight components if necessary to obtain an admissible parameter with exactly $n$ components.
This parameter cannot be a permutation of $x_*$: the latter has positive weights and includes an interior mean. It nevertheless has exactly the same pairwise moments, contradicting the promise.
Thus, on promised inputs,
$$
m\ge3,\quad k=n
\quad\Longrightarrow\quad
\theta_*^{(r)}\in\partial D_C
\quad\text{for every }r.
$$
Equivalently, if any promised component mean is interior, then
$$
k\le n-1.
$$
A further consequence is useful: if $b$ lies on the boundary of $\operatorname{conv}F(D_C)$, a supporting functional $c$ satisfies
$$
c\cdot b=\max_{\theta\in D_C}c\cdot F(\theta).
$$
Positive weights force every component to attain that same maximum. Thus every component lies on $\partial D_C$ and in the same exposed moment face.
This section concerns real ranking masses. It does not construct promised binary-rational inputs.
Take $m=3$ and any $C>0$, and consider
$$
\vartheta^{(1)}=(C,0,-C),\qquad
\vartheta^{(2)}=(-C,C,0),\qquad
\vartheta^{(3)}=(0,-C,C).
$$
Define the cyclic comparison functional
$$
f(\theta)=
h(\theta_1-\theta_2)+
h(\theta_2-\theta_3)+
h(\theta_3-\theta_1).
$$
Claim. Its maximum on $D_C$ is
$$
M=2h(C)+h(-2C),
$$
and its maximizers are exactly the three vectors above.
Proof. Write $q(d)=h(d)-1/2$. This function is odd, and on $(0,\infty)$ it is strictly increasing and strictly concave.
The three cyclic differences sum to zero. If two are positive, write them as $a,b>0$, so the third is $-(a+b)$. Then
$$
f(\theta)-\frac32=q(a)+q(b)-q(a+b).
$$
Their sum $s=a+b$ is the range of the three mean coordinates, hence $s\le2C$. Strict concavity gives
$$
q(a)+q(b)-q(s)\le2q(s/2)-q(s),
$$
with equality precisely when $a=b=s/2$.
The function on the right is strictly increasing for $s>0$, since its derivative is
$$
q'(s/2)-q'(s)>0.
$$
It is positive: strict decrease of $q'$ implies $q(a)+q(b)>q(a+b)$.
If instead two cyclic differences are negative, oddness gives a value below $3/2$. If a difference is zero, the value is $3/2$. Therefore the maximum occurs exactly when the two positive cyclic differences equal $C$ and the negative one equals $-2C$. Centering gives exactly the three listed vectors. $\square$
Use the equivalent moment coordinates $(p_{12},p_{23},p_{31})$. Put
$$
u=h(C),\qquad v=h(-2C).
$$
The three moment vectors are
$$
(u,u,v),\qquad(v,u,u),\qquad(u,v,u).
$$
They are affinely independent because $u\ne v$.
A positive mixture of all three is therefore globally identifiable among admissible three-component parameters from pairwise moments. Any competing representation must have every positive-weight mean among the three maximizers, since its cyclic functional equals $M$. Uniqueness of barycentric coordinates then forces the original weights and means.
Likewise, a positive mixture of any two is identifiable among two-component parameters: its moment vector lies in the open edge joining their two moment vectors, and its barycentric coordinate at the third vertex is zero.
These examples show that boundary configurations genuinely matter. However, no argument here shows that their complete ranking probabilities are binary rational. They therefore do not settle existence or complexity under the exact input promise.
The following tools justify the computational upper bounds without inverse-conditioning assumptions.
Since $h'(d)\le1/2$, admissible parameters $x=(\alpha,\theta)$ and $y=(\beta,\eta)$ satisfy
$$
|p_{ij}(x)-p_{ij}(y)|
\le
\|\alpha-\beta\|_1+
\max_{r,\ell}|\theta_\ell^{(r)}-\eta_\ell^{(r)}|.
$$
The weight contribution is bounded by the first term because component probabilities lie in $[0,1]$. A coordinate perturbation of size $a$ changes each mean difference by at most $2a$, hence its comparison probability by at most $a$.
Lemma. Given integers $R,s\ge1$, one can construct a rational polynomial $P$ with
$$
\sup_{|d|\le R}|P(d)-h(d)|\le2^{-s}
$$
in time polynomial in $R+s$. Its degree and coefficient bit lengths are polynomial in $R+s$.
Proof. Define
$$
T_M(d)=
\sum_{j=0}^{M-1}
\frac{(-1)^jd^{2j+1}}{4^jj!(2j+1)}.
$$
Taylor’s remainder for $e^{-t^2/4}$ gives
$$
\left|T_M(d)-\int_0^d e^{-t^2/4}\,dt\right|
\le
R\frac{(R^2/4)^M}{M!}.
$$
Using $M!\ge(M/e)^M$ and $e<3$, this is at most $R2^{-M}$ whenever $M\ge3R^2/2$. Taking also
$$
M\ge s+\lceil\log_2(R+1)\rceil+4
$$
makes the error at most $2^{-s-4}$.
The constant $A=1/(2\sqrt\pi)$ has polynomial-time rational approximations to any requested binary precision. Here is a construction using the same polynomials. Gaussian normalization gives
$$
\sqrt\pi=\int_0^\infty e^{-t^2/4}\,dt,
$$
and
$$
\int_T^\infty e^{-t^2/4}\,dt
\le \frac2T e^{-T^2/4}.
$$
For precision $2^{-t}$, choose an integer cutoff proportional to $t+1$ and approximate the truncated integral with the preceding Taylor construction. Its degree and rational bit lengths are polynomial in $t$. Taking a reciprocal preserves this complexity because $\sqrt\pi>1$ and the approximations can be kept above $1/2$.
Choose rational $a$ with
$$
|a-A|\le\frac{2^{-s}}{4(R+1)}.
$$
Then $P(d)=1/2+aT_M(d)$ has the required error: the integral approximation contributes at most $2^{-s-4}/2$, and $|T_M(d)|\le R+1$ bounds the constant-approximation contribution by $2^{-s}/4$. The explicit coefficients also give the asserted bit bounds. $\square$
Set
$$
\epsilon_0=\min\{1,\epsilon\},\qquad
q=\frac{\epsilon_0}{64n},\qquad
s=\left\lceil\log_2(1/q)\right\rceil,\qquad
B=2(s+1).
$$
The Gaussian Chernoff bound yields
$$
1-h(B)\le e^{-B^2/4}\le2^{-s}\le q.
$$
For a component mean vector, sort its coordinates and let $g_j$ be the adjacent gaps. Replace each gap by $\min\{g_j,B\}$ and center the resulting coordinates. This preserves the bound $C$: the centered extremes are
$$
\theta_{(m)}=\frac1m\sum_{j=1}^{m-1}jg_j,
\qquad
\theta_{(1)}=-\frac1m\sum_{j=1}^{m-1}(m-j)g_j.
$$
Decreasing gaps lowers the maximum and raises the minimum.
The resulting vector has coordinates bounded by $mB$. For any pair, either its difference is unchanged, or both old and new differences have the same sign and absolute value at least $B$. Its comparison probability consequently changes by at most $q$.
Applying this operation to $x_*$ gives an admissible parameter $x^c$ with mean bound
$$
C'=\min\{C,mB\}
$$
and
$$
|p_{ij}(x^c)-b_{ij}|\le q.
$$
Define
$$
N=
2+m+k+\tau+L+
\left\lceil\max\{0,\log_2(1/\epsilon)\}\right\rceil.
$$
Construct $P$ from Section 5.2 on $[-2mB,2mB]$ with error at most $q$. Define
$$
\widetilde p_{ij}(x)=
\sum_r\alpha_rP(\theta_i^{(r)}-\theta_j^{(r)}).
$$
Consider the conjunction defining $K$:
This is a nonempty semialgebraic set because $x^c\in K$. Every $y\in K$ satisfies
$$
|p_{ij}(y)-b_{ij}|\le3q.
$$
The system has $v=k(m+1)$ variables and $S=O(km+n)$ polynomial constraints. Its degree $D$ and, after clearing denominators, coefficient bit length $H$ are polynomial in $N$.
For a conjunction of $S$ integer polynomial sign conditions in $v$ variables, degrees at most $D$ and coefficient bit lengths at most $H$, existential feasibility is decidable in bit time
$$
(2HSD)^{O(v)}.
$$
This is the one-block, no-free-variable specialization of [Basu’s Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf), including its intermediate bit-length bound. All formulas used here have length $O(S+v)$; thus there is no omitted arbitrary Boolean-formula length. The theorem requires no nonsingularity hypothesis.
To obtain a rational output, repeatedly bisect coordinate intervals, retaining a closed half whose intersection with $K$ and the previously retained intervals is nonempty. Such a half always exists.
Put
$$
\eta=\frac q{2k+4}.
$$
After polynomially many bisections, every interval has width at most $2\eta$. Its rational midpoint vector $u$ is within coordinate distance $\eta$ of some $y=(\alpha,\theta)\in K$.
Repair $u$ as follows. Normalize its nonnegative weight coordinates by their sum. That sum differs from one by at most $k\eta<1$, so normalization is defined and gives
$$
\|\widehat\alpha-\alpha\|_1\le2k\eta.
$$
For each mean vector, subtract its coordinate average. This creates coordinate error at most $2\eta$. If its maximum absolute coordinate $M$ exceeds $C'$, scale it by $C'/M$. Since $M\le C'+2\eta$, scaling adds error at most $2\eta$. Thus
$$
\max_{r,i}|\widehat\theta_i^{(r)}-\theta_i^{(r)}|
\le4\eta.
$$
The output is rational and exactly admissible. Forward continuity gives
$$
|p_{ij}(\widehat x)-p_{ij}(y)|
\le(2k+4)\eta=q.
$$
Therefore
$$
G_\mu(\widehat x)
\le16nq^2
=\frac{\epsilon_0^2}{256n}
\le\epsilon.
$$
There are polynomially many feasibility calls, with coefficient and endpoint bit lengths polynomial in $N$. Dense polynomial encoding, if used, has size $N^{O(v)}$ and fits the same bound. The resulting total time is $N^{O(km)}$.
On promised inputs, $\tau=m!$ implies
$$
m=O\left(\frac{\log N}{\log\log N}\right).
$$
Together with $k\le n=O(m^2)$, this gives the quasipolynomial bound
$$
2^{\,O\left((\log N)^4/(\log\log N)^3\right)}.
$$
Its exponent still prevents a uniform polynomial-time conclusion.
For one component, define $d_m=0$ and
$$
d_i=h^{-1}(b_{im})\quad(i<m).
$$
Strict monotonicity of $h$ and exact realizability give
$$
d_i=\theta_{*,i}-\theta_{*,m},
\qquad
\theta_{*,i}=d_i-\frac1m\sum_jd_j.
$$
Each marginal’s denominator is at most the product of the input mass denominators, hence at most $2^L$. Since it is strictly between zero and one,
$$
2^{-L}\le b_{im}\le1-2^{-L}.
$$
The tail bound places all $d_i$ in $[-T,T]$ for $T=2(L+1)$. On that interval,
$$
h'(d)\ge\lambda,
\qquad
\lambda=2^{-2(L+1)^2-2}.
$$
Indeed, $1/(2\sqrt\pi)>1/4$ and $e<4$.
To compute an inverse to coordinate error $a$, bisect this interval and evaluate $h$ with absolute error at most $\rho=\lambda a/4$, using Section 5.2. At a midpoint $t$:
Alternatively, stop when the interval width is at most $2a$. The evaluation precision has bit length
$$
O\bigl(L^2+\log(1/a)\bigr),
$$
and the number of bisections is polynomial.
Take $a=\epsilon_0/(16n)$. Center the resulting rational approximations, and scale if needed to enforce $C$. The repair calculation gives coordinate error at most $4a$, hence
$$
G_\mu(\widehat x)\le16na^2
=\frac{\epsilon_0^2}{16n}\le\epsilon.
$$
All computations are polynomial in the requested input and precision measures. Since $m=2$ forces $k=1$, that promised case is also settled.
The algorithm in Section 6.1 produces outputs of polynomial bit length. Its approximation tools give a polynomial-time verifier:
$$ |\widetilde p_{ij}(x)-b_{ij}|\le5q \qquad(i<j). $$
The constructed output is accepted: its true moment error is at most $4q$, and polynomial approximation adds at most $q$.
Conversely, every accepted output has true moment error at most $6q$, giving
$$
G_\mu(x)\le36nq^2
=\frac{9\epsilon_0^2}{1024n}<\epsilon.
$$
Thus acceptance is sound. A fixed polynomial bound on witness length can be imposed, since all bisection endpoints and repaired rational coordinates have polynomial bit length.
No inverse-conditioning bound is used. Consequently, under $\mathrm P=\mathrm{NP}$, accepted witnesses can be found in polynomial time by Boolean-circuit encoding and satisfiability self-reduction.
Consider a deterministic polynomial-time oracle procedure deciding satisfiability and using this search task. Assume:
These are explicit robustness requirements; the conclusion below is restricted to this reduction notion.
For an unsatisfiable formula, guess a complete oracle transcript in which each answer is an accepted polynomial-size witness from Section 7.1. Verify the answers and simulate the procedure, accepting the certificate only if its final answer is “unsatisfiable.”
Such a transcript exists: each query is promised, so it has an accepted witness. The transcript has polynomial length.
For a satisfiable formula, every verified answer is a valid approximation output. Inductively, the simulated history is therefore a valid oracle history. The reduction’s correctness excludes an “unsatisfiable” final answer.
Unsatisfiability would consequently belong to $\mathrm{NP}$, implying
$$
\mathrm{NP}=\mathrm{coNP}.
$$
This extends the analogous one-query obstruction to robust adaptive reductions. It does not prove a polynomial-time algorithm and does not address reductions that fail these requirements.
The new boundary theorem restricts the possible identifiable instances but does not remove the dimension-dependent exponent in the algorithm. The identifiable boundary examples also leave the exact rational-mass requirement unproved.
A complete classification still requires either a uniform polynomial-time algorithm or a hardness reduction preserving exact rational realizability and global pairwise uniqueness, under a stated reduction notion. The cited GMM result does not supply such an algorithm: its [Algorithm 2 and consistency proof](https://ojs.aaai.org/index.php/AAAI/article/download/11727/11586) invoke global minimization and global moment identification without a polynomial-time minimization guarantee.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but it does not resolve USER_TASK. The structural restriction, quasipolynomial upper bound, single-component algorithm, and conditional restriction on robust reductions are sound in substance. I found no false central step. Two numerical implementation details need minor clarification.
The appropriate adjudication is partial, with the general complexity classification unresolved.
Verified. A Gaussian component has a strictly positive density throughout $\mathbb R^m$. Each strict ranking corresponds to a nonempty open utility region, so every ranking has positive probability. Consequently, the explicitly listed support must satisfy
$$ \tau=m!. $$
Every pairwise comparison and its reverse have positive probability, yielding $0<b_{ij}<1$.
Exact realizability supplies $G_\mu(x_*)=0$, and nonnegativity of the objective makes this the global minimum. The reduction of the requested guarantee to $G_\mu(\widehat x)\le\epsilon$ is correct.
Verified. An affine dependence among the component moment vectors allows a nonzero weight perturbation preserving the total weight and all moments. Strict positivity of the original weights ensures that sufficiently small perturbations remain admissible.
Distinct component means ensure that changing these weights cannot merely permute the original parameter. Thus the affine-independence conclusion and $k\le n+1$ follow.
The exclusion of $k=n+1$ is also valid:
The resulting parameter contradicts the stated uniqueness promise. Therefore $k\le n$ is established, including the consequence that $m=2$ forces $k=1$.
Verified. The cubic Taylor coefficient of $h$ is nonzero. Therefore constancy of the proposed functional forces
$$ \sum_{i<j}c_{ij}(\theta_i-\theta_j)^3=0 $$
on $H$.
The extension of this polynomial identity to $\mathbb R^m$ is justified by invariance under common coordinate translation. The coefficient of $\theta_i^2\theta_j$ is indeed $-3c_{ij}$, with no contribution from any other pair. Hence all coefficients vanish.
The same argument applies to an affine relation holding on $D_C$, because $C>0$ makes zero a relative interior point. The claimed full affine dimension follows.
Verified. Both derivatives are correct:
$$ h'(d)=\frac{1}{2\sqrt\pi}e^{-d^2/4}, \qquad h''(d)=-\frac d2h'(d). $$
For a coordinate difference, the ambient Laplacian contributes $2h''(d)$, and the drift term contributes $dh'(d)$. Their sum vanishes.
Translation invariance removes the normal derivative and normal second derivative, so restriction to $H$ is valid.
Verified. Analyticity and nonconstancy ensure a first nonzero Taylor term at every point. At a local extremum, its degree is at least two.
In the differential identity, the term of degree $\ell-2$ comes only from $\Delta_HQ_\ell$; the drift terms begin at higher degree. Thus $Q_\ell$ is harmonic.
The divergence-theorem calculation and homogeneity identity are correct. At a local minimum, $Q_\ell$ must be nonnegative on the sphere; at a local maximum, it must be nonpositive. Because it is nonzero and continuous, either sign condition contradicts its zero integral.
No missing substantive hypothesis was found.
Verified. Compactness ensures that every linear functional attains its maximum on $D_C$. The preceding lemma excludes interior maximizers for every nonzero functional.
The compactness argument for the boundary convex hull is valid: affine-dependence elimination bounds the representation size by $n+1$, after which compactness follows from the compact parameter space of points and weights.
Separation then proves equality of the two convex hulls. The supporting-hyperplane argument for interior means mapping into the interior of the full-dimensional moment hull is also valid.
Verified. The proof correctly handles the only remaining case after affine-dependence elimination: $n+1$ independent points with positive weights.
The set of feasible path parameters is closed by compactness of the weight simplex. At the endpoint of its initial feasible interval, independence and strictly positive barycentric coordinates would permit continuation. Consequently, either dependence or a zero weight occurs. Both permit removal of a point.
The radial map is a homeomorphism onto $\partial D_C$, and the sphere is path connected for $m\ge3$. Thus the representation by at most $n$ boundary means follows.
Verified. When $k=n$, a boundary representation supplies a competing admissible parameter with at most $n$ positive-weight components. Padding with zero weights is permitted by the task.
If padding is needed, the competing parameter already differs from the strictly positive original parameter. If padding is unnecessary, all competing means are boundary means, so an original interior mean again prevents equality up to permutation.
The exposed-face consequence is also correct: a positive weighted average can attain the maximum of a functional only when every component attains that maximum.
The claimed structural restriction is established.
Verified within the explicitly stated real-mass scope.
The properties of $q$ follow from the displayed derivatives. The cyclic differences sum to zero, and when two are positive their sum is the coordinate range, bounded by $2C$.
The strict-concavity bound has the stated equality condition. The derivative
$$ q'(s/2)-q'(s) $$
is strictly positive for $s>0$, so the maximum requires range $2C$ and equal positive differences. Centering then gives precisely the three listed vectors.
The cases with two negative differences or a zero difference are handled correctly.
The three moment vectors are affinely independent because $u\ne v$. The supporting functional confines every positive-weight component of any competing representation to these three means. Unique barycentric coordinates then establish the stated identification for both three-component mixtures and mixtures on an open edge.
The examples do not establish the exact rational-input promise. The prover explicitly acknowledges this limitation, so it is not an invalid use of the examples.
Verified. The derivative bound $h'(d)\le1/2$ is valid. Coordinate error at most $a$ produces difference error at most $2a$ and comparison-probability error at most $a$.
The weight contribution is bounded by the weight $\ell_1$ error because the component probabilities lie in $[0,1]$. The combined bound is correct.
Verified in substance, with one minor precision-detail omission.
The Taylor-integral remainder is correct. Using the stated factorial bound gives
$$ R\frac{(R^2/4)^M}{M!} \le R\left(\frac{3R^2}{4M}\right)^M. $$
The condition $M\ge3R^2/2$ therefore gives the asserted $R2^{-M}$ bound. The additional lower bound on $M$ supplies the claimed precision.
Gaussian normalization and the displayed tail bound are correct. The final error budget for $P$ is valid, including the bound $|T_M(d)|\le R+1$. Degree and rational coefficient sizes remain polynomial in $R+s$.
Minor issue: “choose an integer cutoff proportional to $t+1$” does not specify a cutoff or allocate errors between tail truncation, integration approximation, and reciprocal computation.
Minimum clarification: State the actual cutoff rule and the requested intermediate precisions, and verify that their combined error meets the requested approximation accuracy for $A$. This is routine numerical bookkeeping, not new mathematics.
Verified. The Gaussian tail estimate is sufficient for the chosen $B$.
The formulas for the centered extreme coordinates are correct. Decreasing gaps preserves the original coordinate bound. If a pairwise difference changes, it crosses a clipped gap, so both its old and new absolute values are at least $B$ with the same sign. Their comparison probabilities differ by at most $q$.
The compressed parameter therefore satisfies the stated mean bound and moment-error bound.
Verified. The polynomial approximation error puts the compressed parameter in $K$. Every member of $K$ has true moment error at most $3q$.
The variable count, constraint count, degree bounds, and coefficient-size bounds are consistent with the construction.
The cited [Basu Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf) supports the specialization used here: one existential block, no free variables, integer coefficients, and bounded degrees. Its arithmetic-operation and intermediate integer-size bounds yield the stated singly exponential bit bound. No regularity or nonsingularity assumption is needed. The formula-size and dense-encoding considerations do not invalidate the resulting estimate.
Verified in substance, with one minor initialization omission.
Nested closed intervals retaining nonempty intersection with $K$ give a single feasible point close to the final midpoint vector.
The weight-normalization and mean-repair bounds are correct under nonnegative midpoint weights. Centering costs at most $2\eta$ in coordinate error, and scaling costs at most another $2\eta$.
The resulting calculation gives
$$ G_\mu(\widehat x) \le16nq^2 =\frac{\epsilon_0^2}{256n} \le\epsilon. $$
Minor issue: The initial coordinate intervals are not specified. In particular, the later assertion that midpoint weight coordinates are nonnegative needs initialization within the nonnegative weight range.
Minimum clarification: State the initial intervals and their containment of $K$, including nonnegative intervals for weights. This also makes the polynomial bisection count directly verifiable.
Verified. The running time $N^{O(km)}$, together with $\tau=m!$ and $k\le n$, gives the displayed quasipolynomial bound.
This estimate does not establish a polynomial bound for variable $m$ and $k$. The prover correctly states that limitation.
Verified. Exact realizability and strict monotonicity justify the inverse-comparison reconstruction.
The denominator bound and the interval containing every inverse value are valid. The proposed $\lambda$ is a valid lower derivative bound on that interval.
The approximate-evaluation bisection rules preserve the inverse bracket, and the ambiguous-comparison case gives the stated coordinate accuracy. Centering and scaling preserve the claimed error bound. The objective estimate and polynomial precision dependence follow.
Thus polynomial-time solvability for $k=1$ is established.
Verified. The constructed output satisfies the acceptance inequalities. Conversely, acceptance implies comparison error at most $6q$, giving
$$ G_\mu(x)\le36nq^2<\epsilon. $$
Rational admissibility and polynomial evaluation are verifiable in polynomial time for polynomial-size witnesses. The extraction procedure supplies such witnesses.
The conditional search consequence under $\mathrm P=\mathrm{NP}$ is valid.
Verified under the two explicit robustness requirements.
The guessed transcript consists of sound, polynomial-size answers. On promised queries, accepted answers exist.
For a satisfiable input, induction on the transcript establishes that each verified answer is a valid oracle answer and that each succeeding query remains promised. Robust correctness excludes a final unsatisfiability answer.
For an unsatisfiable input, an accepted transcript exists and yields the required certificate. Thus the conditional conclusion $\mathrm{NP}=\mathrm{coNP}$ follows.
This is a restriction on the defined reduction class. It does not unconditionally exclude hardness or establish a polynomial-time algorithm.
Major incompleteness: The general polynomial-time versus NP-hardness question remains unanswered.
The output supplies neither a uniform polynomial-time algorithm nor a hardness reduction for the exact promised task. Its structural theorem and real-mass examples do not bridge that gap. Its quasipolynomial algorithm also does not meet the requested polynomial bound.
The final discussion of the [GMM paper](https://ojs.aaai.org/index.php/AAAI/article/download/11727/11586) is accurate: Algorithm 2 specifies minimization of the objective, and the consistency proof requires global moment identification. These statements do not supply a polynomial-time global minimization guarantee.
The prover accurately describes its own work as partial. Further clarification alone cannot settle the main question; an additional substantive complexity result is required. The established partial results remain useful.
⟨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.