Answer: Polynomial-time solvable.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any ϵ ∈(0, 1/2), n ∈N, and X ∈{0, 1}n, fdist(X) = argmin y∈{0,1} distϵ(y; X) = argmax y∈{0,1} sX(y), where fdist is the distortion-optimal rule. Further, this can be computed in linear time. Note that in case of both estimates having equal strength, the result also implies that their distortion will be equal. A notable property of fdist is that if more than n/3 most accurate judgments or more than 2n/3 least accurate judg- ments are identical, then that will be the output of fdist, re- gardless of the remaining judgments.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(q\) ordered accuracy cohorts and rational report masses \(\mu_{j,b}\ge 0\), with \(\sum_{j=1}^q\sum_{b\in\{0,1\}}\mu_{j,b}=1\), choose \(y\in\{0,1\}\) minimizing \(D^\epsilon_\mu(y)=\sup_{1-\epsilon\ge p_1\ge\cdots\ge p_q\ge 1/2}\exp\!\left(\sum_{j=1}^q(\mu_{j,1-y}-\mu_{j,y})\log\frac{p_j}{1-p_j}\right)\).
A society has \(m=2\) possible reports and \(q\ge 1\) nonempty accuracy cohorts, ordered from most to least accurate. A type is a pair \((j,b)\), where \(j\in\{1,\ldots,q\}\) and \(b\in\{0,1\}\). All mass in cohort \(j\) shares one unknown accuracy \(p_j\).
The society is given by its support: the list of the \(\tau\) types with positive mass, each mass encoded as a binary rational. Thus \(\tau\) is the support size, not the number of possible types. Missing types have mass zero, and \(\sum_{j=1}^q\sum_{b\in\{0,1\}}\mu_{j,b}=1\).
The input also includes a binary rational \(\epsilon\in(0,1/2)\). Feasible accuracies are real numbers satisfying \(1-\epsilon\ge p_1\ge\cdots\ge p_q\ge 1/2\); equality is allowed. Let \(L\) be the total input bit length.
Define \(D^\epsilon_\mu(y)=\sup_{1-\epsilon\ge p_1\ge\cdots\ge p_q\ge 1/2}\exp\!\left(\sum_{j=1}^q(\mu_{j,1-y}-\mu_{j,y})\log\frac{p_j}{1-p_j}\right)\). The computational problem is to return a minimizing \(y\in\{0,1\}\); either bit is permitted when both minimize. State running times in \(m,\tau,q,L\).
Is this exact minimizer-selection problem solvable in polynomial time in \(m,\tau,q,L\), or is it NP-hard?
For a finite ordered list of \(n\) binary judgments with independently varying ordered accuracies, distortion minimization is computable in \(O(n)\) time for every \(\epsilon\in(0,1/2)\). [Source](https://www.cs.toronto.edu/~nisarg/papers/ranked-binary-judgments.pdf)
No published result settling the exact rational-mass cohort problem above was identified in the literature searches.
The exact minimizer-selection problem is polynomial-time solvable. For \(m=2\), a deterministic algorithm uses \(O((\tau+q)L^2)\) bit operations, equivalently \(O(m(\tau+q)L^2)\). The minimizing reports are independent of \(\epsilon\).
Define the signed cohort masses and their prefix sums by
\(a_j=\mu_{j,1}-\mu_{j,0}\), \(S_0=0\), and
\(S_k=\sum_{j=1}^k a_j\) for \(1\le k\le q\).
Let
\(A=\max_{0\le k\le q}S_k\),
\(B=-\min_{0\le k\le q}S_k\), and
\(R=(1-\epsilon)/\epsilon>1\).
We will prove
\(D^\epsilon_\mu(0)=R^A\) and \(D^\epsilon_\mu(1)=R^B\).
First set \(H=\log R>0\) and introduce the log odds
\(x_j=\log(p_j/(1-p_j))\).
The function \(p\mapsto\log(p/(1-p))\) is continuous and strictly increasing on the permitted interval, with endpoint values \(0\) and \(H\). Thus this transformation is a bijection between the feasible accuracy vectors and
\(\{x\in\mathbb R^q:H\ge x_1\ge\cdots\ge x_q\ge0\}\).
We establish the following identity for arbitrary real coefficients \(c_1,\ldots,c_q\). With \(C_0=0\) and \(C_k=\sum_{j=1}^k c_j\),
\[
\max_{H\ge x_1\ge\cdots\ge x_q\ge0}\sum_{j=1}^q c_jx_j
=H\max_{0\le k\le q}C_k.
\]
Here and below, this displayed identity is understood as
\(\max_{H\ge x_1\ge\cdots\ge x_q\ge0}\sum_{j=1}^q c_jx_j=H\max_{0\le k\le q}C_k\).
To prove it, set \(x_{q+1}=0\) and \(d_k=x_k-x_{k+1}\). Then \(d_k\ge0\), \(\sum_{k=1}^q d_k=x_1\le H\), and \(x_j=\sum_{k=j}^q d_k\). Consequently,
\(\sum_{j=1}^q c_jx_j=\sum_{k=1}^q d_kC_k\).
Writing \(M=\max_{0\le k\le q}C_k\), we have \(M\ge0\) because \(C_0=0\). Hence
\(\sum_{k=1}^q d_kC_k\le M\sum_{k=1}^q d_k\le HM\).
This bound is attained. If \(M=0\), choose every \(x_j=0\). If \(M>0\), choose an index \(k\ge1\) with \(C_k=M\), and set \(x_j=H\) for \(j\le k\) and \(x_j=0\) for \(j>k\). This vector is feasible and its objective value is \(HC_k=HM\).
For report \(0\), the coefficients in the stated distortion objective are \(a_j\); for report \(1\), they are \(-a_j\). Applying the identity gives maximum exponents \(HA\) and \(HB\), respectively. Since the exponential is increasing, the distortion formulas follow. In particular, the supremum is attained by a feasible accuracy vector whose first \(k\) coordinates equal \(1-\epsilon\) and whose remaining coordinates equal \(1/2\).
Because \(R>1\), comparing the distortions is equivalent to comparing \(A\) and \(B\). Therefore return:
When \(A=B\), both reports minimize distortion, so this rule validly returns \(0\). No logarithm, exponential, or approximation needs to be computed.
The algorithm forms each cohort difference \(a_j\), scans its prefix sums, and maintains their minimum and maximum, including the initial value \(S_0=0\).
Write each supported mass as \(\mu_{j,b}=u_{j,b}/v_{j,b}\), with positive integers \(u_{j,b},v_{j,b}\). Let
\(Q=\prod_{(j,b)\text{ in the support}}v_{j,b}\).
The sum of the denominator encoding lengths is at most \(L\), so \(Q\) has \(O(L)\) bits. Convert every supported mass to the integer
\(W_{j,b}=u_{j,b}(Q/v_{j,b})=Q\mu_{j,b}\), assigning zero to missing types.
These integers are nonnegative and sum to \(Q\). Thus every integer prefix difference
\(T_k=\sum_{j=1}^k(W_{j,1}-W_{j,0})=QS_k\)
lies between \(-Q\) and \(Q\) and has \(O(L)\) bits. Comparing \(\max_k T_k\) and \(-\min_k T_k\) gives exactly the same answer as comparing \(A\) and \(B\), since \(Q>0\).
Using schoolbook integer arithmetic:
Therefore the total is \(O((\tau+q)L^2)=O(m(\tau+q)L^2)\) for \(m=2\). Since every cohort is nonempty, \(q\le\tau\le2q\), so \(O(\tau L^2)\) is also a valid bound.
This proof directly establishes the rational-mass cohort result. It is consistent with the prefix-strength characterization for finite ordered binary judgments in [Lemma 1 and Theorem 1 of the supplied paper](https://www.cs.toronto.edu/~nisarg/papers/ranked-binary-judgments.pdf).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem correctly. The exact minimizer-selection problem is polynomial-time solvable, with the claimed bound of \(O((\tau+q)L^2)\) bit operations for \(m=2\). No major or minor mathematical gaps were found.
The definitions \(a_j=\mu_{j,1}-\mu_{j,0}\) and \(S_k=\sum_{j=1}^k a_j\) correctly collect the coefficients for report \(0\). Report \(1\) has the opposite coefficients. Including \(S_0=0\) ensures that \(A\) and \(B\) are nonnegative and accounts for choosing every accuracy equal to \(1/2\).
Since \(\epsilon\in(0,1/2)\), the permitted accuracy interval lies inside \((0,1)\), and \(H=\log((1-\epsilon)/\epsilon)>0\) is finite. The log-odds function is continuous and strictly increasing, with the stated endpoint values. Consequently, its coordinatewise application is a bijection onto
\[
\{x\in\mathbb R^q:H\ge x_1\ge\cdots\ge x_q\ge0\}.
\]
Both ordering and equality are preserved. The shared accuracy within each cohort is respected because there is exactly one variable per cohort.
The substitution \(d_k=x_k-x_{k+1}\), with \(x_{q+1}=0\), gives nonnegative differences satisfying \(\sum_k d_k=x_1\le H\). The reconstruction \(x_j=\sum_{k=j}^q d_k\) and finite-sum rearrangement
\[
\sum_{j=1}^q c_jx_j=\sum_{k=1}^q d_kC_k
\]
are correct.
Since \(M=\max_{0\le k\le q}C_k\ge0\), both inequalities in
\[
\sum_{k=1}^q d_kC_k\le M\sum_{k=1}^q d_k\le HM
\]
hold, including when some prefix sums are negative.
The attainment argument covers all cases. When \(M=0\), the zero vector attains the bound. When \(M>0\), a maximizing index necessarily satisfies \(k\ge1\), and the stated step vector attains \(HM\). The identity therefore holds for arbitrary real coefficients, as claimed.
Applying the identity to \(a_j\) yields maximum exponent \(HA\). Applying it to \(-a_j\) yields maximum exponent \(HB\), because its prefix sums are \(-S_k\). The exponential is increasing, and these maxima are attained, so
\[
D^\epsilon_\mu(0)=R^A,\qquad D^\epsilon_\mu(1)=R^B
\]
follows exactly. The corresponding accuracy vectors use permitted endpoints; no limiting argument is necessary.
Because \(R>1\), comparing the distortions is exactly equivalent to comparing their exponents. Returning \(0\) when \(A\le B\) and \(1\) otherwise is correct. Equality gives two minimizers, so the chosen tie convention satisfies the task. The entire minimizing set is independent of \(\epsilon\), although the distortion values generally depend on it.
The common denominator \(Q\) is positive and has \(O(L)\) bits, since its logarithmic size is bounded by the combined denominator encoding lengths. Each division \(Q/v_{j,b}\) is exact.
The resulting integers \(W_{j,b}=Q\mu_{j,b}\) are nonnegative and sum to \(Q\). Thus \(W_{j,b}\le Q\), and every prefix difference lies in \([-Q,Q]\). All arithmetic quantities used in selection consequently have \(O(L)\) bits. Scaling by positive \(Q\) preserves the required comparison exactly.
Schoolbook multiplication, division, and conversion support the claimed \(O(\tau L^2)\) bound. Sorting requires \(O(\tau\log(\tau+1))\) comparisons, each costing at most \(O(L)\); the explicit support encoding implies \(\log(\tau+1)=O(L)\). Aggregation and scanning fit within \(O((\tau+q)L)\).
Therefore the total bound \(O((\tau+q)L^2)\) is valid. Nonempty cohorts imply \(q\le\tau\le2q\), so the simplified \(O(\tau L^2)\) bound also holds. The expression with an additional factor \(m\) is valid here because \(m=2\); it establishes no claim for variable \(m\).
The argument includes \(q=1\), missing report types, zero signed cohort masses, either endpoint accuracy, and exact ties. Neither tiny positive \(\epsilon\) nor \(\epsilon\) close to \(1/2\) creates numerical precision requirements, because selection uses only integers.
The cited paper’s Lemma 1 and Theorem 1 state the analogous distortion formula and prefix-strength selection rule for finite binary judgment lists. The prover’s consistency statement is accurate. Those results are not used to justify the rational-mass extension; the supplied argument establishes it independently. [Supplied paper](https://www.cs.toronto.edu/~nisarg/papers/ranked-binary-judgments.pdf)
No additional lemma, clarification, or correction is required to make the mathematical argument verifiable.
⟨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.