Answer: polynomial-time solvable
Theorem 21 — class: other
Given \(M\), positive rational constituency shares \(\alpha_\lambda\) summing to \(1\), and symmetric finite-support rational bias distributions \(\mu\) and \(\rho^z\) satisfying the paper’s sufficient-randomness and non-tight-correlation assumptions, compute weights \(w\in\mathbb{R}^M\) minimizing \(\mathbb{E}[(R-\sum_\lambda w_\lambda\chi_\lambda)^2]\). For each issue, draw \(Z\sim\mu\) and then conditionally independent \(T_\lambda\sim\rho^Z\); set \(R=\sum_\lambda\alpha_\lambda T_\lambda\) and \(\chi_\lambda=\operatorname{sgn}(T_\lambda)\), using a fair sign when \(T_\lambda=0\).
A society is given by its support: the list of the \(\tau\) constituency types with positive binary rational masses \(\alpha_\lambda\), summing to \(1\). Here \(\tau=M\geq1\), and there are \(m=2\) voting alternatives.
The input also explicitly lists finite-support probability distributions \(\mu\) and \(\rho^z\), for every \(z\in\operatorname{supp}\mu\); all support points are rational numbers in \([-1,1]\), and all listed probabilities are positive binary rationals. Let \(K\) count all listed bias-support entries and \(L\) be the total input bit length.
Require \(\mu(A)=\mu(-A)\) and \(\rho^z(A)=\rho^{-z}(-A)\) for every Borel set \(A\). Require sufficient randomness, \(\mu\{z:\rho^z(\{-1\})=1\text{ or }\rho^z(\{1\})=1\}<1\), and nontriviality, \(\mu\{z:\rho^z(\{0\})=1\}<1\).
Define \(d(z)=\rho^z((0,1])-\rho^z([-1,0))\), and require non-tight correlation, \(\sum_z\mu(\{z\})d(z)^2<1\).
For an issue, draw \(Z\sim\mu\), then conditionally independent \(T_\lambda\sim\rho^Z\). Set \(R=\sum_\lambda\alpha_\lambda T_\lambda\) and \(\chi_\lambda=\operatorname{sgn}(T_\lambda)\); at zero use independent fair signs, independent of all bias draws. Minimize \(\mathbb E[(R-\sum_\lambda w_\lambda\chi_\lambda)^2]\) over unrestricted \(w\in\mathbb R^M\).
Is computing an exact rational minimizing weight vector polynomial-time solvable in \(m,\tau,M,K,L\), or is it NP-hard?
For finite electorates, optimal weights converge to unique limiting weights affine in constituency shares. The limiting objective is exactly the mass objective defined above, and its minimizer is already explicitly characterized in [Kirsch–Toth](https://arxiv.org/pdf/2102.12704); an open-target claim for this formulation is therefore unsupported.
Result. Computing the exact rational minimizing weight vector is polynomial-time solvable. The minimizer is unique and affine in the constituency shares. This agrees with the characterization in [Kirsch–Toth, Theorem 21](https://arxiv.org/pdf/2102.12704#page=13). We derive the formula directly for the stated objective and then prove its exact computational complexity.
1. Conditional moments. Write \(p_z=\mu(\{z\})\) and \(p_{z,t}=\rho^z(\{t\})\). Define
\(\displaystyle h_z=\sum_{t\in\operatorname{supp}\rho^z}p_{z,t}t,\qquad a_z=\sum_{t\in\operatorname{supp}\rho^z}p_{z,t}|t|,\qquad d_z=\sum_{t>0}p_{z,t}-\sum_{t<0}p_{z,t}.\)
The three scalar quantities needed for the optimization are
\(\displaystyle q=\sum_zp_zd_z^2,\qquad A=\sum_zp_za_z,\qquad B=\sum_zp_zd_zh_z.\)
They are rational finite sums. Since \(|d_z|\leq1\), the non-tight correlation hypothesis gives \(0\leq q<1\).
The fair sign at zero has conditional expectation zero. Consequently, for every constituency \(\lambda\),
\(\displaystyle \mathbb E[\chi_\lambda\mid Z=z]=d_z,\qquad \mathbb E[T_\lambda\mid Z=z]=h_z.\)
Moreover, \(T_\lambda\chi_\lambda=|T_\lambda|\), including when \(T_\lambda=0\). Thus
\(\displaystyle \mathbb E[T_\lambda\chi_\lambda\mid Z=z]=a_z.\)
For distinct constituencies \(\lambda,\nu\), conditional independence of the bias draws and independence of the fair signs imply
\(\displaystyle \mathbb E[\chi_\lambda\chi_\nu\mid Z=z]=d_z^2,\qquad \mathbb E[\chi_\lambda T_\nu\mid Z=z]=d_zh_z.\)
Averaging over \(Z\), and using \(\chi_\lambda^2=1\), yields
\(\displaystyle \mathbb E[\chi_\lambda\chi_\nu]= \begin{cases} 1,&\lambda=\nu,\\ q,&\lambda\ne\nu. \end{cases}\)
Also, since \(\sum_\nu\alpha_\nu=1\),
\(\displaystyle \beta_\lambda:=\mathbb E[R\chi_\lambda] =\alpha_\lambda A+\sum_{\nu\ne\lambda}\alpha_\nu B =(A-B)\alpha_\lambda+B.\)
2. Unique global minimizer. Let \(\mathbf1\in\mathbb R^M\) denote the vector whose entries are all one, and define the second-moment matrix
\(\displaystyle G=\mathbb E[\chi\chi^{\mathsf T}]=(1-q)I+q\mathbf1\mathbf1^{\mathsf T}.\)
Expanding the objective gives
\(\displaystyle F(w):=\mathbb E[(R-w^{\mathsf T}\chi)^2] =\mathbb E[R^2]-2\beta^{\mathsf T}w+w^{\mathsf T}Gw.\)
All expectations exist because the random variables are bounded. For every nonzero \(x\in\mathbb R^M\),
\(\displaystyle x^{\mathsf T}Gx =(1-q)\sum_{\lambda=1}^M x_\lambda^2 +q\left(\sum_{\lambda=1}^M x_\lambda\right)^2>0.\)
Here the first term is strictly positive because \(q<1\), and the second is nonnegative. Hence \(G\) is positive definite and invertible.
Let \(w^\star\) be the unique solution of \(Gw^\star=\beta\). Expanding around this solution gives
\(\displaystyle F(w)-F(w^\star) =(w-w^\star)^{\mathsf T}G(w-w^\star).\)
Positive definiteness proves that \(w^\star\) is the unique global minimizer.
To compute it explicitly, put \(S=\sum_\lambda w^\star_\lambda\). The normal equations are
\(\displaystyle (1-q)w^\star_\lambda+qS=(A-B)\alpha_\lambda+B.\)
Summing them gives
\(\displaystyle \bigl(1+(M-1)q\bigr)S=A+(M-1)B.\)
Both \(1-q\) and \(1+(M-1)q\) are positive. Substituting the resulting value of \(S\) into each normal equation yields
\(\displaystyle \boxed{ w^\star_\lambda =\frac{A-B}{1-q}\,\alpha_\lambda +\frac{B-qA}{(1-q)\bigl(1+(M-1)q\bigr)} \qquad(\lambda=1,\ldots,M). }\)
Indeed, the constant numerator simplifies using
\(\displaystyle B\bigl(1+(M-1)q\bigr)-q\bigl(A+(M-1)B\bigr)=B-qA.\)
This formula also covers \(M=1\): since \(\alpha_1=1\), it gives \(w^\star_1=A\).
3. Exact computation and bit complexity. The algorithm scans the listed distributions to compute \(d_z,h_z,a_z\), accumulates \(q,A,B\), and evaluates the boxed expression for each constituency. It uses \(O(K+M)\) rational arithmetic operations.
To establish polynomial time in the binary input model, we must also bound the sizes of the intermediate and output rationals.
Let \(Q\) be the product of the positive denominators of all input rationals. Every input denominator divides \(Q\), and the binary length of \(Q\) is \(O(L)\), because the sum of the lengths of its factors is bounded by the input length.
The reduced denominators of the conditional moments satisfy:
For example, each summand \(p_zd_zh_z\) has denominator dividing \(Q^4\), so its finite sum does too. The other assertions follow in the same way. These bounds also hold for partial sums during accumulation.
Furthermore, \(0\leq q<1\), \(0\leq A\leq1\), and \(|B|\leq1\). Thus their numerators, when expressed over the common denominator \(D=Q^4\), have binary length \(O(L)\). Write
\(\displaystyle q=\frac{u}{D},\qquad A=\frac{v}{D},\qquad B=\frac{s}{D}.\)
If \(\alpha_\lambda=a_\lambda/b_\lambda\), the minimizing weight can be represented explicitly as
\(\displaystyle w^\star_\lambda= \frac{ (v-s)a_\lambda\bigl(D+(M-1)u\bigr) +b_\lambda(sD-uv) }{ b_\lambda(D-u)\bigl(D+(M-1)u\bigr) }. \)
Every integer in this expression has binary length \(O(L+\log M)\). Its denominator is nonzero because \(q<1\). Reduction to lowest terms uses a greatest-common-divisor computation, also polynomial in these bit lengths.
Therefore every arithmetic operation takes polynomial time, and the complete output has polynomial length. The algorithm is polynomial-time in \(K,M,L\), hence in all the requested parameters, with \(m=2\) and \(\tau=M\).
The derivation applies to every promised input. Symmetry, sufficient randomness, and nontriviality require no additional computational step in the proof; positive definiteness follows directly from the stipulated non-tight correlation.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The output establishes a polynomial-time algorithm for the exact rational minimizer on every promised input. The minimizer formula, uniqueness argument, and bit-complexity analysis are correct. No major or minor mathematical issues were found.
The definitions of \(h_z,a_z,d_z\) correctly represent the conditional mean bias, conditional mean absolute bias, and conditional mean sign.
The stipulated fair signs at zero give \(\mathbb E[\chi_\lambda\mid Z=z]=d_z\). The identity \(T_\lambda\chi_\lambda=|T_\lambda|\) holds even at zero, so the diagonal mixed moment is correctly \(a_z\).
For distinct constituencies, conditional independence of the biases and independence of the zero-tie signs justify both factorizations:
\(\mathbb E[\chi_\lambda\chi_\nu\mid Z=z]=d_z^2\) and \(\mathbb E[\chi_\lambda T_\nu\mid Z=z]=d_zh_z\).
No unconditional independence is incorrectly assumed.
Since every sign takes values in \(\{-1,1\}\), the diagonal entries of \(G\) are exactly \(1\), including when a bias is zero. The off-diagonal entries are \(q\). Thus \(G=(1-q)I+q\mathbf1\mathbf1^{\mathsf T}\) is correct.
The calculation \(\beta_\lambda=(A-B)\alpha_\lambda+B\) correctly separates the diagonal contribution from the other constituencies and uses the normalization of the shares.
The quadratic expansion of the objective is valid. All relevant moments are finite.
The displayed quadratic form proves positive definiteness for every nonzero vector because \(0\leq q<1\). Consequently, the normal equations have exactly one solution.
The identity expressing \(F(w)-F(w^\star)\) as the positive-definite quadratic form in \(w-w^\star\) correctly proves unique global optimality over the full unrestricted domain \(\mathbb R^M\). No weight-sign restriction is introduced.
Summing the normal equations correctly gives
\(\bigl(1+(M-1)q\bigr)S=A+(M-1)B\).
Substitution and the displayed numerator simplification correctly yield the boxed formula. Both denominator factors are strictly positive on the promised domain.
The stated \(M=1\) simplification is correct: the formula gives \(w^\star_1=A\). The formulas also remain valid at \(q=0\). No division by \(A-B\), \(B\), or another potentially zero quantity occurs.
The moment computation requires a constant number of rational operations per listed support entry, followed by a constant number per constituency. The claimed \(O(K+M)\) arithmetic-operation count is justified.
The denominator argument is valid: the product \(Q\) has binary length \(O(L)\), and every input denominator divides it. The bounds \(Q,Q^2,Q^3,Q^4\) for the listed moments follow from their respective products and sums. They also control reduced denominators of partial sums.
The magnitude bounds on \(q,A,B\) correctly imply \(O(L)\)-bit numerators over \(D=Q^4\). Conditional moments and their partial sums are likewise bounded in magnitude by \(1\), so their numerator sizes introduce no omitted growth problem.
The explicit integer representation of each weight is algebraically correct. Its numerator and denominator have bit length \(O(L+\log M)\), and the denominator is nonzero. Standard exact rational arithmetic with reduction, including greatest-common-divisor computation, therefore has polynomial bit cost. The complete vector has polynomial output length.
Thus the output proves polynomial time in the binary input model, rather than merely counting arithmetic operations.
The direct proof uses conditional independence, the fair zero-tie convention, normalization, and \(q<1\). Its validity does not require using every additional promise. Omitting promise validation is appropriate because the task specifies promised inputs.
The citation is corroborative; the argument does not depend on an unstated external theorem. The affine coefficients agree with equations (25)–(26) of [Kirsch–Toth, Theorem 21](https://arxiv.org/pdf/2102.12704#page=13), with their correlation parameter corresponding to \(q\), their averaged absolute first moment to \(A\), and their averaged sign-times-first moment to \(B\).
Repair feedback: None required. The write-up resolves the assigned exact continuous optimization problem and its computational complexity.
⟨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.