Answer: \(\text{polynomial-time solvable}\)
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet λ ≥0, and D = (dii′)i,i′∈N be an arbi- trary symmetric nonnegative matrix. Then argmin ¨ f X i,i′∈N:i̸=i′ ( ˆfi+ ˆfi′−dii′)2+λ∥¨f∥2 2 = 2(n −1)⃗π−8n(n−1) 4n+λ−4 ¯µ 2n + λ −4 . 2In the AWG model the equal-difficulty assumption is a nor- mative decision, since we can always scale the data. Essentially, it means that we measure errors in standard deviations, giving the same importance to all questions. 3We use ¨f instead of hat+arrow accent.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete worker-noise types \(\Theta\), positive rational masses \(\mu_t\) summing to one, and a symmetric rational matrix \(D\) of mean report distances between distinct agents of each type pair, compute a minimizer \(\hat f\) of \(\sum_{t,u\in\Theta}\mu_t\mu_u(\hat f_t+\hat f_u-D_{tu})^2\). For \(t=u\), \(D_{tt}\) is the mean distance between distinct agents of that type.
A society is given by its support: a nonempty list \(\Theta\) of \(\tau\) worker-noise types with positive masses \(\mu_t\in\mathbb{Q}_{>0}\), encoded in binary, satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Types identify complete report distributions; their relevant numerical information is supplied directly as an arbitrary symmetric matrix \(D\in\mathbb{Q}_{\geq0}^{\tau\times\tau}\). No report distributions need to be reconstructed.
\(D_{tu}\) represents the mean report distance between distinct agents of types \(t,u\); in particular, \(D_{tt}\) concerns two distinct agents of the same type and need not vanish.
Compute an exact minimizer over \(\hat f\in\mathbb{R}^{\Theta}\) of \(\sum_{t,u\in\Theta}\mu_t\mu_u(\hat f_t+\hat f_u-D_{tu})^2\), including all ordered type pairs. Estimates may be negative; there is no regularization.
Let \(L\) be the total binary input length and \(m\) the underlying number of report coordinates, if specified. State running times in \(m,\tau,L\); reports themselves are not input.
Is computing an exact minimizer of this mass-weighted fault-estimation problem solvable in polynomial time, or is it NP-hard?
For a finite population of at least three workers, the unweighted off-diagonal objective over unrestricted real estimates, also allowing nonnegative quadratic regularization, has a closed-form polynomial-time solution. [Meir et al.](https://ojs.aaai.org/index.php/AAAI/article/download/25750/25522)
No result for exactly the mass-weighted problem above was identified in the search.
The problem is polynomial-time solvable. Its unique exact minimizer is
\[ \boxed{\hat f_t^* =\sum_{u\in\Theta}\mu_uD_{tu} -\frac12\sum_{v,u\in\Theta}\mu_v\mu_uD_{vu}.} \]
This formula applies to every nonempty support, including \(\tau=1\), and retains all diagonal entries \(D_{tt}\).
Write \(f\) for the vector of estimates, and define
\[ r_t=\sum_{u\in\Theta}\mu_uD_{tu}, \qquad A=\sum_{t\in\Theta}\mu_tr_t, \qquad s(f)=\sum_{t\in\Theta}\mu_tf_t. \]
The given objective is
\[ F(f)=\sum_{t,u\in\Theta}\mu_t\mu_u(f_t+f_u-D_{tu})^2. \]
Using symmetry of \(D\) and \(\sum_t\mu_t=1\), expansion gives
\[ F(f) =2\sum_t\mu_tf_t^2 +2s(f)^2 -4\sum_t\mu_tr_tf_t +C, \qquad C=\sum_{t,u}\mu_t\mu_uD_{tu}^2. \]
Indeed, the two squared-estimate terms each contribute \(\sum_t\mu_tf_t^2\); the cross term contributes \(2s(f)^2\); and symmetry makes the two terms linear in the estimates equal.
Consequently, for every \(t\),
\[ \frac{\partial F}{\partial f_t} =4\mu_t\bigl(f_t+s(f)-r_t\bigr). \]
Since every mass is positive, stationarity is equivalent to
\[ f_t+s(f)=r_t \quad\text{for every }t. \]
Multiplying these equations by \(\mu_t\) and summing yields \(2s(f)=A\). Thus the only stationary candidate is \(f_t^*=r_t-A/2\). Its weighted mean is \(s(f^*)=A/2\), so it satisfies every stationarity equation.
To prove global optimality and uniqueness directly, let \(h\in\mathbb R^\Theta\). Substituting \(f^*+h\) into the expanded objective gives
\[ F(f^*+h)-F(f^*) = 2\sum_t\mu_th_t^2 +2\left(\sum_t\mu_th_t\right)^2. \]
The linear terms vanish because \(f_t^*+s(f^*)-r_t=0\) for every \(t\). Both displayed terms are nonnegative. If \(h\ne0\), the first is strictly positive because every \(\mu_t>0\). Therefore \(f^*\) is the unique global minimizer.
All sums here include diagonal type pairs. In particular, for \(\tau=1\), the formula gives \(f_1^*=D_{11}/2\).
Computing the weighted row means \(r_t\), then \(A\), then the output vector requires \(O(\tau^2)\) rational arithmetic operations. We must also bound their bit complexity.
Write the input rationals as \(\mu_t=p_t/q_t\) and \(D_{tu}=c_{tu}/d_{tu}\), with positive denominators. Let \(P\) be the product of the mass denominators and \(Q\) the product of the supplied matrix-entry denominators. Define integers
\[ a_t=p_t(P/q_t), \qquad b_{tu}=c_{tu}(Q/d_{tu}). \]
Then \(\mu_t=a_t/P\) and \(D_{tu}=b_{tu}/Q\). Set
\[ R_t=\sum_u a_ub_{tu}, \qquad B=\sum_t a_tR_t. \]
The exact output can be represented as
\[ f_t^*=\frac{2PR_t-B}{2P^2Q}. \]
The products \(P,Q\) have \(O(L)\) bits because the total lengths of their input denominators are bounded by \(L\). The integers \(a_t,b_{tu},R_t,B\), and the output numerators and denominator also have \(O(L)\) bits: multiplication adds bit lengths, and the sums add at most \(O(\log\tau)\) bits.
There are \(O(\tau^2)\) integer operations. Using elementary multiplication and long division therefore gives the conservative bound \(O(\tau^2L^2)\) bit operations. Since the explicitly supplied matrix implies \(\tau^2=O(L)\), this is also \(O(L^3)\). Unreduced fractions already provide an exact output.
There is no computational dependence on the value of \(m\): report coordinates and report distributions are not processed. If \(m\) is supplied as metadata, its encoding contributes only to \(L\).
⟨structured verdict parsed — rendered above⟩
The prover’s output fully resolves the assigned problem. The minimizer, uniqueness argument, and polynomial bit-complexity bound are correct. No mathematical gaps were found.
The proof uses exactly the stated objective: all ordered type pairs, including diagonal pairs, weighted by \(\mu_t\mu_u\). It assumes symmetry of \(D\), strictly positive masses, and total mass one, all supplied by the task.
The estimates remain unrestricted real numbers. No assumption that \(D_{tt}=0\), reconstruction of report distributions, or regularization is introduced.
The expansion
\[
F(f)=2\sum_t\mu_tf_t^2+2s(f)^2-4\sum_t\mu_tr_tf_t+C
\]
is correct.
Normalization of the masses gives each squared-estimate contribution \(\sum_t\mu_tf_t^2\). The estimate cross term is \(2s(f)^2\). Symmetry of \(D\) makes each of the two distance-linear contributions equal to \(-2\sum_t\mu_tr_tf_t\).
Differentiating therefore gives
\[
\frac{\partial F}{\partial f_t}
=4\mu_t(f_t+s(f)-r_t).
\]
This calculation includes diagonal pairs correctly. Positivity of every mass justifies the equivalence between stationarity and the displayed equations.
Multiplying \(f_t+s(f)=r_t\) by \(\mu_t\) and summing gives \(2s(f)=A\), using \(\sum_t\mu_t=1\). Consequently, every stationary point must satisfy \(f_t=r_t-A/2\).
The stated candidate has weighted mean \(A/2\), so it satisfies all stationarity equations. Both necessity and sufficiency are established.
The asserted difference identity
\[
F(f^*+h)-F(f^*)
=2\sum_t\mu_th_t^2
+2\left(\sum_t\mu_th_t\right)^2
\]
follows from the expanded objective: the linear contribution vanishes by stationarity.
Both remaining terms are nonnegative. For every nonzero \(h\), strict positivity of the masses makes the first term strictly positive. This proves existence, global optimality, and uniqueness without an additional convexity theorem.
The single-type case is correctly covered: normalization forces \(\mu_1=1\), and the formula gives \(f_1^*=D_{11}/2\).
The common-denominator construction is valid. Its definitions give
\[
r_t=\frac{R_t}{PQ},
\qquad
A=\frac{B}{P^2Q},
\]
so the reported output fraction is correct.
The products of input denominators have \(O(L)\) bits. Each subsequently constructed integer also has \(O(L)\) bits: only a constant number of such factors are multiplied in any term, and summation contributes at most \(O(\log\tau)\) additional bits.
Constructing the denominators, scaled entries, sums, and output requires \(O(\tau^2)\) integer operations. Elementary multiplication and division on these integers justify the stated \(O(\tau^2L^2)\) bit-operation bound. Explicit matrix encoding implies \(\tau^2=O(L)\), yielding \(O(L^3)\).
Unreduced rational fractions are valid exact outputs. The absence of computational dependence on the value of \(m\) matches the task because reports are not input.
⟨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.