Answer: polynomial-time solvable
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe eigenvector e corresponding to the largest eigenvalue of the judgement matrix Z is a vector to be pro- jected onto such that the total squared distance E reaches the minimum value.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), a finite support \(T\) of complete score vectors \(x_t\in\mathbb{Q}_{\ge 0}^{C}\), and rational masses \(\mu_t>0\) summing to \(1\), find a direction \(e\in\mathbb{R}^{T}\) with \(\sum_{t\in T}\mu_t e_t^2=1\) minimizing \(\sum_{c\in C}\sum_{t\in T}\mu_t\bigl(x_{ct}-a_c(e)e_t\bigr)^2\), where \(a_c(e)=\sum_{t\in T}\mu_t x_{ct}e_t\); return a minimizing direction and its induced aggregate scores.
Let \(C\) be a nonempty candidate set with \(m=|C|\). A society is given by its support: a list \(T\) of \(\tau\) distinct complete score vectors \(x_t\in\mathbb{Q}_{\geq 0}^{C}\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total binary input length. Scores are already commensurable.
For \(e\in\mathbb{R}^{T}\) satisfying \(\sum_{t\in T}\mu_t e_t^2=1\), define aggregate scores \(a_c(e)=\sum_{t\in T}\mu_t x_{ct}e_t\) and loss \(E(e)=\sum_{c\in C}\sum_{t\in T}\mu_t(x_{ct}-a_c(e)e_t)^2\). Projections are onto a line through the origin. Return any minimizing direction and its aggregate scores, with real algebraic coordinates encoded by square-free integer polynomials and rational isolating intervals. Either sign and any minimizer in a tie are allowed; zero score vectors are allowed.
Is this exact optimization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite list of agents, a unit eigenvector for the largest eigenvalue of \(X^{\mathsf T}X\) minimizes the corresponding unweighted squared projection loss and induces aggregate scores \(Xe\). [Discrete optimality result](https://www.ijcai.org/proceedings/2017/0064.pdf)
No complexity result for this exact support-encoded formulation was located in the search.
1. Result and notation. The exact optimization problem is solvable in deterministic polynomial time in \(m,\tau,L\), including the required algebraic-coordinate output. The construction below handles repeated largest eigenvalues and zero scores.
Index the candidates and support types, and define
\(X=(x_{ct})\in\mathbb{Q}^{m\times\tau}\),
\(D=\operatorname{diag}(\mu_t)\), and
\(S=XDX^{\mathsf T}\in\mathbb{Q}^{m\times m}\).
The matrix \(S\) is symmetric and positive semidefinite: for every \(y\in\mathbb{R}^m\),
\(y^{\mathsf T}Sy=\sum_t\mu_t(x_t^{\mathsf T}y)^2\geq 0\).
Let \(\lambda\) denote its largest eigenvalue.
We first prove optimality, then construct a suitable eigenvector without assuming that \(\lambda\) is simple, and finally establish polynomial bit complexity for the requested encoding.
2. Reducing the loss to a rational spectral problem. For every feasible \(e\), its aggregate vector is \(a(e)=XDe\). Expanding the loss and using both \(a_c(e)=\sum_t\mu_tx_{ct}e_t\) and \(\sum_t\mu_te_t^2=1\) gives
\( E(e)=\sum_{c,t}\mu_tx_{ct}^2 -2\sum_c a_c(e)^2 +\sum_c a_c(e)^2 =\operatorname{tr}(S)-\|a(e)\|_2^2. \)
For any Euclidean unit vector \(y\), weighted Cauchy–Schwarz gives
\( |y^{\mathsf T}a(e)| =\left|\sum_t\mu_t(x_t^{\mathsf T}y)e_t\right| \leq \left(\sum_t\mu_t(x_t^{\mathsf T}y)^2\right)^{1/2} =(y^{\mathsf T}Sy)^{1/2} \leq\sqrt{\lambda}. \)
The final inequality follows from the spectral theorem for the real symmetric matrix \(S\). Taking the supremum over unit vectors \(y\) proves
\(\|a(e)\|_2^2\leq\lambda\).
Consequently every feasible direction satisfies
\(E(e)\geq\operatorname{tr}(S)-\lambda\).
Suppose now that \(\lambda>0\), and choose any nonzero \(v\in\mathbb{R}^m\) satisfying \(Sv=\lambda v\). Put
\(N=v^{\mathsf T}v>0\), and define
\( e=\frac{X^{\mathsf T}v}{\sqrt{\lambda N}}. \)
Its weighted squared norm is
\( e^{\mathsf T}De =\frac{v^{\mathsf T}XDX^{\mathsf T}v}{\lambda N} =\frac{v^{\mathsf T}Sv}{\lambda N} =1. \)
Moreover,
\( a(e)=XDe =\frac{Sv}{\sqrt{\lambda N}} =\frac{\lambda v}{\sqrt{\lambda N}}, \qquad \|a(e)\|_2^2=\lambda. \)
Thus this direction is minimizing, and the exact minimum is
\(E_{\min}=\operatorname{tr}(S)-\lambda\).
If \(\lambda=0\), positive semidefiniteness implies \(S=0\). Then
\(0=\operatorname{tr}(S)=\sum_{c,t}\mu_tx_{ct}^2\).
Because every mass is positive, every score is zero. Return \(e_t=1\) for all \(t\), which is feasible because \(\sum_t\mu_t=1\), and return \(a_c=0\) for all \(c\). These rational coordinates have immediate encodings using the polynomials \(Z-1\) and \(Z\).
It remains to implement the construction for \(\lambda>0\) with polynomially bounded exact output.
3. Constructing an eigenvector when eigenvalues may repeat. Let
\( \chi(z)=\det(zI_m-S), \qquad q(z)=\frac{\chi(z)}{\gcd(\chi,\chi')}, \)
where the gcd is monic. The polynomial \(q\in\mathbb{Q}[z]\) is monic and square-free. Its roots are exactly the distinct eigenvalues of \(S\). Write \(d=\deg q\leq m\).
Isolate the real roots of an integer multiple of \(q\), and select the largest root \(\lambda\).
Define the bivariate polynomial
\( F(z,y)=\frac{q(z)-q(y)}{z-y}\in\mathbb{Q}[z,y]. \)
This is a polynomial because its numerator vanishes when \(z=y\). Its degree in each variable is at most \(d-1\). Substitute \(S\) for \(z\), obtaining the matrix polynomial
\(M(y)=F(S,y)\).
Let \(P_\lambda\) be the orthogonal projector onto the \(\lambda\)-eigenspace. We claim
\( M(\lambda)=q'(\lambda)P_\lambda. \)
Indeed, on the eigenspace corresponding to an eigenvalue \(\beta\neq\lambda\), the matrix \(M(\lambda)\) acts by the scalar
\(F(\beta,\lambda)=0\), since \(q(\beta)=q(\lambda)=0\).
On the \(\lambda\)-eigenspace it acts by
\(F(\lambda,\lambda)=q'(\lambda)\).
The spectral theorem decomposes the entire space into these eigenspaces, proving the identity.
Because \(q\) is square-free, \(q'(\lambda)\neq 0\). Therefore \(M(\lambda)\neq 0\), regardless of the multiplicity of \(\lambda\) in \(\chi\).
For each standard basis vector \(b_j\), define
\( v^{(j)}(y)=M(y)b_j, \qquad N_j(y)=\sum_{c=1}^m v^{(j)}_c(y)^2. \)
At least one \(N_j(\lambda)\) is positive. Choose the first such index and write its column polynomial as \(v(y)\). Then
\(v=v(\lambda)\neq 0\) and \(Sv=\lambda v\).
This choice can be made exactly. For each \(j\), compute \(\gcd(q,N_j)\). Since its roots are a subset of the roots of \(q\), a root count in the isolating interval for \(\lambda\) determines whether \(N_j(\lambda)=0\). Nonzero values are positive because \(N_j(\lambda)\) is a sum of real squares.
Finally define rational polynomials
\( N(y)=\sum_c v_c(y)^2,\qquad h(y)=yN(y), \)
\( f_t(y)=\sum_c x_{ct}v_c(y), \qquad g_c(y)=yv_c(y). \)
The minimizing direction and its aggregate scores from Section 2 are exactly
\( e_t=\frac{f_t(\lambda)}{\sqrt{h(\lambda)}}, \qquad a_c=\frac{g_c(\lambda)}{\sqrt{h(\lambda)}}, \)
where the positive square root is used and
\(h(\lambda)=\lambda N(\lambda)>0\).
4. Producing square-free integer coordinate polynomials. We now give the required individual polynomial encodings.
First remove roots of \(q\) at which the normalization denominator vanishes:
\( q_0(y)=\frac{q(y)}{\gcd(q,h)}. \)
This polynomial is monic and square-free, satisfies \(q_0(\lambda)=0\), and is relatively prime to \(h\). In particular, \(h(\beta)\neq 0\) for every root \(\beta\) of \(q_0\).
Consider any output coordinate, written as
\(u=r(\lambda)/\sqrt{h(\lambda)}\),
where \(r\) is one of the polynomials \(f_t\) or \(g_c\). Form
\( R_r(Z)=\operatorname{Res}_y\bigl(q_0(y),h(y)Z^2-r(y)^2\bigr). \)
Because \(q_0\) is monic, the resultant has the product expression
\( R_r(Z)=\prod_{\beta:\,q_0(\beta)=0} \bigl(h(\beta)Z^2-r(\beta)^2\bigr). \)
Every factor has nonzero leading coefficient. Hence \(R_r\) is a nonzero rational polynomial of degree \(2\deg q_0\leq 2m\). The factor corresponding to \(\beta=\lambda\) shows that \(R_r(u)=0\).
Clear denominators and take the square-free part to obtain a square-free integer polynomial \(P_r(Z)\) satisfying \(P_r(u)=0\). This construction also covers zero coordinates.
A polynomial alone does not identify the intended sign or conjugate. We next show that a rational isolating interval selecting the coordinate given by the displayed formula can also be computed in polynomial time.
5. Bit complexity and isolating intervals. We use standard deterministic algorithms for univariate polynomial gcds, square-free parts, real-root isolation, and root counting. Their bit complexity is polynomial in polynomial degree and coefficient bit length. After isolation, refining a specified root to absolute error at most \(2^{-b}\) also takes polynomial time in these parameters and \(b\), using exact root counts and bisection. These facts are established, for example, in [Emiris, Mourrain, and Tsigaridas, *Real Algebraic Numbers: Complexity Analysis and Experimentation*](https://who.paris.inria.fr/Elias.Tsigaridas/files/emt-lncs-2006.pdf), particularly Sections 2, 5, and 6.
We verify that all inputs to these algorithms, and all precision requirements, are polynomially bounded.
*Coefficient sizes.* Each entry of \(S\) is a sum of \(\tau\) products of three input rationals, so its numerator and denominator have polynomial bit length. For instance, the product of all input denominators has bit length at most \(L\), and its cube supplies a common denominator for all these products.
Clearing a common denominator in \(S\), determinant bounds show that the coefficients of \(\chi\) have polynomial bit length in \(m,\tau,L\). Polynomial gcd and square-free-part algorithms produce \(q\) with polynomial coefficient bit length.
The entries of \(M(y)\) are linear combinations of
\(I_m,S,\ldots,S^{d-1}\), with coefficients obtained from \(q\). Matrix multiplication through these polynomially many powers gives polynomial coefficient bit lengths. Thus the same holds for \(v,N,h,f_t,g_c\), whose degrees are at most \(2m\).
The coordinate resultants can be computed by determinants of Sylvester matrices of order at most \(3m\), with entries of degree at most two in \(Z\). Determinant coefficient bounds give polynomial coefficient bit length. They can be computed in polynomial time, for example by evaluating at polynomially many integer values of \(Z\), computing exact determinants, and interpolating. Clearing denominators and taking square-free parts preserves polynomial bounds.
It follows that every \(P_r\) has degree at most \(2m\) and polynomial coefficient bit length.
*Separation of coordinate roots.* For completeness, a polynomial separation bound follows directly from the discriminant. Let a square-free integer polynomial \(P\) have degree \(n\geq 2\), coefficients of absolute value at most \(2^H\), and roots \(\alpha_1,\ldots,\alpha_n\). Cauchy’s bound gives
\(|\alpha_i|\leq 1+2^H\).
Its discriminant is a nonzero integer, so its absolute value is at least one. Writing it as
\( |\operatorname{disc}(P)| =|a_n|^{2n-2}\prod_{i<j}|\alpha_i-\alpha_j|^2 \)
and bounding every root difference except a smallest one by
\(2(1+2^H)\) yields the convenient lower bound
\( \min_{i\neq j}|\alpha_i-\alpha_j| \geq 2^{-n^2(H+2)}. \)
Thus distinct roots of each \(P_r\) are separated by an explicitly computable \(2^{-B}\), where \(B\) is polynomial in the input parameters. For degree one, no separation issue arises.
*The normalization denominator cannot require excessive precision.* Form
\( G(U)=\operatorname{Res}_y(q_0(y),U-h(y)), \)
and clear denominators. This is a nonzero integer polynomial of polynomial degree and coefficient bit length. Since \(\gcd(q_0,h)=1\), its constant coefficient is nonzero. Moreover, \(G(h(\lambda))=0\).
If its coefficients have absolute value at most \(2^{H_G}\), applying Cauchy’s bound to the reversed polynomial gives
\( h(\lambda)\geq (1+2^{H_G})^{-1}. \)
Thus \(h(\lambda)\) has a positive lower bound whose logarithm is polynomially bounded.
*Selecting the intended coordinate.* Cauchy’s bound also gives
\(|\lambda|\leq 2^{\operatorname{poly}(m,\tau,L)}\).
Using the already established degree and coefficient bounds, the absolute values of \(r,h,r',h'\) on a surrounding bounded interval are at most
\(2^{\operatorname{poly}(m,\tau,L)}\).
The positive lower bound for \(h(\lambda)\), together with the bound on \(h'\), therefore supplies a neighborhood of \(\lambda\) of radius
\(2^{-\operatorname{poly}(m,\tau,L)}\)
on which \(h\) remains positive and bounded below by half that lower bound. On this neighborhood,
\( \frac{d}{dy}\left(\frac{r(y)}{\sqrt{h(y)}}\right) =\frac{r'(y)}{\sqrt{h(y)}}- \frac{r(y)h'(y)}{2h(y)^{3/2}} \)
has absolute value at most
\(2^{\operatorname{poly}(m,\tau,L)}\).
These bounds are computable from the degrees and coefficient sizes.
Consequently, refining \(\lambda\) to polynomially many bits and approximating the positive square root by rational bisection produces a rational \(w\) satisfying
\(|w-u|<\varepsilon\),
where \(\varepsilon\) is any chosen inverse power of two with polynomial exponent.
Choose \(\varepsilon\) smaller than one eighth of the separation lower bound for \(P_r\). Then the rational interval
\( (w-2\varepsilon,\;w+2\varepsilon) \)
contains \(u\) strictly and contains no other root of \(P_r\), because its width is smaller than the root-separation bound. This is the required isolating interval. Evaluating the defining expression selects the intended coordinate consistently, including its sign and any zero value.
There are only \(\tau+m\) coordinates. Each polynomial and interval has polynomial encoding length and is computed in polynomial time.
6. Conclusion. The algorithm computes a minimizing direction and its aggregate scores exactly, with square-free integer coordinate polynomials and rational isolating intervals, in deterministic polynomial time in \(m,\tau,L\). Repeated top eigenvalues require no special assumption: the polynomial-projector construction selects a nonzero vector from the corresponding eigenspace.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed polynomial-time result. It addresses the exact support-encoded problem, including the required individual algebraic-coordinate encodings. I found no major or minor mathematical issues.
The argument establishes more than spectral optimality: it supplies a construction that handles repeated eigenvalues and bounds both the computation time and output length.
The matrices \(X\), \(D\), and \(S=XDX^{\mathsf T}\) have the stated dimensions and rational entries. The displayed quadratic-form identity correctly proves that \(S\) is symmetric positive semidefinite.
The input conditions imply \(\tau\geq 1\): positive masses cannot sum to one over an empty support. Thus the feasible direction used in the zero-score case is defined.
The construction uses the listed support directly. It does not expand rational masses into a potentially exponential population of agents.
The loss expansion is correct. For each candidate, the cross term equals \(-2a_c(e)^2\), and the final term equals \(a_c(e)^2\) by weighted normalization. Consequently,
\[
E(e)=\operatorname{tr}(S)-\|a(e)\|_2^2.
\]
The weighted Cauchy–Schwarz application has the required hypotheses: the masses are positive and the weighted squared norm of \(e\) is one.
The spectral bound applies because \(S\) is real symmetric and \(\lambda\) is its largest eigenvalue. Taking the supremum over Euclidean unit vectors correctly gives \(\|a(e)\|_2^2\leq\lambda\).
For \(\lambda>0\), the normalization denominator \(\sqrt{\lambda N}\) is strictly positive. Both subsequent computations are correct:
Therefore the lower bound on the loss is attained. No simplicity assumption on the eigenvalue is used.
If \(\lambda=0\), positive semidefiniteness forces every eigenvalue of \(S\) to vanish, hence \(S=0\).
The trace identity then forces every score to vanish because every summand is nonnegative and every mass is strictly positive.
Returning \(e_t=1\) is feasible, and all aggregate scores are zero. The proposed linear integer polynomials are square-free and encode these rational values. Supplying rational isolating intervals for these linear polynomials is immediate.
The square-free part \(q\) has exactly the distinct eigenvalues of \(S\) as roots. Since \(S\) is symmetric, all these roots are real, so selecting its largest isolated root correctly selects \(\lambda\).
The divided difference \(F(z,y)\) is a polynomial with the stated degree bounds. Its evaluation on each eigenspace establishes
\[
M(\lambda)=q'(\lambda)P_\lambda.
\]
Square-freeness gives \(q'(\lambda)\neq 0\), and the \(\lambda\)-eigenspace is nonempty. Thus \(M(\lambda)\) has a nonzero column.
The column-selection test is valid. A root of \(q\) is a root of \(N_j\) exactly when it is a root of \(\gcd(q,N_j)\). Root counting in the isolating interval for \(\lambda\) therefore determines whether that column vanishes. Since \(N_j(\lambda)\) is a sum of real squares, a nonzero value is positive.
The definitions of \(f_t\), \(g_c\), and \(h\) correctly reproduce the minimizing direction and its aggregate scores. In particular, \(h(\lambda)>0\).
Removing \(\gcd(q,h)\) preserves the root \(\lambda\), since \(h(\lambda)>0\). It also ensures that \(h\) is nonzero at every root retained in \(q_0\).
The resultant product formula is correct because \(q_0\) is monic. Every factor has a nonzero quadratic coefficient, so the resultant is nonzero and has degree exactly \(2\deg q_0\).
The factor associated with \(\lambda\) vanishes at the intended coordinate. Clearing denominators and taking the square-free part preserve this root.
This also handles a zero coordinate: repeated factors at zero may disappear during square-free reduction, but zero remains a root. No irreducibility or minimal-polynomial computation is required by the requested encoding.
The cited source supports the required polynomial-time operations. Its Theorems 2.2 and 2.4 address polynomial gcds and square-free parts, Corollary 2.1 supplies exact root counting, and Theorem 5.1 supplies real-root isolation. The source also gives a polynomial bound when its simplifying degree-versus-coefficient-size assumption is dropped. Thus that assumption does not invalidate the prover’s polynomial-time claim. [Emiris, Mourrain, and Tsigaridas](https://who.paris.inria.fr/Elias.Tsigaridas/files/emt-lncs-2006.pdf)
The applications satisfy the relevant hypotheses after denominators are cleared. Refinement by exact root counting and bisection retains polynomial bit complexity in the requested precision.
The coefficient-size arguments are valid:
No exponential-size symbolic representation is hidden in these steps.
The discriminant argument is valid for a square-free integer polynomial. Its discriminant is a nonzero integer, and the leading coefficient and all remaining root differences have the stated upper bounds. The resulting separation estimate \(2^{-n^2(H+2)}\) is conservative but valid.
For the normalization resultant \(G\), relative primality ensures a nonzero constant coefficient. Therefore applying Cauchy’s bound to the reversed polynomial is legitimate. Since \(h(\lambda)>0\), this produces the claimed positive lower bound.
The polynomial coefficient and degree bounds also control \(r,h,r',h'\) on a bounded neighborhood. The derivative displayed for \(r/\sqrt h\) is correct. Together with the lower bound on \(h\), it justifies the polynomial precision requirement.
The approximation step identifies the intended coordinate, including its sign, because it evaluates the defining expression using the positive square root.
If \(|w-u|<\varepsilon\), then \(u\) lies strictly inside the proposed interval. Choosing \(\varepsilon\) below one eighth of the separation bound makes the interval too narrow to contain another root. For degree-one coordinate polynomials, uniqueness is automatic.
There are only \(\tau+m\) coordinates, each with polynomial degree, coefficient bit length, and interval-endpoint bit length. Thus the complete requested output has polynomial length and is computable in deterministic polynomial time.
No corrections or additional lemmas are required. The output resolves the assigned optimization and encoding problem.
⟨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.