Answer: —
Theorem 5.1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateComputing the solution JSof Equation 6 is equiva- lent to computing the solution xof the ℓp-regression problem minimise ∥Bx−b∥p, (8) 3We remark that we refer to pas the ethical principle used to compute the aggregation, in accordance with the social choice literature as explained in Section 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite value labels \(V\), actions \(A\), and supported types \(T\), each with rational judgement matrices \(J_t^+,J_t^- \in [-1,1]^{|V|\times|A|}\), positive rational per-person influence \(q_t\), and positive rational mass \(\mu_t\) summing to \(1\), find any pair \(X^+,X^- \in [-1,1]^{|V|\times|A|}\) minimizing the mass-weighted disagreement for fixed \(p\in[1,\infty]\). For finite \(p\), minimize \(\left[\sum_{t\in T}\mu_t q_t\sum_{v\in V,\,a\in A}\left(|J_t^+[v,a]-X^+[v,a]|^p+|J_t^-[v,a]-X^-[v,a]|^p\right)\right]^{1/p}\); for \(p=\infty\), minimize the maximum absolute coordinate disagreement over all positive-mass types, values, actions, and signs.
Let \(V\) and \(A\) be nonempty finite sets of value labels and actions, and put \(m=|V|+|A|\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts supported types, not possible types.
Each type has positive binary-rational per-person influence \(q_t\) and binary-rational matrices \(J_t^+,J_t^-\in[-1,1]^{|V|\times|A|}\). The signs describe judgements of performing and not performing an action; no relation between the two matrices is imposed.
Fix \(p\in\mathbb{Q}\cap[1,\infty)\), or \(p=\infty\). A consensus is any pair \(X^+,X^-\in[-1,1]^{|V|\times|A|}\), with no additional constraints.
For finite \(p\), minimize \(D_p(X)=\left[\sum_{t\in T}\mu_tq_t\sum_{v\in V,a\in A}\sum_{s\in\{+,-\}}|J_t^s[v,a]-X^s[v,a]|^p\right]^{1/p}\); for \(p=\infty\), minimize \(D_\infty(X)=\max_{t\in T,v\in V,a\in A,s\in\{+,-\}}|J_t^s[v,a]-X^s[v,a]|\).
The computational problem is to find any exact minimizer. Encode each output coordinate by an integer polynomial, given by its coefficient list, and a rational interval isolating that real root. Let \(L\) be the total binary input length; use the Turing bit model.
For each fixed \(p\), is exact consensus computation solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite list of agents, judgement aggregation is equivalent to weighted \(\ell_p\)-regression; linear programming handles \(p\in\{1,\infty\}\), and the weighted arithmetic mean handles \(p=2\). [Source](https://ifmas.csc.liv.ac.uk/Proceedings/aamas2022/pdfs/p780.pdf)
For general regression with \(2\le p<\infty\), a geometrically convergent IRLS algorithm computes approximate solutions; this does not establish exact bit complexity for the supported-mass problem. [Source](https://proceedings.neurips.cc/paper/2019/file/46c7cb50b373877fb2f8d5c4517bb969-Paper.pdf)
The unrestricted problem is polynomial-time solvable for every fixed integer $p\geq 1$ and for $p=\infty$.
I do not settle the classification for unrestricted support and noninteger rational $p$. The following two additional results advance that case:
$$
2^{O_p(r_{\max})}\operatorname{poly}(m,\tau,L),
$$
where $r_{\max}$ is the largest number of distinct judgments in one coordinate. Consequently, exact computation is polynomial-time solvable when $r_{\max}$ is logarithmic in $m+\tau+L$.
These are proved below. Neither result establishes NP-hardness or a superpolynomial output-length lower bound.
Let
$$
C=V\times A\times\{+,-\}.
$$
There are
$$
|C|=2|V||A|\leq m^2/2
$$
coordinates. Write $j_{t,c}$ for a judgment and put
$$
w_t=\mu_tq_t>0.
$$
For finite $p$, the outer power in $D_p$ is strictly increasing. Hence minimizing $D_p$ is equivalent to minimizing
$$
\sum_{c\in C}f_c(x_c),
\qquad
f_c(x)=\sum_{t\in T}w_t|x-j_{t,c}|^p.
$$
The feasible set is a Cartesian product. A vector minimizes this sum if and only if each coordinate minimizes its scalar summand: replacing a nonminimizing coordinate would strictly decrease the sum.
For one coordinate, combine equal judgments and write the resulting data as
$$
a_1<\cdots<a_r,
\qquad
W_i=\sum_{t:j_{t,c}=a_i}w_t>0.
$$
Here $r\leq\tau$. Sorting and these rational operations take polynomial bit time. The resulting rational numbers have polynomial bit length: multiplying the relevant denominators produces a common denominator whose bit length is at most the sum of their bit lengths.
For $p>1$, define
$$
G_p(x)=\sum_{i=1}^r
W_i\operatorname{sgn}(x-a_i)|x-a_i|^{p-1},
$$
where a summand at $x=a_i$ is zero. Differentiation gives
$$
f_c'(x)=pG_p(x).
$$
At a judgment node, the corresponding derivative is zero because
$$
\lim_{u\to0}\frac{|u|^p}{u}=0.
$$
The function
$$
u\longmapsto \operatorname{sgn}(u)|u|^{p-1}
$$
is continuous and strictly increasing. Thus $G_p$ is continuous and strictly increasing.
If $r=1$, the unique minimizer is $a_1$. If $r\geq2$, then
$$
G_p(a_1)<0<G_p(a_r).
$$
The intermediate value theorem gives a unique zero $x_*\in(a_1,a_r)$. The derivative is negative before $x_*$ and positive after it, so $x_*$ is the unique minimizer. In particular, it belongs to $[-1,1]$.
We will repeatedly use the resulting equivalence
$$
x_*\leq z
\quad\Longleftrightarrow\quad
G_p(z)\geq0
$$
for every rational threshold $z$.
Let $W=\sum_iW_i$. Choose the smallest index $j$ satisfying
$$
\sum_{i\leq j}W_i\geq W/2.
$$
The weight strictly below $a_j$ is less than $W/2$, and the weight strictly above it is at most $W/2$.
To verify optimality, let $W_<,W_=,W_>$ denote the weights below, equal to, and above a point $x$. The left and right derivatives of the scalar objective are
$$
f'_{c,-}(x)=W_<-W_>-W_=,
\qquad
f'_{c,+}(x)=W_<-W_>+W_=.
$$
These formulas follow from the slopes of each absolute-value term. Those slopes are nondecreasing, so $x$ minimizes the objective exactly when
$$
f'_{c,-}(x)\leq0\leq f'_{c,+}(x).
$$
Equivalently, both $W_<$ and $W_>$ are at most $W/2$. Thus the selected $a_j$ is a minimizer.
All operations are exact rational operations of polynomial bit complexity.
Evaluate $G_k$ at every node. These values are rational and take polynomial bit time to compute because $k$ is fixed.
If a node value is zero, return that node. Otherwise, strict monotonicity identifies consecutive nodes satisfying
$$
G_k(a_j)<0<G_k(a_{j+1}).
$$
On their open gap, $G_k$ equals
$$
H_j(x)=
\sum_{i\leq j}W_i(x-a_i)^{k-1}
-
\sum_{i>j}W_i(a_i-x)^{k-1}.
$$
This is a rational polynomial of degree at most $k-1$. Clear its denominators to obtain an integer polynomial $P_j$.
The polynomial is nonzero because its endpoint values have opposite signs. On $(a_j,a_{j+1})$, its zeros are exactly the zeros of the strictly increasing function $G_k$. Therefore that rational interval isolates exactly one real root of $P_j$, namely the minimizer.
The polynomial has a constant number of coefficients, each of polynomial bit length. This gives a polynomial-time algorithm in the required output representation.
For $k=2$, the root is
$$
x_*=\frac{\sum_iW_ia_i}{\sum_iW_i}.
$$
For each coordinate, let
$$
\ell_c=\min_tj_{t,c},
\qquad
u_c=\max_tj_{t,c}.
$$
For every $x$,
$$
\max_t|j_{t,c}-x|
\geq
\max\{|\ell_c-x|,|u_c-x|\}
\geq
\frac{u_c-\ell_c}{2}.
$$
The last inequality follows from
$$
u_c-\ell_c\leq|\ell_c-x|+|u_c-x|.
$$
The midpoint
$$
x_c=\frac{\ell_c+u_c}{2}
$$
attains this coordinatewise lower bound. Thus the midpoint vector attains the global lower bound
$$
\max_c\frac{u_c-\ell_c}{2}
$$
and is an exact consensus minimizer.
All coordinates are rational and computable in polynomial time. For any rational output $u/v$, with integers $u,v$ and $v>0$, the polynomial
$$
vz-u
$$
and the interval $(u/v-1,u/v+1)$ give the requested encoding.
Fix a noninteger rational $p>1$ and write
$$
p-1=\gamma=\frac{a}{b},
\qquad
a,b\in\mathbb Z_{>0},
\qquad
\gcd(a,b)=1,
\qquad
b>1.
$$
The integers $a,b$ are fixed throughout this section.
We prove that a scalar instance with $r$ distinct judgments can be solved in time polynomial in $b^r$, $r$, and its input bit length.
Fix a gap
$$
I=(a_j,a_{j+1})
$$
and define $\varepsilon_i=1$ for $i\leq j$ and $\varepsilon_i=-1$ otherwise. For $x\in I$,
$$
\varepsilon_i(x-a_i)=|x-a_i|>0.
$$
Consider the algebra
$$
\mathcal R=
\mathbb Q[x,y_1,\ldots,y_r]/
\bigl(y_i^b-\varepsilon_i(x-a_i):1\leq i\leq r\bigr).
$$
As a module over $\mathbb Q[x]$, it is free of rank
$$
N=b^r
$$
with basis
$$
y_1^{e_1}\cdots y_r^{e_r},
\qquad
0\leq e_i<b.
$$
Indeed, division by the monic relations, successively in the separate variables, gives a unique remainder with these exponent bounds.
Let $M_g(x)$ be the multiplication matrix of
$$
g=\sum_i\varepsilon_iW_iy_i^a
$$
in this basis, and define
$$
Q_I(x,z)=\det(zI_N-M_g(x)).
$$
This polynomial belongs to $\mathbb Q[x,z]$ and is monic of degree $N$ in $z$.
For a real $x\in I$, evaluation at
$$
y_i=|x-a_i|^{1/b}
$$
is an algebra homomorphism. Under that homomorphism, $g$ becomes $G_p(x)$. Consequently,
$$
Q_I(x,G_p(x))=0.
$$
More explicitly, the nonzero evaluation functional satisfies
$$
\lambda(M_gv)=G_p(x)\lambda(v).
$$
It is therefore a left eigenvector with eigenvalue $G_p(x)$, which proves the determinant identity.
The matrices and polynomials have controlled size. Multiplication by $y_i^a$ reduces an exponent $e_i+a$ using at most
$$
c=\left\lceil\frac{a}{b}\right\rceil
$$
copies of the defining relation. Thus every matrix entry has degree at most $c$ in $x$, and
$$
\deg_xQ_I\leq cN,
\qquad
\deg_zQ_I=N.
$$
The entry coefficient lengths are polynomial in the input length.
The determinant can be computed in polynomial bit time in $N,r,L$. One explicit method evaluates it on a rational interpolation grid of polynomial size and interpolates. Each evaluation is an $N$-dimensional rational determinant. Its intermediate and final bit lengths are polynomially bounded: determinant expansion has at most $N!$ terms, each a product of $N$ entries. The same bounds control the interpolated coefficient lengths.
Put
$$
P_I(x)=Q_I(x,0).
$$
We must prove that this polynomial is not identically zero.
Away from the judgment nodes, each defining equation has $b$ distinct complex roots. Evaluation at every choice of these roots diagonalizes multiplication. Locally choosing analytic roots $y_i$, we obtain
$$
P_I(x)=
\prod_{\zeta_1^b=\cdots=\zeta_r^b=1}
\left(
-\sum_i\varepsilon_iW_i\zeta_i^ay_i^a
\right).
$$
If this product vanished identically, at least one analytic factor would vanish identically on a disk avoiding the nodes. Continue that identity around a loop enclosing precisely one node, say $a_i$. The corresponding root $y_i$ is multiplied by a primitive $b$th root of unity $\zeta$; every other root returns unchanged. Subtracting the continued identity from the original one gives
$$
\varepsilon_iW_i\zeta_i^a(\zeta^a-1)y_i^a=0.
$$
This is impossible. The weight is positive, $y_i$ is nonzero away from its node, and $\zeta^a\neq1$ because $\gcd(a,b)=1$.
Hence $P_I$ is nonzero. If the minimizer lies in $I$, then
$$
P_I(x_*)=0.
$$
This also proves that the unique scalar minimizer is algebraic: a minimizer at a node is rational, and every other minimizer satisfies one of these nonzero polynomials.
The polynomial $P_I$ can have extraneous roots. We now show how to test $G_p(\alpha)=0$ for any real root $\alpha\in I$ without constructing a tower of algebraic extensions.
Take the square-free part $P_0$ of $P_I$ and form
$$
R(z)=\operatorname{Res}_x(P_0(x),Q_I(x,z)).
$$
This resultant is nonzero. To see this, write the roots of $P_0$ over $\mathbb C$ as $\lambda$. Up to a nonzero constant, the resultant is the product of the polynomials
$$
Q_I(\lambda,z).
$$
Each is monic of degree $N$ in $z$, so their product is nonzero.
For the candidate $\alpha$,
$$
R(G_p(\alpha))=0.
$$
Indeed, at $z=G_p(\alpha)$, the two polynomials in the resultant have the common root $x=\alpha$.
Its degree satisfies
$$
\deg R\leq N\deg P_0\leq cN^2.
$$
Its coefficient lengths and its computation time are polynomial in $N,r,L$, by the Sylvester determinant formula and polynomial interpolation. Clear denominators to make $R$ an integer polynomial.
We use an elementary separation bound. Remove the largest power of $z$ dividing $R$ and denote the remaining polynomial by
$$
R_0(z)=a_0+a_1z+\cdots+a_dz^d,
\qquad
a_0\neq0.
$$
Let
$$
H=\max_i|a_i|\geq1,
\qquad
\kappa=\frac1{H+1}.
$$
Every nonzero root $\beta$ of $R$ satisfies
$$
|\beta|\geq\kappa.
$$
For otherwise,
$$
\left|\sum_{i=1}^da_i\beta^i\right|
\leq
H\frac{|\beta|}{1-|\beta|}
<1
\leq|a_0|,
$$
contradicting $R_0(\beta)=0$.
Therefore, a certified rational enclosure of $G_p(\alpha)$ of width less than $\kappa$ decides its sign and whether it is zero. If the enclosure contains zero, every point in it has magnitude less than $\kappa$, so the actual derivative value must be zero. If it excludes zero, its side determines the sign.
Such an enclosure takes polynomial time in $N,r,L$. Here are the precision details. On $[-2,2]$, the signed power
$$
h_\gamma(u)=\operatorname{sgn}(u)|u|^\gamma
$$
satisfies
$$
|h_\gamma(u)-h_\gamma(v)|
\leq
\begin{cases}
2|u-v|^\gamma,&0<\gamma\leq1,\\
\gamma2^{\gamma-1}|u-v|,&\gamma\geq1.
\end{cases}
$$
For the first inequality, same-sign arguments use subadditivity of $t^\gamma$; opposite-sign arguments have both magnitudes at most $|u-v|$. The second inequality follows from the mean value theorem.
Thus $O_p(s+L+\log r)$ bits of precision in $\alpha$ suffice to enclose $G_p(\alpha)$ to width $2^{-s}$. The weights have polynomial bit length. A fixed-order rational power of a nonnegative rational number can itself be enclosed by rational bisection: compare $y^b$ with $d^a$. Taking $s$ larger than $\log_2(H+1)$ by a constant suffices, and this is polynomial in $N,r,L$.
At a node $a_j$, use the finite-dimensional rational algebra
$$
\mathbb Q[y_1,\ldots,y_r]/
\bigl(y_i^b-|a_j-a_i|:1\leq i\leq r\bigr)
$$
and the element
$$
g_j=\sum_i
W_i\operatorname{sgn}(a_j-a_i)y_i^a.
$$
Its characteristic polynomial is monic of degree $N$, and $G_p(a_j)$ is a root by the same evaluation-functional argument. The separation bound and certified approximation above therefore test node values exactly in polynomial time in $N,r,L$. This remains valid when one of the defining constants is zero.
For candidate coordinates, we use deterministic univariate root isolation. The Sturm algorithm in [Strzebonski–Tsigaridas, Theorem 10](https://arxiv.org/html/1101.4369v2), applied with extension degree one, has polynomial bit complexity in polynomial degree and coefficient length. We apply it to square-free integer polynomials. Comparisons with rational gap endpoints and refinement use Sturm root counts, also in polynomial time. No expected-time isolation result is needed.
The complete scalar algorithm is now:
The minimizer either is a node or belongs to a gap, so the procedure is exhaustive. Strict monotonicity of $G_p$ guarantees exactly one accepted coordinate. For a gap candidate, the integer square-free polynomial and its rational isolating interval are valid output.
There are at most $r-1$ gaps and $cN$ candidate roots per gap. All operations have complexity polynomial in $N,r,L$. Since $N=b^r$ and $p$ is fixed, the scalar running time is
$$
2^{O_p(r)}\operatorname{poly}(r,L).
$$
Applying the procedure independently to all coordinates proves
$$
2^{O_p(r_{\max})}\operatorname{poly}(m,\tau,L).
$$
In particular, for every fixed constant $C$, it is polynomial time on instances satisfying
$$
r_{\max}\leq C\log(m+\tau+L).
$$
This strengthens the bounded-distinct-judgments case to logarithmically many distinct judgments.
Define signed square-root-sum comparison as follows: given binary-encoded integers $c_i$ and positive integers $d_i$, decide whether
$$
E=\sum_{i=1}^nc_i\sqrt{d_i}\geq0.
$$
This is the formulation used by [Eisenbrand, Haeberle, and Singer](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54), who describe polynomial-time comparison as an open problem.
Fix
$$
p=h+\frac32,
\qquad
h\in\mathbb Z_{\geq0}.
$$
Then $p-1=h+1/2$.
Define the scalar threshold problem to ask whether its unique minimizer satisfies $x_*\leq z$, where $z$ is a given rational number.
By Section 1,
$$
x_*\leq z
\quad\Longleftrightarrow\quad
G_p(z)\geq0.
$$
Omit terms for which $z=a_i$. For the remaining terms, write
$$
|z-a_i|=\frac{u_i}{v_i},
\qquad
u_i,v_i\in\mathbb Z_{>0}.
$$
Then
$$
|z-a_i|^{h+1/2}
=
\frac{u_i^h}{v_i^{h+1}}\sqrt{u_iv_i}.
$$
Consequently,
$$
G_p(z)=
\sum_i
\left(
\operatorname{sgn}(z-a_i)W_i
\frac{u_i^h}{v_i^{h+1}}
\right)\sqrt{u_iv_i}.
$$
The parenthesized coefficients are rational. Clearing their denominators yields an integer-coefficient square-root sum with the same sign.
Because $h$ is fixed, all new integer bit lengths and the construction time are polynomial in the threshold input length. This is a polynomial-time many-one reduction, including the equality case.
Start with
$$
E=\sum_{i=1}^nc_i\sqrt{d_i}.
$$
Discard zero coefficients. If no terms remain, the answer is immediate. Otherwise, combine terms having the same sign and the same radicand; retain the notation $n$ for the remaining number of terms.
Choose a power of two $M$ satisfying
$$
M>\max_i d_i
$$
and put
$$
B=\prod_{i=1}^nd_i^h.
$$
For a scalar instance, choose judgments and effective weights
$$
a_i=-\operatorname{sgn}(c_i)\frac{d_i}{M},
\qquad
W_i=|c_i|\frac{B}{d_i^h}.
$$
Every judgment is dyadic and lies in $(-1,1)$. Every weight is a positive integer.
At zero, the derivative divided by $p$ is
$$
\begin{aligned}
G_p(0)
&=
\sum_i
\operatorname{sgn}(c_i)W_i
\left(\frac{d_i}{M}\right)^{h+1/2}\\
&=
\frac{B}{M^{h+1/2}}
\sum_i c_i\sqrt{d_i}.
\end{aligned}
$$
The prefactor is positive. Therefore
$$
E\geq0
\quad\Longleftrightarrow\quad
G_p(0)\geq0
\quad\Longleftrightarrow\quad
x_*\leq0.
$$
These effective weights have an admissible society realization. Use singleton value and action sets, so $m=2$, and set the performing judgments to the $a_i$ and all nonperforming judgments to zero.
For $n\geq2$, choose
$$
\mu_i=2^{-i},
\quad
q_i=2^iW_i
\qquad(1\leq i<n),
$$
and
$$
\mu_n=2^{-(n-1)},
\qquad
q_n=2^{n-1}W_n.
$$
The masses sum to one and satisfy $\mu_iq_i=W_i$. For $n=1$, use $\mu_1=1$ and $q_1=W_1$. All numbers are positive dyadic rationals or integers.
The bit length of $B$ is at most
$$
h\sum_i\bigl(1+\log_2d_i\bigr).
$$
The bit lengths of $M$, the judgments, masses, and influences are also polynomial in the square-root-sum input length. Thus this reduction is polynomial time.
Together with Section 4.1, this proves polynomial-time equivalence of the two decision problems.
Suppose exact consensus computation for this fixed $p$ had polynomial running time. Apply it to the society constructed above. The performing coordinate is unique, so the returned polynomial and isolating interval encode $x_*$.
Its sign can be determined in time polynomial in the returned encoding length. If its isolating interval excludes zero, the sign is immediate. If the interval contains zero, test the polynomial at zero; if that value vanishes, isolation identifies zero as the encoded root. Otherwise, a Sturm root count determines which side contains the unique root.
A polynomial-time algorithm can write only polynomially many output bits. Hence this postprocessing would be polynomial in the original square-root-sum input length. We obtain the proved implication
$$
\text{polynomial-time exact consensus for }p=h+3/2
\quad\Longrightarrow\quad
\text{polynomial-time signed square-root-sum comparison}.
$$
This implication does not establish NP-hardness. It also does not address whether the required exact outputs always have polynomial length.
For the same half-integer exponents, testing whether $x_*=z$ for a given rational $z$ is polynomial-time solvable, even with unrestricted support.
Section 4.1 reduces this question to testing
$$
\sum_i c_i\sqrt{d_i}=0.
$$
We give a deterministic equality test that requires no integer factorization.
Partition the radicands into classes under
$$
d_i\sim d_j
\quad\Longleftrightarrow\quad
d_i/d_j\text{ is a square in }\mathbb Q.
$$
This relation can be tested in polynomial time: reduce the fraction and test whether both its numerator and denominator are perfect squares.
For each class, choose a representative $e_j$. Every term in that class has the form
$$
c_i\sqrt{d_i}
=
c_i\sqrt{d_i/e_j}\sqrt{e_j},
$$
where $\sqrt{d_i/e_j}$ is rational and can be computed exactly. Summing within classes gives
$$
E=\sum_{j=1}^s C_j\sqrt{e_j},
\qquad
C_j\in\mathbb Q.
$$
The radicals $\sqrt{e_j}$ belonging to distinct rational square classes are linearly independent over $\mathbb Q$. Here is a proof. Let
$$
K=\mathbb Q(\sqrt{e_1},\ldots,\sqrt{e_s}),
\qquad
G=\operatorname{Gal}(K/\mathbb Q).
$$
This is a finite Galois extension because it is the splitting field of the product of the polynomials $z^2-e_j$. For each $j$, define the character
$$
\sigma(\sqrt{e_j})=\chi_j(\sigma)\sqrt{e_j},
\qquad
\chi_j(\sigma)\in\{-1,1\}.
$$
The characters are distinct. If $\chi_j=\chi_k$, then $\sqrt{e_j/e_k}$ is fixed by every automorphism and hence rational, contradicting the choice of distinct square classes.
For a nontrivial character, summing its values over $G$ gives zero: multiplication by an element on which the character is negative pairs opposite contributions. Consequently,
$$
\sum_{\sigma\in G}\chi_j(\sigma)\sigma(E)
=
|G|C_j\sqrt{e_j}.
$$
If $E=0$, this identity forces every $C_j=0$. Conversely, those equalities plainly imply $E=0$.
The algorithm only performs rational square tests and rational sums; it does not construct $K$ or enumerate $G$. Its intermediate bit lengths are polynomially bounded. Thus equality is decidable in polynomial time, and
$$
x_*=z
\quad\Longleftrightarrow\quad
G_p(z)=0
$$
proves the claimed recognition algorithm.
The proofs completely resolve the requested exact-computation problem for fixed integer exponents and infinity. They also give a deterministic exact algorithm for every fixed rational exponent with logarithmically many distinct judgments per coordinate.
For unrestricted noninteger rational exponents, the polynomial-time versus NP-hard classification remains unproved here. The half-integer reductions identify a precise comparison barrier, but they do not settle exact output length. A superpolynomial output obstruction must be measured against the full input length $L$, and an NP-hardness conclusion requires an actual reduction from an NP-hard problem.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial correct partial results, but it does not resolve USER_TASK for every fixed rational exponent. I found no false central step in the arguments presented. The unresolved case is unrestricted support with noninteger rational $p>1$.
The appropriate overall status is partial. The incompleteness does not invalidate the proved special cases or the additional reductions.
The coordinate count is correct:
$$
2|V||A|\leq \frac{(|V|+|A|)^2}{2}.
$$
For finite $p$, removing the strictly increasing outer power preserves minimizers. The objective then separates over the Cartesian product of coordinate domains. Consequently, coordinatewise minimization is both necessary and sufficient.
The effective weights $w_t=\mu_tq_t$ are positive. Combining equal judgments preserves the scalar objective, and the stated rational arithmetic has polynomial bit complexity.
For $p>1$, the derivative formula
$$
f_c'(x)=pG_p(x)
$$
is valid, including at judgment nodes: the displayed limit establishes differentiability of the vanishing absolute-power term there.
Each signed-power summand is continuous and strictly increasing, and every weight is positive. Thus $G_p$ is continuous and strictly increasing. The endpoint signs are strict when there are at least two distinct judgments. These facts establish existence and uniqueness of the scalar minimizer and its location inside the judgment range.
The threshold equivalence
$$
x_*\leq z\quad\Longleftrightarrow\quad G_p(z)\geq0
$$
holds for every rational $z$, including equality and thresholds outside the judgment range. The single-judgment case also satisfies this equivalence.
For $p=1$, the left and right derivative formulas are correct. Their signs give exactly the weighted-median condition. The selected judgment has weight strictly below it less than half the total and weight strictly above it at most half the total. This includes the case where the cumulative weight equals half.
For fixed integer $p=k\geq2$, all node evaluations are rational and have polynomial bit length. If no node is a zero, strict monotonicity identifies a consecutive pair with opposite signs. On that gap, the displayed polynomial $H_j$ agrees with $G_k$ and has degree at most $k-1$.
Clearing denominators yields a nonzero integer polynomial. The endpoints are not roots, and the gap contains exactly one root. Therefore the gap is a valid isolating interval for the required output. Since $k$ is fixed, both the coefficient list and its construction have polynomial size and complexity.
The arithmetic-mean formula for $k=2$ is correct.
For $p=\infty$, the diameter lower bound is valid for each coordinate. The midpoint attains every coordinate’s lower bound, so the midpoint vector attains their maximum and minimizes the global objective. Its coordinates remain in $[-1,1]$. The supplied linear-polynomial encoding works for all rational outputs, including node and weighted-median outputs.
The separate monic relations give the stated free $\mathbb Q[x]$-module basis of rank
$$
N=b^r.
$$
The evaluation map on a real gap is well defined and nonzero. Its eigenvector identity correctly implies
$$
Q_I(x,G_p(x))=0.
$$
The reduction-count bound is correct: for a basis exponent $0\leq e_i<b$, reducing $e_i+a$ requires at most $\lceil a/b\rceil$ copies of the defining relation. Hence the matrix-entry degree bound and
$$
\deg_xQ_I\leq cN,\qquad \deg_zQ_I=N
$$
follow.
The determinant/interpolation construction has polynomial complexity in $N,r,L$. The matrix dimension, interpolation-grid size, degrees, and coefficient bit lengths are all polynomially bounded in those parameters. This supports the claimed exponential dependence on the number of distinct judgments.
Away from judgment nodes, each specialized defining polynomial has distinct complex roots. Evaluating at every root choice therefore gives the displayed product formula for $P_I$.
If that finite product vanished identically on a disk, one analytic factor would vanish identically. Continuing its identity around one judgment node changes only the corresponding radical branch. Subtracting the two identities leaves the stated single nonzero term.
The contradiction uses all necessary hypotheses: distinct judgment nodes, nonzero weights, nonvanishing branches away from nodes, and
$$
\gcd(a,b)=1.
$$
In particular, the monodromy multiplier raised to the power $a$ is not one.
Thus $P_I$ is nonzero. This establishes algebraicity of an interior minimizer; node minimizers are already rational. It does not establish a polynomial degree bound for unrestricted support, and the prover does not claim otherwise.
Taking the square-free part preserves every candidate root. The resultant is nonzero because, up to a nonzero constant, it is a product of polynomials $Q_I(\lambda,z)$ that are monic in $z$. For a candidate $\alpha$, the common-root argument correctly gives
$$
R(G_p(\alpha))=0.
$$
The degree bound
$$
\deg R\leq cN^2
$$
and polynomial coefficient-size bound are consistent with the construction.
The separation bound is correct. After removing the largest power of $z$, the remaining integer polynomial has a nonzero constant coefficient of magnitude at least one. The geometric-series estimate excludes every nonzero root of magnitude less than
$$
\kappa=\frac1{H+1}.
$$
The enclosure test also handles equality correctly. If an interval of width less than $\kappa$ contains zero, every point in it has magnitude less than $\kappa$. Since the actual value is a root of $R$, it must then be zero. If the interval excludes zero, its side determines the sign.
Both displayed continuity bounds for the signed power are valid on the stated domain. Together with the weight-size bounds, they justify polynomially many precision bits in $N,r,L$. Rational bisection for fixed-order powers provides certified enclosures.
The node algebra remains finite dimensional when a defining constant vanishes. Reducedness is unnecessary for the evaluation-functional argument, so the characteristic-polynomial method remains valid at nodes.
The root-isolation citation supports the application. The cited theorem gives deterministic polynomial bit complexity for square-free polynomials over a represented real algebraic extension. In the application here, the extension has degree one, the coefficients are integers, and the input polynomial is square-free. These satisfy the relevant hypotheses. See [Strzebonski–Tsigaridas, Theorem 10](https://arxiv.org/html/1101.4369v2).
Gap filtering and refinement by Sturm counts are compatible with the claimed complexity. The algorithm examines every possible location of the minimizer and rejects extraneous polynomial roots using the exact derivative test. Strict monotonicity guarantees a unique accepted value.
With fixed $b$, polynomial complexity in $N=b^r$ yields
$$
2^{O_p(r)}\operatorname{poly}(r,L).
$$
Multiplying by the polynomial number of coordinates establishes the stated society-level bound. The logarithmic-distinct-judgment consequence follows for every fixed constant in the logarithmic restriction.
The forward reduction uses the correct identity
$$
\left(\frac{u_i}{v_i}\right)^{h+1/2}
=
\frac{u_i^h}{v_i^{h+1}}\sqrt{u_iv_i}.
$$
Clearing denominators by a positive common denominator preserves the sign, including equality. Fixed $h$ ensures polynomial construction size.
The cited source uses the stated signed integer-coefficient formulation and describes its polynomial-time comparison question as open. See [Eisenbrand–Haeberle–Singer](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54).
In the reverse reduction, the judgments are dyadic and strictly inside $(-1,1)$, and the effective weights are positive integers. Substitution gives exactly
$$
G_p(0)=\frac{B}{M^{h+1/2}}E.
$$
The prefactor is positive, so the inclusive comparison is preserved.
The society realization is admissible. The displayed masses sum to one, including the separate single-term case, and their products with the influences equal the required weights. The product defining $B$ has polynomial bit length because $h$ is fixed. The other judgment coordinate introduces no coupling.
The branch with no remaining terms is directly decidable and does not obstruct the claimed polynomial-time equivalence of decision problems.
A polynomial-time exact consensus algorithm would return an encoding of polynomial length. The constructed performing coordinate has a unique minimizer.
Its sign can be determined from the encoded polynomial and isolating interval. If zero lies in the interval and is a polynomial root, isolation identifies it as the represented root. Otherwise, root counts determine the represented root’s side. This justifies the claimed implication from polynomial-time exact consensus to polynomial-time signed square-root-sum comparison.
The implication establishes neither NP-hardness nor a superpolynomial output-length obstruction. The prover correctly states both limitations.
Rational square-class membership is correctly tested by reducing the ratio and checking its numerator and denominator for being perfect squares. The resulting rational radical multipliers and within-class sums have polynomial bit length.
The linear-independence argument is valid. The field is a finite Galois splitting field. Distinct rational square classes give distinct sign characters, and character orthogonality isolates each coefficient. This also covers a rational-square class, whose character is trivial.
Consequently, the radical sum vanishes exactly when every grouped rational coefficient vanishes. The algorithm does not enumerate the Galois group or factor the radicands. The stated polynomial-time equality-recognition result follows.
Major issue: the requested classification remains incomplete. Section 6 explicitly leaves every unrestricted noninteger rational exponent unresolved. Neither the exponential algorithm nor the half-integer comparison reductions supply the polynomial-time algorithm or NP-hardness proof requested for those exponents.
No clarification alone can close this issue. The minimum additional substantive requirement is a complexity classification for unrestricted support at each remaining fixed exponent. Any polynomial-time claim must account for the required coefficient-list output; any NP-hardness claim needs an actual appropriate reduction. The existing partial claims need no mathematical repair.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.