Answer: —
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 2 outputs an element of arg maxD∈D 𝑞D.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu\) with \(λ\mu_t∈ℤ\), accuracies \(q_t∈(1/2,1)\), and a connected type graph \(H\), form the cohort blow-up with \(λ\mu_t\) agents of type \(t\), identical accuracy, and uniform delegation access to adjacent cohorts. Each type chooses a feasible stochastic delegation kernel \(D\), inducing expected per-agent weights \(r_D(t)\). Find \(D\) maximizing \(Q_{λ,μ}(D)=\Pr[Σ_t r_D(t)(2X_t−λ\mu_t)>0]+\frac12\Pr[Σ_t r_D(t)(2X_t−λ\mu_t)=0]\), where \(X_t\sim\operatorname{Binomial}(λ\mu_t,q_t)\) independently.
A society is given by its support: the list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types. There are \(m=2\) alternatives.
Input also includes binary-rational accuracies \(q_t\in(1/2,1)\), a binary-encoded positive integer \(\lambda\) with \(n_t=\lambda\mu_t\in\mathbb Z_{>0}\), and a connected undirected simple graph \(H\) on \(T\). Require \(\tau\ge2\) or \(\lambda=1\), so the agent graph below is connected. Let \(L\) be the total input bit length.
Cohort \(t\) contains \(n_t\) agents, each initially carrying unit weight. Agents can delegate to themselves or to any agent in an adjacent cohort; delegation to another agent in their own cohort is unavailable.
A feasible kernel \(D\in\mathbb R_{\ge0}^{T\times T}\) has row sums one and \(D_{ts}=0\) unless \(s=t\) or \(\{t,s\}\in E(H)\). Each agent of type \(t\) chooses itself with probability \(D_{tt}\), and each particular agent in adjacent cohort \(s\) with probability \(D_{ts}/n_s\).
All agents independently sample one proxy, fixed throughout the resulting delegation chains. A self-delegating agent is a guru; weight follows the chain to its guru, while chains entering a cycle of length greater than one lose their weight.
For any agent \(i\) of type \(t\), define \(r_D(t)=\mathbb E[|\{j:\text{the chain from }j\text{ ends at guru }i\}|]\), counting zero when \(i\) is not a guru. Symmetry makes this independent of the chosen agent \(i\).
The two truth states have equal prior probability; conditional on either state, agents vote independently and each type-\(t\) agent is correct with probability \(q_t\). Weighted majority uses the deterministic expected weights \(r_D(t)\), with a fair coin resolving ties.
For independent \(X_t\sim\operatorname{Binomial}(n_t,q_t)\), maximize \(Q_{\lambda,\mu}(D)=\Pr[\sum_t r_D(t)(2X_t-n_t)>0]+\tfrac12\Pr[\sum_t r_D(t)(2X_t-n_t)=0]\). Exact output kernel entries are represented as real algebraic numbers by integer polynomials and rational isolating intervals.
Is finding a feasible kernel maximizing \(Q_{\lambda,\mu}\) solvable in time polynomial in \(m,\tau,L\), or is it NP-hard? State running times in these quantities and any additional dependence on \(\lambda\).
For individually specified agents on connected undirected networks, an optimal expected-weight delegation construction is known, with claimed running time polynomial in the number of agents ([Zhang–Grossi, 2022](https://pure.uva.nl/ws/files/169357679/p1482.pdf)).
No complexity result for this exact succinct, type-symmetric cohort problem was located.
I do not resolve the general exact complexity classification. In particular, I prove neither a uniform polynomial-time exact algorithm nor $\mathrm{NP}$-hardness for the output model in the question.
The following results are proved below:
NOTES.I also prove a comparison reduction for the restricted problem of constructing a rational optimal kernel with acyclic nonself support. The restrictions matter: this reduction does not establish hardness for the unrestricted algebraic-output problem.
Throughout, $m=2$, and running times refer to bit complexity. Thus the displayed bounds have no additional variable dependence on $m$.
Write
$$
\mathcal K=\prod_{t\in T}\{0,\ldots,n_t\},
\qquad
\bar k_t=n_t-k_t,
\qquad
z_t(k)=2k_t-n_t.
$$
Since $\sum_t n_t=\lambda$, every $k\in\mathcal K$ satisfies
$$
\sum_t|z_t(k)|\le\lambda.
$$
Conditional on truth state one, the count vector $k$ has probability
$$
p_k=\prod_{t\in T}\binom{n_t}{k_t}
q_t^{k_t}(1-q_t)^{n_t-k_t}.
$$
Conditional on truth state two, it has probability $p_{\bar k}$. Both probabilities are positive.
For a rule selecting alternative one with probability $a(k)$ after observing $k$, equal-prior accuracy is
$$
\frac12\sum_{k\in\mathcal K}
\bigl[p_k a(k)+p_{\bar k}(1-a(k))\bigr].
$$
Each summand is maximized by choosing alternative one when $p_k>p_{\bar k}$ and alternative two when $p_k<p_{\bar k}$. Consequently, every rule satisfies
$$
Q\le Q^*:=\frac12\sum_{k\in\mathcal K}\max\{p_k,p_{\bar k}\}.
$$
Define the positive log-odds weights
$$
\ell_t=\log\frac{q_t}{1-q_t}>0.
$$
Cancellation of the binomial coefficients gives
$$
\log\frac{p_k}{p_{\bar k}}=z(k)\cdot\ell.
$$
For any nonnegative voting weights $r$, weighted majority with fair tie-breaking selects alternative one with probability $1$, $0$, or $1/2$ according to the sign of $z(k)\cdot r$. Complementing $k$ complements this selection probability. Its equal-prior accuracy therefore equals the objective in the question.
It follows that these weights attain $Q^*$ exactly when
$$
\operatorname{sign}(z(k)\cdot r)
=
\operatorname{sign}(z(k)\cdot\ell)
\quad\text{for every }k\text{ with }z(k)\cdot\ell\ne0.
$$
Indeed, an incorrect decision or a fair tie at any strict likelihood comparison incurs a positive loss, because that count vector has positive probability. Conversely, preserving every strict comparison attains every pointwise maximum.
Bayes ties impose no constraint on the voting weights. If $z(k)\cdot\ell=0$, either decision and a fair tie have the same accuracy.
Suppose $w_t>0$ and
$$
\sum_t n_t w_t=\lambda.
$$
There is a feasible kernel $D$ with acyclic nonself support such that
$$
r_D(t)=w_t
\quad\text{for all }t.
$$
For rational $w$, the construction uses polynomial time in the input length and the encoding length of $w$.
Root a spanning tree of $H$. Set
$$
b_t=n_t-n_t w_t,
\qquad
\sum_t b_t=0.
$$
For each nonroot vertex $u$, let $S_u$ be its rooted subtree and define
$$
B_u=\sum_{t\in S_u}b_t.
$$
Send $B_u$ from $u$ to its parent if $B_u>0$, and send $-B_u$ in the reverse direction if $B_u<0$. Let $F_{ts}$ denote these nonnegative directed flows.
Each tree edge carries flow in at most one direction, so the positive-flow graph is acyclic. The subtree identities imply
$$
\sum_s F_{ts}-\sum_s F_{st}=b_t.
$$
For a nonroot vertex, the signed sum is $B_t-\sum_{u\text{ child of }t}B_u=b_t$. At the root, the same identity follows from $\sum_t b_t=0$.
Define
$$
G_t=n_t+\sum_sF_{st}
=n_t w_t+\sum_sF_{ts},
$$
and set
$$
D_{tt}=\frac{n_t w_t}{G_t},
\qquad
D_{ts}=\frac{F_{ts}}{G_t}\quad(s\ne t).
$$
All denominators are positive. The displayed identity for $G_t$ proves that each row sums to one. The support uses only self-delegation and edges of $H$.
For an agent $i$, let $W_i$ be the number of initial units whose chains reach $i$, including its own unit, before following its proxy.
Under this construction, nonself delegation advances along an acyclic graph of types. Thus a chain reaching $i$ has not previously visited $i$’s type. Whether an initial unit reaches $i$ consequently depends only on other agents’ proxy choices. Hence $W_i$ is independent of $i$’s own proxy choice.
Let
$$
U_t=\sum_{i\text{ of type }t}\mathbb E[W_i].
$$
The independence just established and linearity of expectation give, in topological order,
$$
U_t=n_t+\sum_sU_sD_{st}.
$$
Induction yields $U_t=G_t$: for a source, both equal $n_t$; otherwise,
$$
U_t=n_t+\sum_sG_s\frac{F_{st}}{G_s}
=n_t+\sum_sF_{st}=G_t.
$$
Cohort symmetry gives $\mathbb E[W_i]=G_t/n_t$. The final weight of guru $i$ is $W_i$ if it self-delegates, and zero otherwise. Therefore
$$
r_D(t)=D_{tt}\frac{G_t}{n_t}=w_t.
$$
Every chain eventually self-delegates, since its nonself steps follow a finite acyclic graph. Thus no weight is lost.
The construction requires only a spanning tree, subtree sums, and rational arithmetic; it does not expand the cohorts.
Choose
$$
w_t=\frac{\lambda\ell_t}{\sum_s n_s\ell_s}.
$$
These positive weights meet the normalization and preserve all Bayes comparisons. Therefore
$$
\max_D Q_{\lambda,\mu}(D)=Q^*.
$$
The logarithms used here need not be algebraic. This establishes attainment over real kernels; the rational constructions below establish attainment within the required output representation.
If $\tau=1$, the hypotheses require $\lambda=1$. The unique feasible kernel is $D_{11}=1$, which is optimal. Henceforth assume $\tau\ge2$.
Write
$$
q_t=\frac{a_t}{b_t},
\qquad
c_t=b_t-a_t,
\qquad
\ell_t=\log\frac{a_t}{c_t},
$$
where $a_t,c_t$ are positive integers at most $2^L$ and $a_t>c_t$.
For any count vector, moving negative exponents between numerator and denominator expresses
$$
\prod_t\left(\frac{a_t}{c_t}\right)^{z_t(k)}
=\frac AB
$$
with positive integers $A,B\le2^{\lambda L}$. If the corresponding logarithmic form is nonzero, then $A\ne B$, and
$$
\left|\log\frac AB\right|
\ge\frac{|A-B|}{\max\{A,B\}}
\ge2^{-\lambda L}.
$$
The first inequality follows by integrating $1/x$ between the smaller and larger integer.
Choose
$$
p=\lambda L+\lceil\log_2\lambda\rceil+3
$$
and rational approximations satisfying
$$
|v_t-\ell_t|\le2^{-p}.
$$
For every count vector,
$$
|z(k)\cdot(v-\ell)|
\le\lambda2^{-p}
\le\frac18\,2^{-\lambda L}.
$$
Thus every strict Bayes comparison is preserved.
These approximations are positive. Indeed,
$$
\ell_t
=\int_{c_t}^{a_t}\frac{dx}{x}
\ge\frac{a_t-c_t}{a_t}
\ge2^{-L},
$$
whereas $2^{-p}<2^{-L}/2$.
Normalize $v$ by
$$
w_t=\frac{\lambda v_t}{\sum_s n_s v_s}
$$
and apply Section 2. Normalization multiplies the weights by a common positive factor, so the resulting rational kernel is exactly optimal.
For completeness, the logarithms can be computed with polynomial bit complexity. Write an integer $a$ as $a=2^j y$ with $1\le y<2$, and use
$$
\log a=j\log2+
2\sum_{h=0}^{\infty}\frac{u^{2h+1}}{2h+1},
\qquad
u=\frac{y-1}{y+1}\in[0,1/3).
$$
The same series computes $\log2$ using $u=1/3$. The tail after $N$ terms is at most
$$
\frac{2(1/3)^{2N+1}}{1-1/9}<3^{-2N}.
$$
Taking $N=O(p+\log(L+1))$ accounts for range reduction, subtraction, and dyadic rounding. Exact rational powers and sums have encoding length polynomial in $N,L$.
This proves the unconditional exact running-time bound
$$
\operatorname{poly}(\tau,L,\lambda).
$$
Because $\lambda$ is binary encoded, this does not establish polynomial time in the succinct input length.
Every output fraction $A/B$ meets the required algebraic representation: use the integer polynomial $Bx-A$ and the rational isolating interval $(-1,2)$.
For every integer $b\ge1$, one can construct a rational feasible kernel $D$ satisfying
$$
Q_{\lambda,\mu}(D)\ge Q^*-2^{-b}
$$
in time
$$
\operatorname{poly}(\tau,L,b).
$$
The dependence on population size is through $\log\lambda$, already included in $L$.
First suppose positive weights $v$ satisfy
$$
\max_t|v_t-\ell_t|\le\delta.
$$
If weighted majority using $v$ makes an incorrect decision or a fair tie at a strict Bayes comparison, then
$$
|z(k)\cdot\ell|
\le |z(k)\cdot(\ell-v)|
\le\lambda\delta.
$$
Let
$$
M_k=\frac{p_k+p_{\bar k}}2.
$$
These numbers sum to one. At a strict comparison, let $\rho_k$ be the probability that the weighted rule chooses the alternative opposite to the Bayes choice. Thus $\rho_k$ is $0$, $1/2$, or $1$. Subtracting the rule’s accuracy from Bayes accuracy gives
$$
Q^*-Q(v)
=
\sum_{k:\,p_k\ne p_{\bar k}}
M_k
\frac{|p_k-p_{\bar k}|}{p_k+p_{\bar k}}
\rho_k.
$$
Since $p_k/p_{\bar k}=\exp(z(k)\cdot\ell)$,
$$
\frac{|p_k-p_{\bar k}|}{p_k+p_{\bar k}}
=
\tanh\left(\frac{|z(k)\cdot\ell|}{2}\right).
$$
Whenever $\rho_k>0$, the preceding margin bound and $\tanh x\le x$ for $x\ge0$ imply
$$
\frac{|p_k-p_{\bar k}|}{p_k+p_{\bar k}}
\le\frac{\lambda\delta}{2}.
$$
Therefore
$$
Q^*-Q(v)\le\frac{\lambda\delta}{2}.
$$
Now compute rational logarithm approximations with
$$
p=L+\lceil\log_2\lambda\rceil+b+3,
\qquad
\delta=2^{-p}.
$$
They are positive by the lower bound $\ell_t\ge2^{-L}$. Also,
$$
\frac{\lambda\delta}{2}\le2^{-b}.
$$
Normalize $v$ and apply Section 2. This preserves the voting rule and produces the claimed kernel.
The logarithm computation and kernel construction are polynomial in $\tau,L,p$. Since $\log\lambda\le L$, the stated running time follows. No count-vector enumeration or exact likelihood comparison is needed. $\square$
The relevant arithmetic dimension can be smaller than the number of distinct accuracies.
A coprime basis for the integers $a_t,c_t$ is a list of pairwise coprime integers $g_1,\ldots,g_s>1$ such that each input integer is a product of powers of the $g_j$.
Such a basis and the exponents can be constructed in polynomial time without prime factorization. Start with the distinct input integers greater than one. Whenever distinct current bases $u,v$ have $g=\gcd(u,v)>1$, replace them by
$$
u/g,\quad v/g,\quad g,
$$
discard ones, merge duplicates, and update the exponent representations.
This preserves every input factorization. Before merging duplicates, the product of current bases decreases from $uv$ to $uv/g$; merging decreases it further. Thus each iteration decreases its logarithm by at least $\log2$. The initial product has polynomial bit length, so there are polynomially many iterations. All bases remain at most $2^L$. Every representation exponent is at most $L$, because its base is at least two and the represented integer is at most $2^L$. Consequently, the gcd operations and representation updates have polynomial bit complexity.
Write the odds ratios as
$$
\frac{a_t}{c_t}=\prod_{j=1}^s g_j^{E_{tj}},
\qquad
|E_{tj}|\le L,
$$
and let
$$
d=\operatorname{rank}_{\mathbb Q}E.
$$
This $d$ is the multiplicative rank of the odds ratios.
To justify that interpretation, the numbers $\log g_j$ are linearly independent over $\mathbb Q$. After clearing denominators, a putative relation would give
$$
\prod_jg_j^{h_j}=1
$$
with integer $h_j$. A prime dividing a particular $g_j$ divides no other basis element, so its valuation forces $h_j=0$. Therefore rational linear relations among the $\ell_t$ are precisely rational relations among the rows of $E$.
Since every $\ell_t>0$, we have $d\ge1$. Gaussian elimination computes $d$ in polynomial time.
Choose $d$ independent rows, indexed by $I$, and $d$ columns, indexed by $J$, such that
$$
A=E_{I,J}
$$
is nonsingular. Set
$$
\Delta=|\det A|,
\qquad
H_d=d^{d/2}L^d.
$$
Hadamard’s inequality gives $\Delta\le H_d$.
Every row lies in the span of the selected rows. Cramer’s rule, applied on the selected columns, supplies integers $h_{ti}$ satisfying
$$
E_t=\frac1\Delta\sum_{i\in I}h_{ti}E_i,
\qquad
|h_{ti}|\le H_d.
$$
The numerator determinants obey the same bound because their entries also have absolute value at most $L$. Equality on the selected columns determines the coefficients uniquely; since $E_t$ belongs to the selected row span, it gives equality on all columns.
Consequently,
$$
\ell_t=\frac1\Delta\sum_{i\in I}h_{ti}\ell_i.
$$
For any voting coefficient vector $z=z(k)$, put
$$
f_i=\sum_t z_t h_{ti}.
$$
Then
$$
z\cdot\ell=\frac1\Delta\sum_{i\in I}f_i\ell_i,
\qquad
|f_i|\le\lambda H_d.
$$
Splitting each $\ell_i=\log a_i-\log c_i$ expresses the numerator using at most $2d$ integer logarithms.
We use this standard integer specialization of the Baker–Wüstholz theorem: for integers $A_j\ge2$, nonzero integer coefficients $e_j$, and
$$
\Lambda=\sum_{j=1}^r e_j\log A_j\ne0,
\qquad
B=\max\{e,|e_1|,\ldots,|e_r|\},
$$
one has
$$
|\Lambda|
\ge
\exp\left(
-C_r\prod_{j=1}^r\max\{1,\log A_j\}\log B
\right),
$$
where $C_r$ is effective and $C_r=2^{O(r\log(r+1))}$. This specialization is stated in [Etessami–Stewart–Yannakakis, Theorem 3.1](https://arxiv.org/pdf/1304.5429).
Here we discard bases equal to one and coefficients equal to zero. If $z\cdot\ell\ne0$, the remaining form is nonzero. Its number of terms is at most $2d$, its bases are at most $2^L$, and its coefficients have absolute value at most $\lambda H_d$. These verify all hypotheses.
Choose an integer
$$
M=\left\lceil d\log_2(d+1)+d\log_2(L+1)\right\rceil+3,
$$
so $H_d\le2^M$. Let $K_d$ be an effective integer upper bound on $C_r$ for $1\le r\le2d$, with
$$
K_d=2^{O(d\log(d+1))}.
$$
Define
$$
R_d=
K_d(L+1)^{2d}
\bigl(1+\lceil\log_2\lambda\rceil+M\bigr)+M.
$$
The theorem, followed by division by $\Delta\le2^M$, proves
$$
z(k)\cdot\ell\ne0
\quad\Longrightarrow\quad
|z(k)\cdot\ell|\ge e^{-R_d}>2^{-2R_d}.
$$
Now approximate each logarithm to precision
$$
p=2R_d+L+\lceil\log_2\lambda\rceil+3.
$$
The aggregate approximation error is smaller than every nonzero margin, and positivity is preserved. Normalization and Section 2 therefore give an exact rational optimizer.
The running time is
$$
\operatorname{poly}(\tau,L,R_d),
$$
or, with parameter dependence displayed,
$$
(d(L+1))^{O(d)}
\operatorname{poly}(\tau,1+\log\lambda).
$$
For fixed $d$, this is polynomial in $\tau,L$.
If $h$ is the number of distinct accuracies, then $d\le h$, because equal accuracies give equal rows of $E$. Thus this result includes the fixed-$h$ case.
There is an especially simple rank-one case. Choose any type $i$. Rank one gives rational numbers $\alpha_t$ with
$$
\ell_t=\alpha_t\ell_i.
$$
Since both logarithms are positive, $\alpha_t>0$. The coefficients are computable from $E$, so using $v_t=\alpha_t$ gives an exact rational optimizer in polynomial time without logarithmic approximation.
The following is an explicit assumption, not an unconditional result.
Suppose there is a fixed constant $C>0$ such that every nonzero integer logarithmic form satisfies
$$
\left|\sum_{j=1}^r e_j\log A_j\right|
\ge
\exp\left(
-C
\left(\sum_{j=1}^r\max\{1,\log A_j\}\right)
\log\max\{e,|e_1|,\ldots,|e_r|\}
\right).
$$
Bounds sufficient for this assumption follow from the number-theoretic conjectures discussed in [Etessami–Stewart–Yannakakis, Section 3](https://arxiv.org/pdf/1304.5429).
For the voting forms, splitting the rational odds uses at most $2\tau$ bases, each at most $2^L$, with coefficients bounded by $\lambda$. The assumption therefore supplies the uniform bound
$$
z(k)\cdot\ell\ne0
\quad\Longrightarrow\quad
|z(k)\cdot\ell|\ge e^{-R},
$$
where one may choose
$$
R=O\bigl(\tau(L+1)(1+\log\lambda)\bigr).
$$
Approximating all logarithms with
$$
p=2\lceil R\rceil+L+\lceil\log_2\lambda\rceil+3
$$
preserves every strict comparison simultaneously. Section 2 then constructs an exact rational optimizer in $\operatorname{poly}(\tau,L)$ time.
This implication does not require enumerating the comparisons: one uniform margin bound suffices.
This existence result does not depend on any separation assumption.
For each voting vector $z=z(k)$ with $z\cdot\ell\ne0$, set
$$
\sigma_z=\operatorname{sign}(z\cdot\ell).
$$
Consider the finite polyhedron
$$
P=\left\{
v:
v_t\ge1\text{ for every }t,\quad
\sigma_z z\cdot v\ge1
\text{ for every strict comparison}
\right\}.
$$
A sufficiently large positive multiple of $\ell$ belongs to $P$: there are finitely many positive signed margins.
Minimize $\sum_t v_t$ over $P$. Given any feasible point, its objective sublevel set in $P$ is nonempty and compact, because every coordinate is at least one and their sum is bounded. Thus the minimum is attained. The minimizing face is bounded and has a vertex, which is also a vertex of $P$.
At such a vertex, $\tau$ active constraint normals are linearly independent. Otherwise, a nonzero vector orthogonal to every active normal would permit sufficiently small perturbations in both directions, contradicting extremality. Hence the vertex satisfies
$$
Av=\mathbf1
$$
for a nonsingular integer matrix with entries bounded in absolute value by $\lambda$.
Cramer’s rule and Hadamard’s inequality give
$$
|\det A|\le\tau^{\tau/2}\lambda^\tau
$$
and the same bound for every numerator determinant. Therefore
$$
u=|\det A|v
$$
is a positive integer vector with
$$
u_t\le\tau^{\tau/2}\lambda^\tau.
$$
It preserves every strict Bayes comparison. Each coordinate has
$$
O\bigl(\tau\log(\tau+1)+\tau\log(\lambda+1)\bigr)
$$
bits.
Normalize $u$ and apply Section 2. With
$$
S=\sum_t n_tu_t,
$$
the retained cohort weights and subtree flows have common denominator $S$. Their numerators and the resulting kernel fractions have polynomial bit length in $\tau,L$.
Thus polynomial-size rational optimal output always exists. This proof does not locate it in polynomial time: the defining inequalities use the strict Bayes signs.
Here is a valid reduction that also works when all input masses and accuracies are required to have finite binary expansions.
Consider comparison of products of powers of odd integers:
$$
\operatorname{sign}\left(\sum_{i=1}^r e_i\log A_i\right),
$$
where $A_i\ge3$ is odd and $e_i\ne0$ is binary encoded.
Starting from an odd integer $a>1$, let $P$ be the smallest power of two exceeding $a$. Then
$$
P/2<a<P,
\qquad
a'=P-a
$$
is positive and odd, and has smaller bit length than $a$. The accuracy
$$
q=a/P
$$
is dyadic and belongs to $(1/2,1)$, with odds ratio $a/a'$.
Repeating until the remainder is one gives, in polynomial time,
$$
A_i=\prod_j\frac{q_{ij}}{1-q_{ij}},
\qquad
q_{ij}\in(1/2,1).
$$
The product telescopes, and the number of factors is at most the bit length of $A_i$.
Create one cohort for each factor, with
$$
n_{ij}=2|e_i|,
\qquad
z_{ij}=2e_i.
$$
Choose $\lambda$ to be a power of two strictly larger than $\sum_{i,j}n_{ij}$. Add a dummy cohort with
$$
n_0=\lambda-\sum_{i,j}n_{ij},
\qquad
q_0=3/4,
\qquad
z_0=0.
$$
Every cohort size is positive and even. Thus all selected $z$ coordinates are valid voting coefficients, and the masses $n_t/\lambda$ are dyadic. Choose $H$ to be a path.
The likelihood form at this selected count vector is
$$
z\cdot\ell=2\sum_i e_i\log A_i.
$$
The constructed instance has polynomial succinct encoding length.
Equality of the original products can first be tested in polynomial time using the coprime-basis construction of Section 5: equality holds exactly when every resulting basis exponent is zero. For a nonequal instance, every exact optimizer must preserve the sign of this selected comparison.
Suppose an algorithm returns an exact optimal kernel with rational entries given as fractions and acyclic nonself support. Its expected weights can be computed in topological order:
$$
U_t=n_t+\sum_sU_sD_{st},
\qquad
r_D(t)=\frac{D_{tt}U_t}{n_t}.
$$
Section 2’s fixed-proxy independence argument applies to any such acyclic kernel.
This computation has polynomial bit complexity. Expanding $U_t$ as a sum over directed type paths shows that its denominator divides the product of the denominators of all nonself entries. Each path uses every edge at most once. Also $U_t\le\lambda$, because each initial unit visits a type at most once. Thus the recurrence’s exact rational values have polynomial encoding length.
Computing the sign of $z\cdot r_D$ consequently determines the original product comparison.
Therefore a polynomial-time rational acyclic exact-optimizer construction would yield a polynomial-time algorithm for this odd-base product-of-powers comparison problem. If arbitrary binary-encoded rational accuracies are allowed, the same construction directly handles general integer bases using $q_i=A_i/(A_i+1)$.
This is not an $\mathrm{NP}$-hardness result. Moreover, an arbitrary optimizer for USER_TASK can return a cyclic kernel and general algebraic entries. The polynomial-time extraction above does not apply to that output. Existence of a rational acyclic optimum does not permit imposing those restrictions on an unrestricted optimizer oracle.
The new approximation result shows that succinct population size does not obstruct obtaining arbitrarily high prescribed accuracy in polynomial time. The multiplicative-rank result also gives an exact polynomial algorithm for a broader class than fixed numbers of accuracies.
For unrestricted exact optimization, the missing step remains one of the following:
The structural realization theorem, small-output existence theorem, and restricted comparison reduction do not supply either step. Likewise, a running time polynomial in the individually specified population size can retain polynomial dependence on $\lambda$, which is exponential in its binary encoding length.
⟨structured verdict parsed — rendered above⟩
Overall assessment: correct and substantial partial progress; the requested exact complexity classification remains unresolved. The unconditional constructions and bounds withstand verification. The output expressly acknowledges that it proves neither a polynomial-time exact algorithm for the general succinct problem nor $\mathrm{NP}$-hardness.
No central mathematical step was found to be false. The main issue is incomplete resolution of USER_TASK, rather than an incorrect claim of completion.
The probability model is consistent with the task:
The equal-prior accuracy formula for a randomized decision rule is correct. Maximizing its summands independently gives the stated upper bound
$$
Q^*=\frac12\sum_{k\in\mathcal K}\max\{p_k,p_{\bar k}\}.
$$
The likelihood-ratio calculation is also correct: the binomial coefficients cancel, leaving
$$
\log\frac{p_k}{p_{\bar k}}=\sum_t(2k_t-n_t)\ell_t.
$$
For weighted majority, complementing the count vector reverses the score and complements the decision probability, including at ties. This establishes the claimed correspondence between equal-prior accuracy and the objective in USER_TASK.
The equality condition is exact. At a strict likelihood comparison, an incorrect decision or a fair voting tie incurs positive loss. Conversely, matching every strict Bayes decision maximizes every relevant summand.
The statement that Bayes ties impose no constraint is correct. The proof does not unnecessarily require preservation of zero logarithmic forms.
Finding: verified.
This is the principal structural result, and the fixed-proxy argument is valid.
The normalization implies
$$
\sum_t b_t=0.
$$
The signed subtree flows therefore satisfy the claimed divergence identities. At the root, the total-zero identity supplies the missing parent contribution.
Every positive-flow edge lies on a tree and is oriented in only one direction. Consequently, the directed nonself support is acyclic.
The identity
$$
G_t=n_t+\sum_sF_{st}=n_tw_t+\sum_sF_{ts}
$$
establishes positive denominators and row sums equal to one. All nonself entries use permitted graph edges.
The independence argument correctly addresses the model in which proxies are sampled once and remain fixed. In an acyclic graph of types, reaching an agent does not depend on that agent’s outgoing proxy choice. Hence the expected incoming weight can be multiplied by its proxy probabilities.
The recurrence
$$
U_t=n_t+\sum_sU_sD_{st}
$$
is valid in topological order. The induction identifying $U_t$ with $G_t$ checks out. Cohort symmetry and independence then give
$$
r_D(t)=D_{tt}\frac{G_t}{n_t}=w_t.
$$
Termination is also justified: a chain can take only finitely many nonself steps along the acyclic type graph. No weight is lost.
The rational construction uses only polynomially many arithmetic operations on quantities whose encoding lengths are polynomial in the input and supplied weights. It does not require expanding the population.
Applying this result to normalized log-odds establishes the graph-independent Bayes optimum over real kernels. The output correctly distinguishes this real construction from the later constructions meeting the algebraic output requirement.
The exceptional case $\tau=1$ is handled correctly: the task then requires $\lambda=1$, and the unique feasible kernel is optimal.
Finding: verified.
The integer-product separation bound is correct. Since
$$
\sum_t|z_t(k)|\le\lambda,
$$
the constructed numerator and denominator satisfy
$$
A,B\le2^{\lambda L}.
$$
For unequal positive integers $A,B$, integration of $1/x$ gives the stated lower bound
$$
\left|\log\frac AB\right|\ge2^{-\lambda L}.
$$
With the selected precision, the aggregate approximation error is at most one eighth of this lower bound. Thus all strict comparisons retain their signs.
Positivity is also checked correctly. The bound
$$
\ell_t\ge2^{-L}
$$
follows from the positive integer difference $a_t-c_t$, and the approximation error is smaller than half this bound.
The logarithm series, range reduction, and tail estimate are valid. The required number of terms is polynomial in the precision and input length, and exact rational evaluation has polynomial bit complexity. The unspecified constant in the term count is routine implementation detail, not a mathematical gap.
Normalization preserves every comparison. Section 2 then yields an exact rational optimizer in
$$
\operatorname{poly}(\tau,L,\lambda)
$$
time.
For the kernel entries, the proposed linear integer polynomial and interval $(-1,2)$ provide valid algebraic representations: every entry belongs to $[0,1]$, and a linear polynomial has exactly one root.
The output correctly states that polynomial dependence on $\lambda$ is insufficient for polynomial time in the succinct input length.
Finding: verified.
The margin argument is correct. Whenever the approximate weights disagree with a strict Bayes choice or produce a voting tie, the true likelihood margin is bounded by the aggregate weight error.
The loss identity has the correct normalization:
$$
M_k\frac{|p_k-p_{\bar k}|}{p_k+p_{\bar k}}
=\frac{|p_k-p_{\bar k}|}{2}.
$$
Also, $\sum_kM_k=1$. Thus summing over complementary count vectors does not introduce an extra factor.
The likelihood ratio gives the displayed hyperbolic-tangent expression, and $\tanh x\le x$ applies in the stated range. Consequently,
$$
Q^*-Q(v)\le\frac{\lambda\delta}{2}.
$$
The selected precision ensures both positivity and error at most $2^{-b}$. Since $\log\lambda$ is part of the input length, the construction indeed runs in
$$
\operatorname{poly}(\tau,L,b)
$$
time.
This is an approximation guarantee for a constructed kernel. It does not require evaluating the optimal accuracy or enumerating count vectors.
Finding: verified.
The refinement operation preserves the factorization representations. Its termination argument is valid: each operation decreases the product of the current distinct bases by at least a factor of two before any additional decrease from merging duplicates.
The initial logarithm of that product is polynomially bounded. The number and sizes of current bases remain polynomially bounded, and representation exponents cannot exceed the logarithmic size of the integer being represented. Thus the claimed polynomial bit complexity is justified.
Pairwise coprimality establishes rational independence of the basis logarithms by prime valuations. Therefore the rational rank of the exponent matrix is the multiplicative rank claimed.
The selection of independent rows and nonsingular columns is valid. Cramer’s rule supplies the stated integer coefficients, with the sign of the determinant absorbed into their numerators.
The Hadamard bounds apply to both denominator and numerator determinants because their entries have absolute value at most $L$. Equality on the selected columns determines the row-span coefficients uniquely.
The voting coefficients therefore satisfy the claimed reduction and bound
$$
|f_i|\le\lambda H_d.
$$
The integer specialization stated in the output matches Theorem 3.1 of the cited paper, including the effective constant growth. The theorem does not require distinct or multiplicatively independent bases. After discarding bases equal to one and coefficients equal to zero, all hypotheses are met whenever the original form is nonzero. [Etessami–Stewart–Yannakakis, Theorem 3.1](https://arxiv.org/pdf/1304.5429)
The bounds on the bases, coefficients, and determinant justify $R_d$. Division by $\Delta$ is accounted for. The conversion
$$
e^{-R_d}>2^{-2R_d}
$$
is valid, and the chosen approximation precision preserves every strict sign.
The running times
$$
\operatorname{poly}(\tau,L,R_d)
$$
and
$$
(d(L+1))^{O(d)}\operatorname{poly}(\tau,1+\log\lambda)
$$
are consistent. For fixed $d$, this gives polynomial time in $\tau,L$.
The rank-one case and the implication $d\le h$ are valid.
Finding: verified, with one minor reference issue: the opening comparison to NOTES names an unavailable document. The mathematical inclusion of the fixed-number-of-distinct-accuracies case is independently established here.
The separation bound is explicitly presented as an assumption. It is not misrepresented as an unconditional theorem.
Under that assumption, the number of logarithmic terms, their base sizes, and their coefficient sizes yield the stated polynomial bound on $R$. The approximation and realization steps then provide the claimed conditional algorithm.
The cited paper discusses conjectural bounds sufficient for this purpose. [Etessami–Stewart–Yannakakis, Section 3](https://arxiv.org/pdf/1304.5429)
Finding: the conditional implication is verified; it contributes no unconditional general classification.
The polyhedron is nonempty because there are finitely many strict comparisons and all their signed log-odds margins are positive.
The bounded objective sublevel argument correctly establishes attainment. The minimizing face is bounded and therefore has a vertex, which is also a vertex of the original polyhedron.
At a vertex, the active normals must span the ambient space. The stated perturbation argument justifies selecting $\tau$ independent active constraints.
All constraint coefficients are integers bounded in absolute value by $\lambda$, and their right-hand sides are one. Cramer’s rule and Hadamard’s inequality therefore give the claimed coordinate bounds after clearing the determinant.
Normalization and the flow construction preserve polynomial encoding length. Thus a polynomial-size rational exact optimizer exists.
The output correctly distinguishes this existence theorem from an efficient method for finding the optimizer.
Finding: verified.
The odd-base encoding is valid. At each step, the remainder is positive, odd, and has smaller bit length. The odds ratios telescope, and the construction has polynomial encoding length.
The selected coordinates satisfy the voting-vector range and parity conditions. The dummy cohort is positive and even, its selected coordinate is valid, and the masses are dyadic. The path graph satisfies connectivity.
The likelihood form is exactly twice the original comparison form. Equality testing via the coprime basis is justified by the earlier construction.
For rational kernels with acyclic nonself support, the recurrence for expected weights is valid. The path-denominator argument and bound $U_t\le\lambda$ justify polynomial-size intermediate rational values and polynomial-time sign extraction.
The reduction consequently establishes the restricted implication claimed. It does not establish $\mathrm{NP}$-hardness, and the output correctly explains why it does not apply to arbitrary cyclic kernels with algebraic entries.
Finding: verified.
Major — incomplete resolution of the assigned target. The general exact problem remains unclassified. Polynomial dependence on $\lambda$, approximation algorithms, fixed-rank algorithms, and polynomial-size output existence do not settle whether the unrestricted task has a polynomial-time exact algorithm or is $\mathrm{NP}$-hard.
To complete the assignment, the prover must supply one of the two general results it identifies, using the specified algebraic output model. This requires additional mathematics; no clarification of the existing arguments resolves it.
Minor — unavailable reference. Identify NOTES with a precise accessible reference, or remove that comparison. This does not affect the independently proved fixed-rank result.
The direction is promising because its structural realization and arithmetic reductions are sound. The report should retain its explicit partial status.
⟨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.