d4-conf-ijcai-2019-0587 (d4-conf-ijcai-2019-0587)

Given a fixed question set \(\mathcal Q\), answer sets \(\mathcal C_q\), and a distribution \(\mu\) with binary-rational masses over the observed answer signatures \(t=(t_q)_{q\in\mathcal Q}\), let \(a(t,u)=|\{q\in\mathcal Q:t_q=u_q\}|\) and \(p_\mu=\frac{1}{|\mathcal Q|}\sum_{t,u}\mu_t\mu_u a(t,u)\). Define \(Q_\mu(t,u)=\sum_{j=a(t,u)}^{|\mathcal Q|}\binom{|\mathcal Q|}{j}p_\mu^j(1-p_\mu)^{|\mathcal Q|-j}\), \(\gamma_\mu(t,u)=-\log Q_\mu(t,u)\), and \(d_R(t)=\sum_{u\in R}\mu_u\gamma_\mu(t,u)\). Find a nonempty set of signatures \(R\) maximizing \(\min_{t\in R}d_R(t)\).

Input consists of a nonempty question set \(\mathcal Q\), with \(m=|\mathcal Q|\), and finite answer sets \(\mathcal C_q\), each of the same size \(s\ge 2\).
A society is given by its support \(T\): the list of \(\tau\) distinct complete answer signatures \(t\in\prod_{q\in\mathcal Q}\mathcal C_q\) with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible signatures; \(L\) is the total binary input length.
Define \(a(t,u)=|\{q\in\mathcal Q:t_q=u_q\}|\) and \(p_\mu=m^{-1}\sum_{t,u\in T}\mu_t\mu_u a(t,u)\). Promise \(0<p_\mu<1\).
Define \(Q_\mu(t,u)=\sum_{j=a(t,u)}^m\binom{m}{j}p_\mu^j(1-p_\mu)^{m-j}\) and \(\gamma_\mu(t,u)=-\ln Q_\mu(t,u)\).
A feasible solution is a nonempty subset \(R\subseteq T\), selecting the entire mass of each included signature. Set \(d_R(t)=\sum_{u\in R}\mu_u\gamma_\mu(t,u)\), including \(u=t\), and \(F(R)=\min_{t\in R}d_R(t)\). Any exact maximizer is acceptable when there are ties.
Use the binary Turing model, with these expressions interpreted exactly and without a unit-cost oracle for real arithmetic; state running times in \(m,\tau,s,L\).

Is finding a nonempty \(R\subseteq T\) maximizing \(F(R)\) solvable in polynomial time in \(m,\tau,s,L\), or is it NP-hard?

For a finite list of \(n\) workers, the discrete expert-core problem has an algorithm with stated running time \(O(n^2m)\); its degrees exclude the worker herself, and its agreement probability averages over distinct worker pairs.
That result does not establish a bit-complexity bound for this exact binary-rational mass problem.

Partial progress

The unrestricted polynomial-time versus $\mathrm{NP}$-hardness classification is not resolved here.

I prove two further results:

• An unconditional exact algorithm runs in

$$ 2^{O(\sqrt L\log(L+2))}\operatorname{poly}(m,\tau,s,L) $$
for the stated explicit support representation.

• A family of exact comparisons involving arbitrarily many binomial-tail factors reduces to finding an exact maximizer. The reduction uses dyadic masses, $s=4$, and exactly $p_\mu=1/4$.

The second result establishes a restricted reverse reduction. It does not establish hardness for general products of powers or $\mathrm{NP}$-hardness.

1. Exact preprocessing

Write the input masses as $\mu_t=r_t/d_t$, and define
$$ D=\operatorname{lcm}_{t\in T}d_t, \qquad w_t=D\mu_t. $$
Then every $w_t$ is a positive integer,
$$ \sum_{t\in T}w_t=D, \qquad \log_2D\leq L. $$
These quantities can be computed in polynomial time in $L$. This construction also applies when the masses are given as finite binary fractions.

Set
$$ A=\sum_{t,u\in T}w_tw_u a(t,u), \qquad b=mD^2. $$
Then $p_\mu=A/b$. The promise gives $0<A<b$.

For $0\leq k\leq m$, define
$$ N_k=\sum_{j=k}^{m}\binom mj A^j(b-A)^{m-j}, \qquad W=b^m. $$
Thus
$$ Q_k=\frac{N_k}{W}, \qquad g_k=-\ln Q_k=\ln W-\ln N_k, \qquad \gamma_\mu(t,u)=g_{a(t,u)}. $$
The binomial theorem and positivity of the summands give
$$ N_0=W, \qquad N_k-N_{k+1}=\binom mk A^k(b-A)^{m-k}>0. $$
Consequently, $g_0=0$ and $g_k>0$ for $k\geq1$.

