Learning Real-Life Approval Elections (aamas25-00084)

Given candidates \(C\), \(t\le |C|\), and an explicitly represented rational distribution \(\mu\) over approval-ballot types \(A\subseteq C\), choose a partition \(C=C_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}C_t\) and probabilities \(p_1,\ldots,p_t\in[0,1]\) maximizing \(\sum_{A\subseteq C}\mu_A\sum_{j=1}^{t}\left(|A\cap C_j|\ln p_j+|C_j\setminus A|\ln(1-p_j)\right)\), and return an optimal partition and parameter vector.

Let \(C\) be a candidate set with \(m\geq1\), and let \(1\leq t\leq m\) be an input integer. A society is given by its support \(S\): the list of the \(\tau\) approval types \(A\subseteq C\) with positive mass, each mass \(\mu_A\) a binary rational, with \(\sum_{A\in S}\mu_A=1\). Here \(\tau=|S|\) is the support size, not the number of possible approval types; let \(L\) be the total input bit length.
A feasible model consists of a partition \(C=C_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}C_t\) into nonempty groups and probabilities \(p_j\in[0,1]\); probabilities for different groups may coincide. Each candidate in \(C_j\) is approved independently with probability \(p_j\).
The optimization problem returns a partition and parameter vector maximizing \(F=\sum_{A\in S}\mu_A\sum_{j=1}^{t}\bigl(|A\cap C_j|\ln p_j+|C_j\setminus A|\ln(1-p_j)\bigr)\). Use \(0\ln0=0\), and interpret a positive coefficient times \(\ln0\) as \(-\infty\). Any maximizer is acceptable; optimal probabilities are returned exactly as binary rationals.

Is this exact optimization problem solvable in polynomial time in \(m,\tau,t,L\) in the Turing bit model, or is it NP-hard?