All the integers $N_k$ and $W$ have at most
$$ B=1+\left\lceil m\log_2b\right\rceil =O\bigl(m(L+\log(m+1))\bigr) $$
bits. Computing the agreement counts and these integers therefore takes
$\operatorname{poly}(m,\tau,s,L)$ bit operations.

The promise also implies $\tau\geq2$: a support containing one signature would have $p_\mu=1$.

2. Peeling reduces optimization to polynomially many comparisons

Start with $S_1=T$. At stage $i$, choose a vertex $v_i\in S_i$ of minimum degree:
$$ d_{S_i}(v_i)=F(S_i). $$
Record $S_i$, and remove $v_i$ unless $S_i$ is a singleton.

Lemma. Some recorded set is an exact maximizer.

Proof. Let $R^*$ maximize $F$, and let $i$ be the first stage at which a member of $R^*$ is removed. Then $R^*\subseteq S_i$ and $v_i\in R^*$. Every contribution to a degree is nonnegative, so
$$ F(S_i)=d_{S_i}(v_i) \geq d_{R^*}(v_i) \geq F(R^*). $$
Global optimality of $R^*$ supplies the reverse inequality. Hence $F(S_i)=F(R^*)$.

This proof includes the self-contributions, keeps $p_\mu$ fixed, and permits arbitrary choices among tied minimum-degree vertices. $\square$

For implementation, maintain
$$ \beta_{t,k}(S) =\sum_{\substack{u\in S\\a(t,u)=k}}w_u. $$
Then
$$ D\,d_S(t)=\sum_{k=1}^{m}\beta_{t,k}(S)(\ln W-\ln N_k). $$
Deleting one vertex changes one coefficient for each remaining vertex. Scanning for a minimum at every stage and comparing the recorded values requires $O(\tau^2)$ comparisons.

Every comparison between degrees, including degrees from different stages, has the form
$$ D\bigl(d_S(t)-d_H(v)\bigr) =\Lambda=\sum_{i=1}^{n}c_i\ln z_i, $$
where, after omitting zero coefficients and bases equal to $1$,

• each $z_i$ is a positive integer with at most $B$ bits;
• each $c_i$ is a nonzero integer satisfying $|c_i|\leq D$;
• the number of terms satisfies

$$ n\leq r:=\min\{m+1,\,2\tau+1\}. $$

To check the coefficient bound explicitly, the coefficient of $\ln W$ is
$$ \sum_{k=1}^{m}\beta_{t,k}(S) -\sum_{k=1}^{m}\beta_{v,k}(H). $$
Both sums belong to $[0,D]$. The coefficient of $\ln N_k$ is
$\beta_{v,k}(H)-\beta_{t,k}(S)$, which also belongs to $[-D,D]$.

The bound $m+1$ comes from grouping by agreement count. The bound $2\tau+1$ comes from retaining the individual contributions from $S$ and $H$.

3. An unconditional subexponential exact algorithm

3.1. The quantitative theorem used