For an explicitly listed finite electorate, maximum-likelihood fitting of a single independent approval model with at most \(t\) approval probabilities is polynomial-time solvable. [Faliszewski et al.](https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p704.pdf)
Rationally weighted fitting is known to be equivalent to fitting an induced finite electorate; the verified result does not establish a polynomial bound in the binary weight length. [Faliszewski et al., extended version](https://arxiv.org/html/2601.18651v1)

1. Status and scope

The unrestricted exact complexity classification remains unresolved here. I do not obtain either a polynomial-time algorithm or an NP-hardness reduction.

I prove three further results beyond the verified structural reduction:

• Arbitrary rational candidate marginals can be realized by a society with at most $m+1$ nested approval types.
• Equality of the optimized scores of two given partitions is decidable in polynomial time, even when $t$ is unrestricted.
• For unrestricted inputs, arbitrarily accurate additive approximation—and relative approximation of the optimal clustering loss—is possible in polynomial bit time.

I also give a precise conditional polynomial-time result and re-establish the exact special cases used below.

Throughout, a binary rational means a rational whose numerator and denominator are encoded in binary.

2. Reduction to candidate marginals

For each candidate $c$, define its marginal approval probability by
$$ q_c=\sum_{\substack{A\in S\\c\in A}}\mu_A. $$
Let $D$ be the product of the denominators of all input masses. Its binary length is at most $L+1$, and every $Dq_c$ is an integer. Thus $D$ and all marginals can be computed using polynomial-time rational arithmetic.

Interchanging the finite sums in the objective gives
$$ F=\sum_{j=1}^{t}\sum_{c\in C_j} \bigl(q_c\ln p_j+(1-q_c)\ln(1-p_j)\bigr). $$
This identity respects the endpoint conventions: the coefficient of $\ln 0$ is positive in the original expression exactly when its aggregated coefficient is positive.

For a nonempty group $B$, write
$$ n_B=|B|, \qquad s_B=\sum_{c\in B}q_c. $$
Its contribution at parameter $p$ is
$$ s_B\ln p+(n_B-s_B)\ln(1-p). $$
If $0<s_B<n_B$, its derivative is
$$ \frac{s_B-n_Bp}{p(1-p)}. $$
Consequently, its unique maximizer is $p=s_B/n_B$. If $s_B=0$, the contribution is $n_B\ln(1-p)$ and uniquely maximized at $p=0$. If $s_B=n_B$, it is uniquely maximized at $p=1$.

Define
$$ f(x)=x\ln x+(1-x)\ln(1-x), \qquad f(0)=f(1)=0. $$
For a partition $\mathcal P$, its optimized score is therefore
$$ W(\mathcal P)=\sum_{B\in\mathcal P}w(B), \qquad w(B)=n_Bf\!\left(\frac{s_B}{n_B}\right). $$
Every partition has an attained finite optimized score. Since there are finitely many partitions, a global optimum exists.

Moreover, if
$$ a_B=\sum_{c\in B}Dq_c, $$
then its optimal parameter is
$$ p_B=\frac{a_B}{n_BD}. $$
Both numerator and denominator have binary length $O(L+\log m)$. Thus the exact output parameters always have polynomial-size encodings.

3. Sorted intervals and the dynamic program

Order the candidates so that
$$ q_1\leq q_2\leq\cdots\leq q_m. $$

Lemma. Some optimal partition consists of exactly $t$ nonempty intervals of this order.

Proof. Take an optimal partition, and order its groups by their means. Suppose groups $B,E$ have sizes $n,r$ and means $u\leq v$, but contain marginals $x\in B$ and $y\in E$ with $x>y$.

Put $\delta=x-y>0$. Swapping these candidates changes the means to
$$ u-\frac{\delta}{n}, \qquad v+\frac{\delta}{r}. $$
Both remain in $[0,1]$, since they are means of actual groups.

Consider
$$ g(z)=nf\!\left(u-\frac zn\right) +rf\!\left(v+\frac zr\right), \qquad 0\leq z\leq\delta. $$
The initial means are interior: $x>0$ implies $u>0$, and $y<1$ implies $v<1$; together with $u\leq v$, this gives $0<u\leq v<1$. For $0<z<\delta$, the interpolated means are also interior.

On $(0,1)$,
$$ f'(x)=\ln\frac{x}{1-x}, \qquad f''(x)=\frac{1}{x(1-x)}>0. $$
Thus
$$ g'(z)= f'\!\left(v+\frac zr\right) - f'\!\left(u-\frac zn\right)>0, $$
because the difference between the two arguments is
$$ (v-u)+z\left(\frac1r+\frac1n\right)>0. $$
Continuity at the endpoints gives $g(\delta)>g(0)$, contradicting optimality.

Hence an earlier group cannot contain a marginal strictly larger than one in a later group. Candidates with equal marginals can be reassigned among their tied positions without changing group sizes or sums. This represents the groups as intervals in the fixed sorted order. $\square$

For an interval, define
$$ w(a,b)=(b-a+1)f\!\left( \frac{\sum_{i=a}^{b}q_i}{b-a+1} \right). $$
Let $V(i,j)$ be the best score for the first $i$ candidates partitioned into $j$ nonempty intervals. Then
$$ V(i,j)= \max_{j-1\leq h<i} \bigl(V(h,j-1)+w(h+1,i)\bigr), $$
with $V(0,0)=0$ and invalid states assigned $-\infty$.

Every interval partition has a last interval, so every feasible solution occurs in a transition. Conversely, every valid transition constructs a feasible partition. Additivity proves optimal substructure.

There are $O(tm)$ states and $O(tm^2)$ transitions. This is the same combinatorial recurrence underlying the finite-electorate algorithm in [Faliszewski et al., Theorem 4.9](https://arxiv.org/html/2601.18651v1). Its transition count alone does not establish polynomial bit complexity.

4. Exact score representation and polynomial-time equality testing

For a group $B$, put
$$ b_B=n_BD-a_B. $$
Direct substitution gives
$$ Dw(B)= a_B\ln a_B+b_B\ln b_B-n_BD\ln(n_BD), $$
where a term with zero coefficient is omitted. Therefore
$$ \exp(DW(\mathcal P)) = \prod_{B\in\mathcal P} \frac{a_B^{a_B}b_B^{b_B}} {(n_BD)^{n_BD}}, $$
again omitting zero-exponent factors.

Comparing two partition scores is equivalent to comparing two products of positive integer powers after cross-multiplication. There are at most $6t$ factors in total, and every base and exponent is at most $mD$.

This proves a polynomial-time Turing reduction of exact optimization to general product-of-powers comparison. It proves no reduction in the reverse direction.

Polynomial-time equality testing

Proposition. Given two partitions, whether their optimized scores are equal can be decided in polynomial time in the original input length and the partition encodings.

Proof. It suffices to decide whether
$$ X=\prod_i x_i^{u_i} \quad\text{and}\quad Y=\prod_j y_j^{v_j} $$
are equal, where all bases and exponents are positive binary integers. Discard bases equal to $1$.

If a left base $a$ and a right base $c$ have
$$ g=\gcd(a,c)>1, $$
and corresponding exponents $u,v$, use
$$ \frac{a^u}{c^v} = \frac{(a/g)^u}{(c/g)^v}g^{u-v}. $$
Replace the two bases by $a/g,c/g$, discarding unit bases. If $u>v$, append $g^{u-v}$ on the left; if $v>u$, append $g^{v-u}$ on the right. If $u=v$, append nothing. This preserves $X/Y$.

To bound the number of steps, consider the product of all current bases on both sides, without their exponents. At each step this product decreases by a factor $g$ if $u\neq v$, and by $g^2$ if $u=v$. It therefore decreases by at least a factor $2$.

Consequently, the number of steps is at most the sum of the binary lengths of the initial bases. Each step adds at most one factor. No base exceeds the initial maximum base, and no exponent exceeds the initial maximum exponent: new exponents are differences of existing positive exponents. All intermediate encodings therefore have polynomial size, and each gcd and update takes polynomial time.

At termination, every left base is coprime to every right base. Hence the represented integers $X,Y$ are coprime. They are equal exactly when both equal $1$, equivalently when both factor lists are empty. $\square$

Thus exact ties can be recognized efficiently. The unresolved arithmetic operation is determining the order of unequal scores.

5. Uniform polynomial-time additive approximation

Theorem. Given the society, $t$, and a rational $0<\varepsilon\leq1$, one can compute a feasible partition and its exact rational group means satisfying
$$ F\geq F^*-\varepsilon $$
in time polynomial in $m,\tau,t,L$ and the encoding length of $\varepsilon$. The precision required depends logarithmically on $1/\varepsilon$.

Here $F^*$ denotes the exact optimum.

Computing logarithms with certified error

First, let $x\in(0,1]$ be rational, with numerator and denominator at most $2^B$. Choose an integer $0\leq k\leq B$ such that
$$ 1\leq z=2^kx<2. $$
Then
$$ \ln x=\ln z-k\ln2. $$
For $1\leq z\leq2$, set
$$ r=\frac{z-1}{z+1}, \qquad 0\leq r\leq\frac13. $$
The convergent series is
$$ \ln z= 2\sum_{\ell=0}^{\infty}\frac{r^{2\ell+1}}{2\ell+1}. $$
After $N$ terms, its remainder satisfies
$$ 0\leq 2\sum_{\ell=N}^{\infty}\frac{r^{2\ell+1}}{2\ell+1} \leq \frac{2r^{2N+1}}{1-r^2} \leq \frac34\,9^{-N}. $$
The same formula computes $\ln2$, using $r=1/3$. Thus the resulting approximation to $\ln x$ has error at most
$$ (k+1)9^{-N}. $$
Choosing
$$ N=O\!\left(\log(B+1)+\log\frac1\eta\right) $$
gives error at most $\eta$.

All truncated expressions are rational. Their powers, numerators, and denominators have bit lengths polynomial in $B,N$: even multiplying the denominators of all summands gives length $O(N^2B+N\log(N+1))$. Hence exact evaluation of the truncated series takes polynomial bit time.

Approximate interval weights and exact rational dynamic programming

Set
$$ \eta=\frac{\varepsilon}{2m}. $$
For each interval $B$ with fitted probability $p_B\in(0,1)$, approximate $\ln p_B$ and $\ln(1-p_B)$ to error at most $\eta$, and define
$$ \widehat w(B)= s_B\,\widehat{\ln p_B} + (n_B-s_B)\,\widehat{\ln(1-p_B)}. $$
For $p_B\in\{0,1\}$, set $\widehat w(B)=0$, its exact score.

Since the nonnegative coefficients sum to $n_B$,
$$ |\widehat w(B)-w(B)|\leq n_B\eta. $$
For every full interval partition $\mathcal P$, this implies
$$ |\widehat W(\mathcal P)-W(\mathcal P)| \leq m\eta=\frac{\varepsilon}{2}. $$

Run the dynamic program using the rational weights $\widehat w$. Rational additions and comparisons are exact, and all resulting encodings have polynomial size. Let $\widehat{\mathcal P}$ maximize $\widehat W$, and let $\mathcal P^*$ be an exact optimal interval partition. Then
$$ \begin{aligned} W(\widehat{\mathcal P}) &\geq \widehat W(\widehat{\mathcal P})-\frac{\varepsilon}{2}\\ &\geq \widehat W(\mathcal P^*)-\frac{\varepsilon}{2}\\ &\geq W(\mathcal P^*)-\varepsilon. \end{aligned} $$
Return $\widehat{\mathcal P}$ with its exact rational group means. This proves the theorem.

In particular, error $2^{-K}$ is achievable in time polynomial in the original input parameters and $K$.

6. A quantitative loss bound and relative approximation

Define the fully individualized score
$$ F_{\mathrm{full}}=\sum_{c\in C}f(q_c), $$
and the clustering loss of a fitted partition by
$$ \mathcal L(\mathcal P)=F_{\mathrm{full}}-W(\mathcal P). $$
Let $d$ be the number of distinct candidate marginals.

Proposition.

• If $t\geq d$, the optimal clustering loss is $0$, and an exact optimum is constructible in polynomial time.
• If $t<d$, every feasible partition has clustering loss at least $D^{-2}$.

Proof. On $(0,1)$,
$$ f''(x)=\frac1{x(1-x)}\geq4. $$
Consequently, $f(x)-2x^2$ is convex there. Its continuous extension to $[0,1]$ remains convex, by taking endpoint limits in the defining convexity inequality.

Applying Jensen’s inequality to a group $B$ with mean $u$ gives
$$ \sum_{c\in B}f(q_c)-n_Bf(u) \geq 2\sum_{c\in B}(q_c-u)^2. $$
Thus every group has nonnegative loss.

If $B$ contains distinct marginals $x,y$, then
$$ 2\bigl((x-u)^2+(y-u)^2\bigr)\geq(x-y)^2. $$
Because $Dx,Dy$ are distinct integers,
$$ |x-y|\geq\frac1D. $$
Therefore this group has loss at least $D^{-2}$.

If $t<d$, some group must contain two distinct marginals: otherwise each group contains only one marginal value, requiring at least $d$ groups. This proves the second assertion.

If $t\geq d$, group candidates by equal marginals and assign each group that marginal as its probability. Every group then has zero loss. If fewer than $t$ groups result, repeatedly split a nonsingleton group while retaining its probability. Such a group exists whenever the current group count is less than $t\leq m$. This constructs exactly $t$ groups with zero loss. $\square$

Corollary. Given rational $0<\delta\leq1$, a feasible model with
$$ \mathcal L(\mathcal P)\leq(1+\delta)\mathcal L^* $$
can be computed in polynomial time in the input and the encoding length of $\delta$, where $\mathcal L^*$ is the minimum clustering loss.

Proof. If $t\geq d$, return the zero-loss construction. Otherwise, use the additive approximation theorem with
$$ \varepsilon=\frac{\delta}{D^2}. $$
Its precision requirement is polynomial, because
$$ \log\frac1\varepsilon = 2\log D+\log\frac1\delta. $$
The returned partition satisfies
$$ \mathcal L(\mathcal P) \leq\mathcal L^*+\frac{\delta}{D^2} \leq(1+\delta)\mathcal L^*, $$
using $\mathcal L^*\geq D^{-2}$. $\square$

This gives a uniform approximation result for unrestricted binary weights. It does not determine the exact maximizing partition.

7. Arbitrary marginals are realizable by nested support

Theorem. Given arbitrary rational numbers
$$ 0\leq q_1\leq\cdots\leq q_m\leq1, $$
one can construct, in polynomial time, a society having these candidate marginals and at most $m+1$ positive-mass approval types. Its support is totally ordered by inclusion.

Proof. Set $q_0=0$. For each $1\leq i\leq m$, define
$$ A_i=\{c_i,c_{i+1},\ldots,c_m\}, \qquad \mu_{A_i}=q_i-q_{i-1}. $$
Also assign
$$ \mu_{\varnothing}=1-q_m. $$
Delete every zero-mass type.

All retained masses are positive, and their sum is
$$ \sum_{i=1}^{m}(q_i-q_{i-1})+(1-q_m)=1. $$
Candidate $c_k$ belongs exactly to the listed suffixes with $i\leq k$. Its marginal is therefore
$$ \sum_{i=1}^{k}(q_i-q_{i-1})=q_k. $$
The suffixes and the empty set form a chain under inclusion.

Sorting and taking rational differences are polynomial-time operations. The approval sets require at most $O(m^2)$ bits, and the rational differences have polynomial encoding length. $\square$

Combining this construction with Section 2 proves polynomial-time equivalence between the society problem and optimization from an arbitrary rational marginal list. This equivalence already holds for societies whose support is nested and has size at most $m+1$.

Consequently, consistency constraints on marginals imposed by a society do not simplify the unrestricted problem.

8. Exact special cases and a conditional unrestricted result

Unconditional exact special cases

The following known arithmetic theorem is applicable: products of positive binary integers raised to positive binary integer powers can be compared in polynomial time when their total number of factors is bounded by a fixed constant. See [Etessami, Stewart, and Yannakakis, Proposition 3.7(2)](https://arxiv.org/pdf/1304.5429).

Fixed $t$. Each dynamic-programming comparison has at most $6t$ factors, all with polynomial binary length. For fixed $t$, the theorem supplies polynomial-time comparisons, and hence exact optimization.

Fixed support size $\tau$. A candidate’s marginal is determined by its incidence pattern across the $\tau$ support types, so
$$ d\leq2^\tau. $$
If $t\geq d$, Section 6 constructs an exact optimum. Otherwise $t<2^\tau$ is bounded by a constant, and the fixed-$t$ algorithm applies.

Fixed $k=m-t$. An interval partition is specified by omitting exactly $k$ of the $m-1$ boundaries, giving
$$ \binom{m-1}{k} $$
possibilities.

For such a partition, let $\mathcal B$ be its nonsingleton blocks. Then
$$ \sum_{B\in\mathcal B}(|B|-1)=k. $$
Hence
$$ |\mathcal B|\leq k, \qquad \sum_{B\in\mathcal B}|B|\leq2k. $$
Subtracting the common singleton score, the partition’s score difference is
$$ \sum_{B\in\mathcal B} \left(w(B)-\sum_{i\in B}f(q_i)\right). $$
It contains at most $k$ block contributions and $2k$ singleton contributions. Each contribution has at most three logarithmic terms. Comparing two differences therefore requires at most $18k$ product factors. For fixed $k$, enumeration and exact comparison both take polynomial time.

These are polynomial-time results for fixed parameter values; they are not uniform polynomial bounds for unrestricted inputs.

Conditional unrestricted polynomial time

Here is an explicit arithmetic assumption sufficient to settle the problem positively.

Assumption. There is an absolute constant $\kappa>0$ such that, for every $r\geq1$, integers $a_i\geq2$, and nonzero integers $b_i$, if
$$ \Lambda=\sum_{i=1}^{r}b_i\ln a_i\neq0, $$
then
$$ |\Lambda| \geq \frac{\kappa} {rB\left(\prod_{i=1}^{r}a_i|b_i|\right)^2}, \qquad B=\max(3,|b_1|,\ldots,|b_r|). $$
This is the parameter-$1$ case of the Lang–Waldschmidt conjecture as formulated in [Etessami, Stewart, and Yannakakis, Conjecture 3.2](https://arxiv.org/pdf/1304.5429). It is an assumption, not a proved bound.

Conditional theorem. Under this assumption, unrestricted exact optimization is polynomial-time solvable.

Proof. For two interval partitions $\mathcal P,\mathcal Q$, Section 4 represents
$$ D\bigl(W(\mathcal P)-W(\mathcal Q)\bigr) $$
as a linear form having at most $6t$ terms. Omit zero coefficients and bases equal to $1$. Every remaining base and absolute coefficient is at most
$$ M=\max(3,mD). $$
If the scores differ, the assumption gives, for some $1\leq r\leq6t$,
$$ |W(\mathcal P)-W(\mathcal Q)| \geq \frac{\kappa}{DrM^{4r+1}} \geq \frac{\kappa}{D(6t)M^{24t+1}}. $$
The binary logarithm of the reciprocal of this lower bound is
$$ O\bigl(L+\log(t+1)+t(L+\log(m+1))\bigr), $$
with an additive constant depending only on $\kappa$.

Choose additive approximation error smaller than this lower bound. Section 5 then runs in polynomial time. Its returned interval partition must be exactly optimal: a strictly suboptimal interval partition would have a deficit at least the displayed lower bound. Ties between optimal partitions cause no difficulty, since any maximizer is acceptable. $\square$

In particular, an NP-hardness reduction from satisfiability to this optimization problem, under polynomial-time Turing reductions, would imply $\mathsf P=\mathsf{NP}$ if this arithmetic conjecture holds. This is a conditional implication, not a hardness obstruction proved unconditionally.

9. Remaining open point

The combinatorial optimization reduces to sorted interval partitioning, the output probabilities have polynomial encodings, exact ties are polynomial-time decidable, and unrestricted approximation is polynomial-time solvable to any prescribed binary precision.

What remains unproved is an unconditional method for selecting exact maxima among the structured scores
$$ \sum_{B} n_Bf\!\left(\frac{a_B}{n_BD}\right) $$
in polynomial bit time, or an NP-hardness reduction to the optimization problem itself.

Neither the approximation results nor the reduction to general product-of-powers comparison settles that question.

⟨structured verdict parsed — rendered above⟩

Verification report

Assessment: partial, with substantial correct content. The output does not answer the unrestricted exact complexity question in USER_TASK. It explicitly acknowledges this limitation. Its structural, equality-testing, approximation, realizability, and fixed-parameter results are sound. The unrestricted polynomial-time result is valid only under the stated arithmetic assumption.

No central false mathematical step was found.

1. Scope and target

USER_TASK asks for an unconditional classification of exact optimization with unrestricted binary rational weights and input parameter $t$.

The prover instead establishes several auxiliary results and a conditional classification. Consequently, neither a polynomial-time algorithm nor NP-hardness for the requested unrestricted exact problem has been established.

Major issue — target remains unresolved. This is incompleteness relative to the assignment, rather than a contradiction in the prover’s expressly partial claim.

Minimum required progress: supply either an unconditional polynomial-time exact algorithm with a valid bit-complexity analysis, or a valid NP-hardness reduction to this optimization problem. Clarifying the existing approximation results cannot fill this gap.

2. Candidate marginals and fitted parameters

The reduction in Section 2 is correct.

• The product $D$ of input denominators has polynomial binary length. Each $Dq_c$ is an integer, and the marginals can be computed with polynomial-size rational arithmetic.
• Reordering the finite sums correctly produces the candidate-marginal objective. Nonnegative coefficients and positive support masses justify the stated treatment of endpoints.
• For a nonempty group, the derivative has the asserted sign, yielding the unique interior maximizer $s_B/n_B$. The two endpoint cases also have the stated unique maximizers.
• Substitution gives $w(B)=n_Bf(s_B/n_B)$.
• Every fitted partition has finite score, and the finite set of partitions therefore has a maximizer.
• The exact parameters $a_B/(n_BD)$ have polynomial-size encodings, including when $a_B=0$ or $a_B=n_BD$.

The argument covers $m=1$, $t=1$, and marginals equal to $0$ or $1$.

No issue found.

3. Sorted intervals and dynamic programming

The exchange argument in Section 3 is valid.

Given the asserted inversion, the initial group means are interior. For every $0<z<\delta$, both interpolated means remain interior: each lies strictly between its initial interior value and its final value in $[0,1]$.

Strict monotonicity of $f'$ gives $g'(z)>0$. Continuity at the endpoints then yields the strict score improvement claimed, contradicting optimality.

The absence of strict inversions implies that group membership can be made consecutive in the sorted order by rearranging equal-marginal candidates. This preserves each group’s size and sum, and hence preserves its score and nonemptiness.

The recurrence, initial state, and invalid-state convention correctly enforce exactly $t$ nonempty intervals. Its state and transition counts are correct. The cited finite-electorate recurrence matches this combinatorial structure. [Faliszewski et al., Theorem 4.9](https://arxiv.org/html/2601.18651v1)

The prover correctly distinguishes a polynomial number of transitions from polynomial Turing bit complexity.

No issue found.

4. Score representation and equality testing

The logarithmic score identity is correct:

$$ Dw(B)=a_B\ln a_B+b_B\ln b_B-n_BD\ln(n_BD). $$

The terms involving $\ln(n_BD)$ combine with total coefficient $-n_BD$. Omitting zero-coefficient terms handles endpoint groups correctly.

Exponentiation and cross-multiplication preserve score comparisons. Two partitions contribute at most $6t$ factors, with bases and exponents bounded by $mD$.

The equality-testing algorithm is also correct:

• Each gcd update preserves the represented ratio.
• The product of unweighted bases decreases by the stated factor.
• The resulting iteration bound is polynomial in the initial encoding length.
• Bases never increase, and new exponents are positive differences of existing exponents.
• Searching all current cross-pairs for a nontrivial gcd remains polynomial.
• At termination, the two represented positive integers are coprime, so equality holds exactly when both are $1$.

This establishes equality testing, not ordering of unequal scores. The prover maintains that distinction correctly.

No issue found.

5. Additive approximation

The certified logarithm calculation and approximation theorem are valid.

For rational $x\in(0,1]$, the stated normalization can be chosen with $0\leq k\leq B$. The series applies throughout the required normalized range, including the separate computation of $\ln2$.

The remainder constant checks out:

$$ \frac{2(1/3)^{2N+1}}{1-1/9} =\frac34\,9^{-N}. $$

Combining the two truncated logarithms gives the asserted error bound. The rational series evaluations have polynomial encoding length in $B$ and $N$.

For each interval, the logarithm coefficients are nonnegative and sum to its size. Thus the interval error is at most $n_B\eta$, and every full partition has error at most $\varepsilon/2$.

The three displayed inequalities correctly show that maximizing the approximate rational score returns a partition within $\varepsilon$ of the true optimum. Dynamic-programming scores sum at most $t$ polynomial-size rational weights, so their encodings remain polynomial.

No issue found. This theorem does not certify an exact maximizer without an additional separation bound.

6. Loss bound and relative approximation

Section 6 is correct.

The inequality $f''(x)\geq4$ establishes convexity of $f(x)-2x^2$ on the interior. Continuity extends convexity to the closed interval, allowing Jensen’s inequality even for endpoint marginals.

The resulting group loss bound has the correct constant. For two distinct marginals in a group,

$$ 2\bigl((x-u)^2+(y-u)^2\bigr)\geq(x-y)^2. $$

The common denominator gives $|x-y|\geq D^{-1}$, and therefore the asserted group loss is at least $D^{-2}$.

The counting argument for $t<d$ is valid. For $t\geq d$, the equal-marginal construction and subsequent splits produce exactly $t$ nonempty zero-loss groups.

The relative approximation corollary follows with $\varepsilon=\delta/D^2$, whose encoding length is polynomial.

No issue found. The positive lower bound on clustering loss does not provide a separation bound between distinct partition scores.

7. Nested-support realizability

The construction in Section 7 is correct.

The masses are nonnegative, deletion leaves only positive masses, and telescoping proves total mass $1$. Candidate membership in the suffixes gives exactly the prescribed marginal.

Repeated marginals, $q_1=0$, and $q_m=1$ are handled by deleting zero-mass types. At least one positive-mass type remains.

The support-size and encoding-size bounds are polynomial. Combined with Section 2, this proves the stated equivalence with optimization from arbitrary rational marginals.

No issue found.

8. Exact special cases

The arithmetic theorem is stated sufficiently precisely and is applicable: comparison of products with positive binary integer bases and exponents is polynomial-time when the numbers of factors are fixed constants. This matches the cited proposition. [Etessami, Stewart, and Yannakakis, Proposition 3.7(2)](https://arxiv.org/pdf/1304.5429)

• Fixed $t$: each finite dynamic-programming alternative represents at most $t$ groups, so the comparison-factor bound applies.
• Fixed $\tau$: the bound $d\leq2^\tau$ is valid. The two branches give either the zero-loss construction or bounded $t$.
• Fixed $k=m-t$: the boundary count and nonsingleton-block bounds are correct. After subtracting the common individualized score, each partition uses at most $3k$ contributions, giving at most $18k$ factors across a comparison.

For $k=0$, there is one partition, so no comparison is necessary.

No issue found. These results do not give a uniform polynomial bound when the parameters vary with the input.

9. Conditional unrestricted result

The stated assumption is a valid weakened version of the parameter-$1$ instance of the cited conjecture; using $B=\max(3,|b_i|)$ only weakens its lower bound. [Etessami, Stewart, and Yannakakis, Conjecture 3.2](https://arxiv.org/pdf/1304.5429)

The conditional calculation is correct. There are at most $6t$ logarithmic terms, and each base and absolute coefficient is at most $M$. Consequently,

$$ \prod_{i=1}^r a_i|b_i|\leq M^{2r}, $$

which yields the displayed score-separation bound after division by $D$. Its reciprocal has polynomial logarithmic size.

An additive error strictly below that separation forces the returned partition to be optimal. The final conditional implication concerning $\mathsf P=\mathsf{NP}$ is also valid.

Minor clarification: the instruction to choose an error below a bound involving the unspecified existential constant $\kappa$ leaves the algorithm’s fixed precision constant implicit. Specify that a fixed positive rational lower bound for $\kappa$ is incorporated into the conditional algorithm. This is an expositional issue, not additional mathematics.

10. Actionable feedback

Retain the proved auxiliary results and the explicit partial-status statement. Clarify the fixed constant in the conditional algorithm.

To complete the assignment, address the unconditional exact-selection problem or provide a hardness reduction. Neither efficient equality testing, arbitrarily precise approximation, nor a one-way reduction to general product-of-powers comparison establishes the requested classification.

⟨structured verdict parsed — rendered above⟩