I use the following integer specialization of the Baker–Wüstholz theorem. For positive integers $z_i>1$ and nonzero integer coefficients $c_i$, put
$$ \Lambda=\sum_{i=1}^{n}c_i\ln z_i, \qquad H=\max\{3,|c_1|,\ldots,|c_n|\}. $$
If $\Lambda\neq0$, then
$$ |\Lambda| \geq \exp\left( -C(n)\prod_{i=1}^{n}\max\{\ln z_i,1\}\,\ln H \right), $$
where
$$ C(n)=18(n+1)!\,n^{n+1}32^{n+2}\ln(2n). $$
This specialization is stated as Theorem 3.1 in [Etessami, Stewart, and Yannakakis](https://arxiv.org/pdf/1304.5429).

Its hypotheses hold for the comparisons above: the bases are positive rational integers, the coefficients are rational integers, and the logarithms are real logarithms of positive numbers. Bases equal to $1$ and zero coefficients have already been omitted.

Define the explicitly computable integer
$$ \widehat C(r) =18(r+1)!\,r^{r+1}32^{r+2}(2r), $$
and put
$$ M=\widehat C(r)(B+1)^r(L+2). $$
Since $n\leq r$, $z_i<2^B$, and $|c_i|\leq D\leq2^L$, the theorem implies
$$ \Lambda\neq0 \quad\Longrightarrow\quad |\Lambda|\geq e^{-M}>2^{-2M}. $$
The last inequality follows from $2\ln2>1$.

Thus the theorem gives an explicit separation bound, although its required precision need not be polynomial in the input length.

3.2. Computing the required approximations

For completeness, logarithms of $B$-bit positive integers can be approximated to additive error $2^{-P}$ in $\operatorname{poly}(B,P)$ bit operations.

Indeed, write
$$ z=2^e y, \qquad 1\leq y<2, \qquad 0\leq e\leq B. $$
For $x=(y-1)/(y+1)$, one has $0\leq x<1/3$ and
$$ \ln y =2\sum_{j=0}^{\infty}\frac{x^{2j+1}}{2j+1}. $$
Truncation after $j=R$ has error at most
$$ 2\sum_{j=R+1}^{\infty}(1/3)^{2j+1} =\frac94\,3^{-(2R+3)}. $$
The same series, with $x=1/3$, approximates $\ln2$.

Taking $R=O(P+\log(B+1))$ makes the error in $e\ln2+\ln y$ at most $2^{-P-1}$. Downward rounding to a dyadic rational with denominator $2^{P+1}$ adds less than $2^{-P-1}$ error.

There are polynomially many rational operations. Their operands have polynomial bit length: each term has polynomial bit length, and even multiplying all denominators occurring in the finite sum produces only polynomially many bits. Hence this is a bit-complexity bound, rather than an arithmetic-operation bound.

Apply this procedure to each logarithm in $\Lambda$, with enough additional precision to account for
$$ \sum_i|c_i|\leq rD. $$
We can therefore compute a rational $\widehat\Lambda$ satisfying
$$ |\widehat\Lambda-\Lambda| \leq 2^{-(2M+3)} $$
in $\operatorname{poly}(m,\tau,s,L,M)$ bit operations.

Let $\delta=2^{-2M}$. Then:

• if $\Lambda=0$, one has $|\widehat\Lambda|\leq\delta/8$;
• if $\Lambda\neq0$, one has

$$ |\widehat\Lambda| \geq|\Lambda|-\delta/8 >7\delta/8. $$

Consequently, testing whether $|\widehat\Lambda|\leq\delta/2$ detects equality exactly. Otherwise, the sign of $\widehat\Lambda$ is the sign of $\Lambda$. This handles exact ties without a real-arithmetic oracle.

3.3. Running time

The preceding comparison algorithm and peeling give running time
$$ \operatorname{poly}(m,\tau,s,L)\, 2^{O(r\log(r(B+1)))}. $$
Indeed,
$$ \log_2 M =O\bigl(r\log(r+1)+r\log(B+1)+\log(L+2)\bigr), $$
and the approximation algorithm is polynomial in the numerical precision $M$.

For the stated explicit list representation, each of the $\tau$ signatures contains $m$ answer entries. In the usual binary index encoding, every entry occupies at least one bit. Thus
$$ m\tau\leq L. $$
It follows that
$$ r=1+\min\{m,2\tau\} \leq1+\sqrt{2m\tau} \leq1+\sqrt{2L}. $$
Also $m\leq L$, so $B=O(L^2)$. Substitution yields the unconditional exact bound
$$ \boxed{ 2^{O(\sqrt L\log(L+2))} \operatorname{poly}(m,\tau,s,L). } $$

In particular, the same argument gives polynomial time whenever $m$ or $\tau$ is fixed. When both vary, the displayed bound remains subexponential rather than polynomial.

4. A restricted comparison problem

Here is the arithmetic problem that will reduce back to exact optimization.

Let $m\geq1000$, represented in unary, and define
$$ I_m=\left\{ k\in\mathbb Z: \frac{4m}{5}\leq k\leq\frac{81m}{100} \right\}. $$
For $X\sim\operatorname{Bin}(m,1/4)$, put
$$ g_j=-\ln\Pr(X\geq j), \qquad h_k=g_k+g_{m-k}. $$

The input consists of two dyadic probability distributions $\alpha$ and $\beta$ on $I_m$. Only their positive entries are listed. The task is to compare
$$ H_\alpha=\sum_{k\in I_m}\alpha_kh_k \qquad\text{and}\qquad H_\beta=\sum_{k\in I_m}\beta_kh_k. $$

Proposition. This comparison problem has a polynomial-time Turing reduction to finding an exact maximizer in the society problem, using only instances with $s=4$ and $p_\mu=1/4$.

The proof requires bounds that ensure the constructed blocks have unique optimal subsets.

5. Binomial estimates for the reduction

Throughout this section, the probability parameter is $1/4$. In particular,
$$ g_m=m\ln4. $$

5.1. Two elementary inequalities

For every $0\leq j\leq m$, requiring the first $j$ Bernoulli trials to succeed guarantees at least $j$ successes. Therefore
$$ \Pr(X\geq j)\geq4^{-j}, \qquad g_j\leq j\ln4. $$
Consequently,
$$ g_j+g_{m-j}\leq g_m. $$

Also, if $j\leq m/5$, then
$$ \mathbb E X=\frac m4, \qquad \operatorname{Var}(X)=\frac{3m}{16}. $$
Chebyshev's inequality gives
$$ \Pr(X<j) \leq \Pr\left(\left|X-\frac m4\right|\geq\frac m{20}\right) \leq\frac{75}{m}. $$
For $m\geq1000$, this is less than $1/2$, so
$$ j\leq\frac m5 \quad\Longrightarrow\quad g_j\leq\ln2. $$

5.2. Bounds through relative entropy

Define
$$ \mathcal D(x) =x\ln(4x)+(1-x)\ln\left(\frac{4(1-x)}3\right), $$
with the continuous interpretation at the endpoints.

For an integer $j$ with $j/m\geq1/4$,
$$ m\mathcal D(j/m) \leq g_j \leq m\mathcal D(j/m)+\ln(m+1). $$

For the lower bound, exponential Markov inequality gives, for $u\geq0$,
$$ \Pr(X\geq j) \leq e^{-uj}\left(\frac{3+e^u}{4}\right)^m. $$
When $x=j/m<1$, choose $e^u=3x/(1-x)$. Substitution gives
$\Pr(X\geq j)\leq e^{-m\mathcal D(x)}$. The endpoint $j=m$ follows directly.

For the upper bound, consider a binomial distribution with parameter $x=j/m$. Its probability at $j$ is a maximum among its $m+1$ probabilities: the consecutive probability ratios decrease, the ratio at $j-1$ is greater than $1$, and the ratio at $j$ is less than $1$. Hence
$$ \binom mj x^j(1-x)^{m-j}\geq\frac1{m+1}. $$
It follows that the probability at $j$ under parameter $1/4$ is at least
$e^{-m\mathcal D(x)}/(m+1)$. The upper bound on $g_j$ follows because the tail includes this probability.

Furthermore,
$$ \mathcal D'(x)=\ln\left(\frac{3x}{1-x}\right), $$
so $\mathcal D$ is increasing on $[1/4,1]$.

5.3. Explicit bounds on the required interval

First,
$$ \frac9{20}\ln4 < \mathcal D(4/5) < \frac12\ln4. $$
These inequalities can be verified entirely with integers. The lower inequality is equivalent to
$$ 2^{54}>3^4 5^{20}, $$
and the upper inequality is equivalent to
$$ 2^{26}<3^2 5^{10}. $$
Explicitly,
$$ 18014398509481984>7724761962890625, $$
and
$$ 67108864<87890625. $$

On $[4/5,81/100]$, one has $\mathcal D'(x)<3$, because
$$ \frac{3x}{1-x}\leq\frac{243}{19} < \frac{131}{8} = \sum_{j=0}^{4}\frac{3^j}{j!} <e^3. $$
Also $\ln4>6/5$. One elementary justification is that
$$ \ln z>\frac{2(z-1)}{z+1} \qquad(z>1), $$
as follows by differentiating the difference; apply this with $z=4$.

Therefore
$$ \mathcal D(81/100) < \frac12\ln4+\frac3{100} < \frac{21}{40}\ln4. $$

For $m\geq1000$,
$$ \ln(2(m+1))<\frac{3m}{100}<\frac{m\ln4}{40}. $$
For the first inequality, the difference
$3m/100-\ln(2(m+1))$ is increasing on this range. It is positive at $m=1000$, since
$$ e^{30}>1+30+450+4500=4981>2002. $$

Combining these estimates with the preceding binomial bounds gives, for every $k\in I_m$,
$$ \boxed{ \frac9{20}g_m<h_k<\frac{11}{20}g_m. } $$
Indeed, the lower bound follows from $g_k\geq m\mathcal D(k/m)$. For the upper bound, use
$$ g_k < \frac{21}{40}g_m+\ln(m+1), \qquad g_{m-k}\leq\ln2, $$
and absorb their combined error using $\ln(2(m+1))<g_m/40$.

Finally, we need
$$ j\geq\frac{99m}{100} \quad\Longrightarrow\quad g_j>\frac{47}{50}g_m. $$
To verify this, let
$$ \mathcal H(x)=-x\ln x-(1-x)\ln(1-x). $$
Then
$$ \mathcal D(99/100) = \frac{99}{100}\ln4 +\frac1{100}\ln(4/3) -\mathcal H(1/100). $$
Now
$$ \mathcal H(1/100) = \frac{\ln100}{100} +\frac{99}{100}\ln(100/99) < \frac{5}{100}+\frac1{100} =\frac3{50}. $$
Here $\ln(1+z)<z$ gives the second estimate, and $\ln100<5$ follows, for example, from
$$ e^5>\sum_{j=0}^{6}\frac{5^j}{j!} =\frac{16289}{144}>100. $$
Since $\ln4>6/5$, we obtain
$$ \mathcal D(99/100) > \frac{99}{100}\ln4-\frac3{50} > \frac{47}{50}\ln4. $$
Monotonicity of $\mathcal D$ and the lower binomial bound prove the assertion.

6. Constructing and analyzing the society

6.1. Two blocks with four answer symbols

Give every question the answer set $\{0,1,2,3\}$.

For a distribution $\alpha$ and two different symbols $a,b$, construct a block as follows:

• two hub signatures $a^m$ and $b^m$, each of mass $3/32$;
• for every $k$ with $\alpha_k>0$, two satellite signatures

$$ v_k=a^k b^{m-k}, \qquad \bar v_k=b^k a^{m-k}, $$
each of mass $5\alpha_k/32$.

The notation denotes concatenation of answer symbols. All signatures within a block are distinct because $0<k<m$ and the listed values of $k$ are distinct.

The total mass of a block is
$$ 2\frac3{32} +2\frac5{32}\sum_k\alpha_k =\frac12. $$

Construct the first block using $\alpha$ and symbols $0,1$, and the second using $\beta$ and symbols $2,3$. Their union is the society.

All masses are positive dyadic rationals, and their total is $1$.

At every question, each answer symbol has marginal mass $1/4$. For example, in the first block, the complementary satellite pairs contribute total marginal mass $5/32$ to each of $0,1$, and the corresponding hub contributes another $3/32$.

The identity
$$ p_\mu =\frac1m\sum_{q\in\mathcal Q} \sum_{c\in\mathcal C_q} \left(\sum_{t:t_q=c}\mu_t\right)^2 $$
therefore gives
$$ \boxed{p_\mu=4(1/4)^2=1/4.} $$
The promise is satisfied exactly.

Signatures in different blocks agree on no question. Hence their mutual weight is $g_0=0$.

If the two distributions have $n_\alpha,n_\beta$ positive entries, the society has
$$ \tau=4+2n_\alpha+2n_\beta. $$
Its explicit encoding has length polynomial in $m$ and the comparison input length. Since $m$ is represented in unary, this is a polynomial-time construction.

6.2. The full block has its hubs as bottlenecks

Consider the first block, with the globally fixed probability $1/4$. The degrees of its two hubs in the full block are equal to
$$ J_\alpha = \frac3{32}g_m +\frac5{32}\sum_k\alpha_kh_k. $$
The estimates from Section 5 give
$$ \frac{21}{128}g_m < J_\alpha < \frac{23}{128}g_m. $$

For two satellites with the same orientation,
$$ a(v_k,v_\ell)=a(\bar v_k,\bar v_\ell) =m-|k-\ell| \geq\frac{99m}{100}. $$
Thus each corresponding weight exceeds $(47/50)g_m$.

The satellites of either orientation have total mass $5/32$. A satellite indexed by $k$ also receives from the hubs the contribution $(3/32)h_k$. Ignoring the remaining nonnegative contributions, its degree in the full block is greater than
$$ \frac5{32}\frac{47}{50}g_m +\frac3{32}\frac9{20}g_m = \frac{121}{640}g_m. $$
But
$$ J_\alpha<\frac{23}{128}g_m =\frac{115}{640}g_m. $$
Therefore the hubs are the bottlenecks, and the full block has objective value exactly $J_\alpha$.

6.3. The full block is its unique optimum

Let $R$ be a proper nonempty subset of the block.

Case 1: $R$ contains no hub.

For any satellite signature $t$, complementarity gives
$$ a(t,v_k)+a(t,\bar v_k)=m. $$
Section 5 therefore implies
$$ g_{a(t,v_k)}+g_{a(t,\bar v_k)}\leq g_m. $$
Its degree even in the full satellite set is at most
$$ \sum_k\frac{5\alpha_k}{32}g_m =\frac5{32}g_m. $$
Deleting signatures cannot increase a degree. Hence
$$ F(R)\leq\frac5{32}g_m < \frac{21}{128}g_m <J_\alpha. $$

Case 2: $R$ contains a hub but omits a satellite.

Every satellite agrees with either hub on either $k$ or $m-k$ questions. Both numbers are positive, so every such contribution is strictly positive.

The other hub contributes zero. Thus the degree of any retained hub is strictly smaller than its full-block degree $J_\alpha$. Consequently $F(R)<J_\alpha$.

Case 3: $R$ contains all satellites and exactly one hub.

Choose a satellite whose agreement with the retained hub is $m-k\leq m/5$. Its satellite contribution is at most $(5/32)g_m$, by Case 1, and its hub contribution is at most $(3/32)\ln2$. Therefore
$$ F(R)\leq\frac{5g_m+3\ln2}{32}. $$
Since $g_m=m\ln4$ and $m>6$,
$$ 3\ln2<\frac{g_m}{4}. $$
It follows that
$$ F(R)<\frac{21}{128}g_m<J_\alpha. $$

These cases cover all proper nonempty subsets. Hence the full block is its unique optimum. The same proof applies to the second block.

6.4. An optimizer reveals the comparison

The two block values satisfy
$$ J_\alpha-J_\beta = \frac5{32}(H_\alpha-H_\beta). $$
Cross-block contributions vanish. Thus, if a selected set meets both blocks, its objective is the minimum of its two within-block objectives.

If $H_\alpha>H_\beta$, the unique global maximizer is the full first block. If $H_\beta>H_\alpha$, it is the full second block.

If they are equal, the maximizers are the full first block, the full second block, and their union. This follows from uniqueness of the optimum within each block.

Thus an exact optimizer identifies the sign whenever the compared values are unequal.

6.5. Equality can be tested in polynomial time

To handle the equality case without relying on the optimizer’s tie choice, define
$$ M_j=\sum_{\ell=j}^{m}\binom m\ell 3^{m-\ell}. $$
Then
$$ g_j=m\ln4-\ln M_j, \qquad h_k=2m\ln4-\ln(M_kM_{m-k}). $$

Let $E$ be a common denominator of $\alpha$ and $\beta$, and write
$e_k=E\alpha_k$ and $f_k=E\beta_k$. Since both distributions sum to $1$, the constant logarithmic terms cancel. Hence
$$ H_\alpha=H_\beta \quad\Longleftrightarrow\quad \prod_k(M_kM_{m-k})^{e_k} = \prod_k(M_kM_{m-k})^{f_k}. $$
The bases have $O(m)$ bits and the exponents have polynomial encoding length.

Here is a polynomial equality test for such products. Remove bases equal to $1$ and zero exponents. Whenever opposite-side bases $x,y$ have $g=\gcd(x,y)>1$, replace their factors $x^e,y^f$ by
$$ (x/g)^e,\qquad(y/g)^f, $$
and append $g^{e-f}$ to the left if $e>f$, or $g^{f-e}$ to the right if $f>e$. This divides both represented products by $g^{\min(e,f)}$, preserving equality.

The product of all listed bases, ignoring exponents, decreases by a factor at least $2$ at each step. Thus the number of steps is bounded by the initial sum of base bit lengths. Bases never increase, exponent differences never exceed the previous maximum exponent, and list lengths grow by at most one per step. Every step therefore has polynomial bit complexity.

At termination, every left base is coprime to every right base. The represented products are then equal precisely when both sides are empty.

This detects equality in polynomial time. Otherwise, one optimizer call supplies the sign, completing the claimed reduction.

7. What remains open

The exact upper bound above improves the unconditional exponential algorithm to subexponential time. It does not establish polynomial time or exclude $\mathrm{NP}$-hardness under unrestricted polynomial-time reductions.

The reverse reduction shows that even dyadic masses, four answers per question, and a fixed agreement probability retain a nontrivial exact arithmetic comparison problem. It does not reduce general product-of-powers comparison to this problem, and no $\mathrm{NP}$-hardness result follows from it.

To settle the assigned classification, a further argument is needed: either a polynomial-time exact comparison method sufficient for optimization, or a valid hardness reduction. Neither is proved here.

⟨structured verdict parsed — rendered above⟩

The appropriate assessment is partial. The two auxiliary results are sound in substance, subject to minor boundary and implementation clarifications. Neither establishes polynomial-time solvability or $\mathrm{NP}$-hardness for the unrestricted problem. The prover correctly acknowledges this limitation.

1. Exact preprocessing

The common-denominator construction is valid. Since $D$ is a common multiple of all denominators, every $w_t=D\mu_t$ is a positive integer, and normalization gives
$$ \sum_t w_t=D. $$
The bound $\log_2D\leq L$ follows from bounding the least common multiple by the product of the encoded denominators. Standard integer arithmetic computes these quantities in polynomial bit complexity.

The expressions
$$ p_\mu=\frac{A}{b},\qquad Q_k=\frac{N_k}{b^m} $$
follow directly by substitution. The promise ensures that every binomial summand is positive. The stated bit bound on $N_k$ and $W$ is correct because
$$ 0<N_k\leq W=b^m. $$
Agreement counting and construction of these integers therefore require polynomially many bit operations.

Minor issue — endpoint notation. Only $N_0,\ldots,N_m$ are defined, whereas the displayed difference identity contains $N_{k+1}$. Its range should be stated as $0\leq k<m$, or $N_{m+1}=0$ should be defined. This does not affect the positivity conclusion.

The inference $\tau\geq2$ is correct.

2. Peeling and the comparison representation

Whenever the stated first removal stage exists, the peeling proof is correct:
$$ R^*\subseteq S_i,\qquad v_i\in R^* $$
imply
$$ F(S_i)=d_{S_i}(v_i)\geq d_{R^*}(v_i)\geq F(R^*). $$
The first inequality uses precisely the nonnegativity of all contributions. Self-contributions cause no difficulty, and the agreement probability remains fixed.

Minor issue — the last singleton is never removed. The proof defines $i$ as the first stage at which a member of $R^*$ is removed, but that stage need not exist.

For a concrete permitted instance, take $m=1$, two distinct signatures, and masses $1/4$ and $3/4$. Then
$$ p_\mu=\frac58, $$
and cross-signature contributions vanish. The unique optimum is the singleton with mass $3/4$. Peeling removes the other signature and then retains this final singleton without removing it.

Minimum clarification: explicitly account for an optimum contained in the final singleton. The algorithm already records that set; no new mathematical argument is needed.

The coefficient representation is otherwise correct. Each $\beta_{t,k}(S)$ lies in $[0,D]$, so all grouped coefficient differences have absolute value at most $D$. Both term-count bounds are valid:
$$ n\leq m+1,\qquad n\leq2\tau+1. $$
Scanning all remaining vertices and comparing the recorded objective values uses $O(\tau^2)$ comparisons. The stated running time also allows polynomial overhead for manipulating coefficient vectors.

3. Exact comparisons and the subexponential bound

The integer specialization of Baker–Wüstholz is accurately stated. The hypotheses match the comparisons after removing unit bases and zero coefficients. The cited [Theorem 3.1](https://arxiv.org/pdf/1304.5429) supports the stated constant and lower bound; replacing the theorem’s coefficient parameter by the larger $H\geq3$ gives a valid weaker bound.

The proposed $M$ dominates the theorem’s exponent because
$$ \max\{\ln z_i,1\}\leq B+1,\qquad \ln H\leq L+2, $$
and $\widehat C(r)$ dominates $C(n)$ for $1\leq n\leq r$. Consequently,
$$ \Lambda\neq0\implies |\Lambda|\geq e^{-M}>2^{-2M} $$
is justified. An empty comparison sum is simply zero and presents no difficulty.

The logarithm approximation argument is valid:

• The series parameter satisfies $0\leq x<1/3$ for $\ln y$, and $x=1/3$ is valid for $\ln2$.
• The geometric tail bound has the correct constant and exponent.
• The additional precision accommodates multiplication by $e$ and by the coefficients $c_i$.
• Exact rational evaluation of the finite sums has polynomial operand length in $B$ and the requested precision.

The equality threshold and sign test are correct. They distinguish zero from every nonzero comparison using the established separation bound, including exact ties.

The running-time calculation is also correct. Under the explicit signature-list encoding,
$$ m\tau\leq L,\qquad r\leq1+\sqrt{2L},\qquad B=O(L^2). $$
These imply the claimed bound
$$ 2^{O(\sqrt L\log(L+2))}\operatorname{poly}(m,\tau,s,L). $$
This is subexponential in $L$, and the fixed-$m$ or fixed-$\tau$ polynomial-time conclusions follow.

4. Binomial estimates

The event argument giving $g_j\leq j\ln4$ is valid. It also proves the complementary bound
$$ g_j+g_{m-j}\leq g_m. $$

The Chebyshev calculation is correct:
$$ \frac{3m/16}{(m/20)^2}=\frac{75}{m}. $$
For $m\geq1000$, it yields the asserted $g_j\leq\ln2$ when $j\leq m/5$.

The relative-entropy lower bound follows from the displayed exponential Markov estimate and the stated choice of parameter. For $1/4\leq j/m<1$, the tilted-binomial mode argument correctly establishes the upper bound.

Minor issue — the upper-bound endpoint. The mode argument uses consecutive probability ratios that are not defined as written when $j=m$ and the tilted parameter is $1$. The lower-bound endpoint is explicitly handled, but the upper-bound endpoint is not.

Minimum clarification: explicitly include $j=m$ in the endpoint treatment for both bounds. This is routine using the already stated exact value of $g_m$.

All numerical estimates in Section 5.3 check out. In particular:

• Both integer comparisons equivalent to the bounds on $\mathcal D(4/5)$ are correct.
• The derivative bound on $[4/5,81/100]$ is valid.
• The stated exponential partial sums and the logarithmic error bound are correct.
• The entropy estimate gives the claimed strict bound at $99/100$.

Thus the two bounds used in the block construction are established:
$$ \frac9{20}g_m<h_k<\frac{11}{20}g_m, \qquad j\geq\frac{99m}{100}\implies g_j>\frac{47}{50}g_m. $$

5. Society construction and block optimality

The constructed signatures are distinct, and all listed masses are positive dyadic rationals. Each block has mass $1/2$.

Complementary satellite pairs give the asserted marginal masses at every coordinate. The marginal identity for $p_\mu$ is correct, so the constructed instance satisfies
$$ p_\mu=\frac14 $$
exactly. Cross-block agreement is zero, making all cross-block contributions vanish.

The construction has polynomial encoding length because $m$ is unary and all signatures and masses are explicitly written.

The full-block hub degrees are correctly computed as
$$ J_\alpha=\frac3{32}g_m+\frac5{32}H_\alpha. $$
The bounds
$$ \frac{21}{128}g_m<J_\alpha<\frac{23}{128}g_m $$
are arithmetically correct.

Same-orientation satellites agree on at least $99m/100$ coordinates, including the self-pair. Their total orientation mass is $5/32$. The satellite lower bound is therefore valid, and its coefficient checks:
$$ \frac5{32}\frac{47}{50}+\frac3{32}\frac9{20} =\frac{121}{640} > \frac{115}{640} =\frac{23}{128}. $$
Hence the hubs are indeed the bottlenecks.

The three cases for proper nonempty subsets are exhaustive and valid:

• Without hubs, complementarity bounds every satellite degree by $(5/32)g_m$.
• If a hub is retained and a satellite omitted, that hub loses a strictly positive contribution.
• With all satellites and exactly one hub, a satellite with low agreement with that hub exists, and the stated degree bound is strictly below $J_\alpha$.

Thus the full block is its unique optimum. The same reasoning applies to the second block.

The global optimizer analysis follows correctly from zero cross-block contributions and unique block optima. In the unequal case, the winning full block is the unique global optimum. In the equal case, precisely the two full blocks and their union maximize the objective.

6. Equality testing and the reverse reduction

The formula for $M_j$ and the cancellation of constant logarithmic terms are correct. Equality of $H_\alpha$ and $H_\beta$ is equivalent to equality of the displayed integer products.

The greatest-common-divisor cancellation preserves equality. The product of listed bases, ignoring exponents, decreases by a factor at least $2$ at every iteration. Exponents do not increase, and the iteration count and operand lengths are polynomially bounded.

Minor issue — unit factors must be removed throughout. The write-up explicitly removes unit bases before iteration, but does not explicitly remove unit bases created by division. Its final “both sides are empty” criterion requires this continuing cleanup.

For example, applying the written replacement to $2^1$ on each side leaves $1^1$ on each side. No further cancellation is possible, but the lists are nonempty.

Minimum clarification: discard unit bases after every iteration, or formulate the terminal test as requiring every remaining base to equal $1$. This is an implementation clarification, not a new lemma.

With that clarification, equality testing is polynomial, and one optimizer call handles the unequal case. The restricted polynomial-time Turing reduction is sound.

7. What is established and what remains missing

The output provides genuine progress: an exact subexponential algorithm and a restricted reverse reduction. It neither claims nor proves that the restricted comparison problem is $\mathrm{NP}$-hard, and it does not reduce unrestricted product-of-powers comparison to optimization.

Major issue relative to the assignment — the requested classification remains unsettled. Resolving it requires additional mathematics: either a polynomial-time exact optimization argument or an appropriate hardness reduction. This is explicitly acknowledged by the prover.

Another round is worthwhile, but repairing the minor issues above will only make the auxiliary results fully verifiable; it will not answer the unrestricted classification question.

⟨structured verdict parsed — rendered above⟩