Mind the Gap: Cake Cutting With Separation (d4-conf-aaai-2021-1087)

Given a finite type set \(T\), rational masses \(\mu_t\), rational separation intensity \(\sigma\), and rational piecewise-constant densities \(f_t\) on \([0,1]\), define \(q_t=\sup_p\operatorname*{ess\,inf}_{z\in[0,1]} f_t(X_p(z))p(z)\), where the supremum ranges over measurable \(p\ge0\) with \(X_p(z)=\int_0^z(p(u)+\sigma)\,du\) and \(\int_0^1(p(z)+\sigma)\,dz\le1\). Decide whether there exist a measurable type order \(\theta\) and piece-length profile \(p\) with \(\operatorname{Leb}\{z:\theta(z)=t\}=\mu_t\) and \(f_{\theta(z)}(X_p(z))p(z)\ge q_{\theta(z)}\) almost everywhere; more generally, compute the maximum \(\rho\) after replacing the right side by \(\rho q_{\theta(z)}\), with a finite cell-and-boundary encoding of the schedule and gaps.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The resource is \([0,1]\). Each type has an explicitly given nonnegative piecewise-constant density \(f_t\), with binary-rational breakpoints and heights and \(\int_0^1 f_t(x)\,dx=1\); zero-density intervals are allowed. Let \(m\) be the number of cells in the common breakpoint refinement and \(L\) the total input bit length. The binary-rational separation intensity satisfies \(0<\sigma<1\).
An admissible profile is a measurable integrable \(p:[0,1]\to\mathbb R_{\ge0}\) with \(X_p(z)=\int_0^z(p(u)+\sigma)\,du\) and \(X_p(1)\le1\). Here \(z\) indexes population mass, \(p(z)\) is resource length per unit mass, and \(\sigma\) is mandatory separation length per unit mass; any suffix beyond \(X_p(1)\) is unused.
Define \(q_t=\sup_{p\text{ admissible}}\operatorname*{ess\,inf}_{z\in[0,1]}f_t(X_p(z))p(z)\), independently of \(\mu_t\).
A schedule is an admissible \(p\) and a measurable \(\theta:[0,1]\to T\) with \(\operatorname{Leb}(\theta^{-1}(t))=\mu_t\). At factor \(\rho\ge0\), it must satisfy \(f_{\theta(z)}(X_p(z))p(z)\ge\rho q_{\theta(z)}\) almost everywhere. A zero benchmark imposes no positive utility requirement.
The decision problem asks whether a schedule exists at \(\rho=1\); its threshold version takes a binary-rational \(\rho\ge0\) as input. The optimization value is \(\rho^*=\sup\{\rho\ge0:\text{a schedule exists at factor }\rho\}\), allowing \(+\infty\) and distinguishing a finite attained optimum from an unattained supremum.
A finite schedule encoding consists of rational boundaries partitioning the population interval, a type and a nonnegative rational constant profile on each interval, and the resulting affine position maps and unused suffix; intervals may be refined at resource-cell crossings. Feasibility is defined over all measurable schedules, without assuming that such finite representatives exist.

Is continuous MMS feasibility in \(\mathrm P\) or NP-hard, and is exact optimization of \(\rho^*\), including attainment and finite schedule representation, polynomial-time solvable or NP-hard? State running times in \(m\), \(\tau\), \(L\), and the threshold bit length when applicable.

For finitely many agents, connected separated MMS-fair allocations exist and can be computed in polynomial time with explicit rational piecewise-constant densities; individual MMS values are also exactly computable in polynomial time. [Verified source](https://arxiv.org/pdf/2012.06682).
No result settling this exact population-mass model was identified in the literature search.

Partial resolution

Feasibility at factor $1$ is in $\mathrm P$: every valid input is feasible. The general threshold and compact exact-value complexity classifications remain unresolved here.

The following additional results are proved below:

• Every finite optimum is attained.
• Exact threshold feasibility takes

$$ m^{O(\tau)}\operatorname{poly}(m,\tau,L+B) $$
bit operations, where $B$ is the threshold bit length. Thus it is polynomial-time solvable for fixed support size.

• A finite optimum has algebraic degree at most

$$ m\prod_{t:q_t>0}\deg P_t\le m^{\tau+1}, $$
for explicitly constructed benchmark polynomials $P_t$.

• Even with two cells and exclusively dyadic input, the exact optimum can have algebraic degree $2^{\tau-1}$ while the input length is polynomial in $\tau$. Consequently, dense polynomial output for the exact value cannot always be produced in polynomial time.
• The stipulated rational schedule representation need not exist, even for one type at factor $1$.
• General rational-threshold feasibility is square-root-sum-hard under the convention that rational numerators and denominators are encoded in binary.
• Exact algebraic values and attaining algebraic schedules can be constructed with explicit exponential bounds. The schedule construction below uses linear-program bases and Cramer’s rule, repairing the witness-construction gap identified in the verifier report.

Throughout, “binary-rational” means a rational numerator and denominator encoded in binary. All results except the stated square-root-sum reduction also apply when inputs are restricted to dyadic rationals.

1. Individual benchmarks

Let the common refinement be
$$ 0=b_0<b_1<\cdots<b_m=1, $$
with cell lengths $d_j=b_j-b_{j-1}$ and density heights $h_{tj}$.

For type $t$, let $r_t$ be the number of cells in its initial consecutive positive-density run, and put
$$ \ell_t=\sum_{j=1}^{r_t}d_j. $$
An empty initial run has $\ell_t=0$.

Proposition. If $\ell_t\le\sigma$, then $q_t=0$. Otherwise $q_t$ is the unique positive solution of
$$ F_t(Q)=\sum_{j=1}^{r_t}\frac{d_jh_{tj}}{\sigma h_{tj}+Q}=1. $$
This positive benchmark is attained.

Proof. Every admissible position map is absolutely continuous, with
$$ X_p'(z)=p(z)+\sigma\ge\sigma $$
almost everywhere. Hence it is continuous and strictly increasing. Breakpoint preimages have measure zero.

Suppose a profile gives homogeneous utility at least $v>0$. It cannot traverse a positive-length zero-density cell: its population preimage would be a nondegenerate interval on which the utility requirement fails. Therefore $X_p(1)\le\ell_t$.

On a positive cell of height $h$, the utility requirement implies
$$ p\ge\frac vh, \qquad \frac{h}{\sigma h+v}(p+\sigma)\ge1. $$
Integration, separately over the population preimages of the cells, gives
$$ 1\le \int_0^{X_p(1)}\frac{f_t(x)}{\sigma f_t(x)+v}\,dx \le F_t(v). $$
The change of variables follows from absolute continuity: on each cell preimage, the integral of $X_p'$ equals the traversed resource length.

The function $F_t$ is continuous and strictly decreasing on positive arguments, tends to zero at infinity, and satisfies
$$ F_t(0)=\frac{\ell_t}{\sigma}. $$
Thus, if $\ell_t\le\sigma$, no positive target is feasible.

If $\ell_t>\sigma$, there is a unique positive root $q$ of $F_t(q)=1$. Assign population length
$$ w_{tj}=\frac{d_j}{\sigma+q/h_{tj}} $$
to each initial positive cell, using profile $p=q/h_{tj}$. These population lengths sum to one, each block traverses its cell exactly, and utility equals $q$. Every larger target violates the necessary bound above. Hence $q_t=q$. $\square$

Clearing denominators produces
$$ P_t(Q)= \sum_{j=1}^{r_t}d_jh_{tj} \prod_{\substack{i=1\\i\ne j}}^{r_t}(\sigma h_{ti}+Q) - \prod_{i=1}^{r_t}(\sigma h_{ti}+Q). $$
After clearing rational coefficient denominators and changing its sign if necessary, this is an integer polynomial with positive leading coefficient, degree at most $m$, and coefficient bit length
$$ H=O\bigl(m(L+\log(m+1))\bigr). $$
This bound follows by expanding products of at most $m$ input factors and clearing their rational denominators.

There are no positive extraneous roots, since every cleared denominator is positive there. Moreover,
$$ F_t(1) < \sum_{j=1}^{r_t}d_jh_{tj} \le1, $$
so every positive benchmark lies in $(0,1)$. Thus the polynomial together with the isolating interval $(0,1)$ already gives an exact benchmark encoding.

All benchmarks can therefore be encoded in
$$ \tau\,\operatorname{poly}(m,L) $$
bit operations. Approximating them to $k$ binary places also takes polynomial time in $m,\tau,L+k$: bisect $(0,1)$ and compare the rational value $F_t(Q)$ with one.

2. Exact finite-dimensional characterization

Fix $\rho>0$. A type-cell pair is allowed when either $q_t=0$ or $h_{tj}>0$. Let $K$ be the number of cells before the first cell having no allowed type; put $K=m$ if no such cell exists.

For an allowed pair, define
$$ c_{tj}(\rho)= \begin{cases} \sigma,&q_t=0,\\ \sigma+\rho q_t/h_{tj},&q_t>0. \end{cases} $$

Consider the system
$$ y_{tj}\ge0, $$
$$ \sum_{\substack{j\le K\\(t,j)\text{ allowed}}}y_{tj}=\mu_t \quad(t\in T), $$
$$ \sum_{\substack{t\\(t,j)\text{ allowed}}} c_{tj}(\rho)y_{tj}\le d_j \quad(j\le K). $$

Proposition. A measurable schedule exists at factor $\rho$ if and only if this system is feasible.

Necessity

Given a schedule, put
$$ G_{tj}=\{z:X_p(z)\in(b_{j-1},b_j),\ \theta(z)=t\}, \qquad y_{tj}=\operatorname{Leb}(G_{tj}). $$
Forbidden pairs have zero mass. A cell having no allowed type cannot be entered through a positive resource length: its population preimage would have positive measure, but its intersection with every type population would have measure zero. Consequently, $X_p(1)\le b_K$.

All population except finitely many breakpoint preimages is accounted for by the sets $G_{tj}$, giving the type equations. On an allowed pair, $p+\sigma\ge c_{tj}(\rho)$ almost everywhere, whence
$$ \sum_t c_{tj}(\rho)y_{tj} \le \sum_t\int_{G_{tj}}(p+\sigma)\,dz \le d_j. $$

Sufficiency and empty-cell repair

Let $y$ satisfy the system. Originally empty cells require repair, since a positive resource interval cannot be traversed instantaneously.

For each originally empty cell $j$, choose an allowed type $t(j)$. Its positive mass supplies an original donor entry
$$ y_{t(j),i(j)}>0. $$
Move from that donor to cell $j$ the amount
$$ \delta_j= \frac{d_jy_{t(j),i(j)}} {2m\bigl(d_j+c_{t(j),j}(\rho)y_{t(j),i(j)}\bigr)}. $$
It satisfies
$$ 0<\delta_j\le \frac{y_{t(j),i(j)}}{2m}, \qquad c_{t(j),j}(\rho)\delta_j\le\frac{d_j}{2m}. $$
At most $m$ transfers charge any donor entry, so every original positive entry retains at least half its mass. Donor capacities decrease, recipient capacities hold, and type totals are preserved.

Write the repaired vector as $\widehat y$. Every cell is now occupied. Start with block lengths
$$ a_{tj}=c_{tj}(\rho)\widehat y_{tj}. $$
Give the remaining length of each cell to any one of its positive-mass entries. Then
$$ \sum_t a_{tj}=d_j, \qquad a_{tj}\ge c_{tj}(\rho)\widehat y_{tj}. $$
Omit every zero-mass entry. For each remaining block, use population length $\widehat y_{tj}$ and constant profile
$$ p_{tj}=\frac{a_{tj}}{\widehat y_{tj}}-\sigma. $$
This is nonnegative and meets the required utility inequality. Concatenate the blocks in cell order. Their population lengths sum to one, their resource lengths sum to $b_K$, and the unused suffix is $[b_K,1]$.

The resulting schedule has at most $m\tau$ blocks. Its finite profile is integrable and admissible. $\square$

This proves finite real representability from measurable feasibility, rather than assuming it.

3. Every society is feasible at factor one

For each positive-benchmark type, take the homogeneous attaining profile from Section 1. For a zero-benchmark type, take $p=0$, ending at position $\sigma$.

Let $w_{tj}$ be the population mass and $D_{tj}$ the resource length of this homogeneous schedule in cell $j$. Then
$$ \sum_j w_{tj}=1, \qquad D_{tj}=c_{tj}(1)w_{tj}, \qquad 0\le D_{tj}\le d_j. $$
These schedules remain within the accessible prefix. Indeed, a positive-benchmark schedule traverses only its initial positive-density run. If a zero benchmark exists, every cell has an allowed type.

Set
$$ y_{tj}=\mu_t w_{tj}. $$
The type equations hold, and each capacity satisfies
$$ \sum_t c_{tj}(1)y_{tj} =\sum_t\mu_tD_{tj} \le d_j\sum_t\mu_t=d_j. $$
Section 2 constructs the required schedule.

Therefore every valid input answers YES at factor $1$, and every factor in $[0,1]$ is feasible. On the promised valid-input domain, the decision takes constant time; reading, validation, and refinement take $\operatorname{poly}(m,\tau,L)$ time.

The same construction gives a polynomial-size description by arithmetic expressions in the individually encoded benchmarks. Rational coefficients, however, are not guaranteed.

4. Unboundedness and attainment

Let
$$ H_t=\max_j h_{tj}, \qquad A=\sum_t\frac{\mu_tq_t}{H_t}. $$
Normalization ensures $H_t>0$.

Every feasible factor satisfies
$$ \int_0^1p(z)\,dz \ge \rho\sum_t\frac{\mu_tq_t}{H_t} =\rho A. $$
Admissibility gives $\int p\le1-\sigma$. Hence, if any benchmark is positive,
$$ 1\le\rho^*\le\frac{1-\sigma}{A}<+\infty. $$
If all benchmarks are zero, $p=0$ works at every finite factor, so $\rho^*=+\infty$.

Suppose now that $\rho^*$ is finite. Choose positive feasible factors $\rho_n\to\rho^*$ and corresponding cell vectors $y^{(n)}$. Each coordinate is bounded by its type mass. A subsequence converges to $y^*$.

The allowed pairs and accessible prefix are independent of the positive factor. Nonnegativity and type equations are closed, and
$$ c_{tj}(\rho_n)y_{tj}^{(n)} \longrightarrow c_{tj}(\rho^*)y_{tj}^*. $$
Thus all capacity inequalities survive the limit. Section 2 constructs an attaining schedule.

Consequently, the feasible-factor set is either $[0,+\infty)$ or $[0,\rho^*]$ with a finite attained endpoint. A finite unattained supremum cannot occur.

5. A degree bound for the optimum

Let
$$ \mathbb K=\mathbb Q(q_t:t\in T). $$
For positive benchmarks, put $d_t=\deg P_t$, and define
$$ D_0=\prod_{t:q_t>0}d_t, $$
with empty product one. Successively adjoining the benchmarks gives
$$ [\mathbb K:\mathbb Q]\le D_0\le m^\tau. $$

Introduce one nonnegative slack variable per capacity constraint. The cell system becomes
$$ A(R)x=b,\qquad x\ge0. $$
There are $r=\tau+K$ rows and at most $m\tau+K$ columns. The matrix has full row rank: slack columns isolate the cell rows, and population columns then isolate the type rows.

For any basis $B$, Cramer’s rule gives
$$ x_{B,i}(R)=\frac{E_{B,i}(R)}{\Delta_B(R)}, \qquad \Delta_B(R)=\det A_B(R). $$
Only the $K$ cell rows depend on $R$, each affinely. Therefore
$$ \deg_R\Delta_B\le K, \qquad \deg_R E_{B,i}\le K. $$

At $\rho^*$ the feasible polytope is nonempty and bounded: population coordinates are bounded by type masses, and slack coordinates by cell lengths. It therefore has a feasible basic solution.

Take its basis $B$, so $\Delta_B(\rho^*)\ne0$. If every basic coordinate vanishing there had an identically zero numerator, all positive coordinates would remain positive in a sufficiently small neighborhood, and identically zero coordinates would stay zero. This would extend feasibility above $\rho^*$, a contradiction.

Thus some nonzero polynomial $E_{B,i}$ vanishes at $\rho^*$. It has degree at most $K$, proving
$$ [\mathbb K(\rho^*):\mathbb K]\le K. $$
In particular,
$$ [\mathbb Q(\rho^*):\mathbb Q] \le K D_0 \le m^{\tau+1}. $$

6. Exact threshold decision in polynomial time for fixed support

The argument here supplies an exact bit algorithm, including equality cases.

A capacity-violation linear program

Fix rational $\rho>0$, of bit length $B$. Let $\mathcal A$ be the compact assignment polytope defined by nonnegativity and the type equations, using only allowed pairs in the accessible prefix. Every type has an allowed first-cell pair, so $\mathcal A$ is nonempty.

Define
$$ v= \min_{y\in\mathcal A} \max\left\{ 0,\ \max_{j\le K} \left(\sum_t c_{tj}(\rho)y_{tj}-d_j\right) \right\}. $$
By Section 2, threshold feasibility is equivalent to $v=0$.

This is a linear program after introducing $w$ with
$$ w\ge0,\qquad w\ge\sum_t c_{tj}(\rho)y_{tj}-d_j. $$
Its optimal face, with $w=v$, is nonempty and compact. A vertex of that face is also a vertex of the feasible polyhedron. At such a vertex, active constraint rows span the full variable space; otherwise a sufficiently small perturbation in both directions along a common null vector would preserve feasibility.

Hence Cramer’s rule expresses $v$ as a ratio
$$ v=\frac{E(q)}{F(q)}, \qquad F(q)\ne0. $$
The numerator and denominator are integer polynomials after clearing rational coefficients. Their benchmark degree is at most $K\le m$, because benchmark coefficients occur only in cell rows.

An explicit positive-gap bound

Let $n$ be the number of variables, including $w$, so $n\le m\tau+1$. Clear all rational coefficients in the constraint system by one positive common denominator. Let $H_0$ bound the bit lengths of the resulting integer coefficients. It is computable with
$$ H_0=\operatorname{poly}(m,\tau,L+B). $$

Use the benchmark coefficient bound $H$ from Section 1. Every conjugate of a benchmark has modulus at most $2^{H+1}$, by the Cauchy root bound.

Let $a_t$ be the positive leading coefficient of $P_t$. The number $a_tq_t$ is an algebraic integer: substituting $Z=a_tQ$ into $P_t$ and multiplying by $a_t^{d_t-1}$ gives a monic integer polynomial in $Z$. Put
$$ U=\prod_{t:q_t>0}a_t, \qquad U\le2^{\tau H}. $$
Because $E$ has total benchmark degree at most $m$, the number
$$ \beta=U^mE(q) $$
is an algebraic integer.

For every embedding of $\mathbb K$ into $\mathbb C$, determinant expansion gives
$$ |E(q)|,\ |F(q)|\le2^V, $$
where one may take
$$ V=n\bigl(H_0+H+2+\lceil\log_2(n+1)\rceil\bigr). $$
Indeed, each matrix entry has modulus at most $2^{H_0+H+2}$, and there are at most $n!$ determinant terms.

Set
$$ Z=m\tau H+V+2. $$
Every conjugate of $\beta$ has modulus at most $2^Z$.

If $v>0$, then $\beta\ne0$. The field norm of a nonzero algebraic integer is a nonzero integer. Thus
$$ 1\le \left|N_{\mathbb K/\mathbb Q}(\beta)\right|, $$
and, bounding every factor except the distinguished one,
$$ |\beta|\ge2^{-Z([\mathbb K:\mathbb Q]-1)}. $$
Combining this with $U^m\le2^{m\tau H}$ and $|F(q)|\le2^V$ yields
$$ v\ge2^{-ZD_0}. $$
Therefore
$$ v=0 \quad\text{or}\quad v\ge g, \qquad g:=2^{-ZD_0}. $$

The algebraic-integer facts used here are closure under addition and multiplication, and the norm formula as the product over field embeddings. Their hypotheses hold for $\beta$ by the explicit denominator clearing above.

Rational approximation decides exactly

Approximate every coefficient $c_{tj}(\rho)$ by a rational coefficient within $\varepsilon=g/8$. This requires
$$ ZD_0+\operatorname{poly}(L+B) $$
binary places of benchmark precision.

Let $\widehat v$ be the exact optimum of the resulting rational linear program. For every $y\in\mathcal A$,
$$ \sum_t y_{tj}\le1. $$
Therefore each cell-load error is at most $\varepsilon$. Taking a maximum and then a minimum preserves that error bound:
$$ |\widehat v-v|\le\varepsilon. $$
Consequently,
$$ v=0\implies\widehat v\le g/8, $$
whereas
$$ v>0\implies\widehat v\ge7g/8. $$
Comparing $\widehat v$ with $g/2$ decides the original threshold exactly.

Rational linear programming is polynomial-time solvable in its dimensions and coefficient bit lengths. Benchmark bisection also has polynomial bit complexity in the requested precision. Since $D_0\le m^\tau$, the resulting running time is
$$ m^{O(\tau)}\operatorname{poly}(m,\tau,L+B). $$
The case $\rho=0$ answers YES immediately.

7. Rational finite schedule encoding can fail

Take one type, mass one, with $\sigma=1/2$ and density heights $1/2$ and $3/2$ on the two half-cells. All inputs are dyadic.

Its benchmark equation is
$$ \frac1{1+4q}+\frac3{3+4q}=1, $$
giving
$$ q=\frac{\sqrt3}{4}. $$
With one type, the definition of its benchmark prohibits any feasible factor above one. Benchmark attainment proves that $\rho^*=1$.

For any schedule at factor one, define
$$ c(x)=\frac1{\sigma+q/f(x)}. $$
The utility inequality and cellwise change of variables give
$$ 1 \le \int_0^1c(X_p(z))(p(z)+\sigma)\,dz = \int_0^{X_p(1)}c(x)\,dx \le \int_0^1c(x)\,dx =1. $$
Every inequality is therefore equality. Positivity of $c$ forces $X_p(1)=1$. The first integrand is at least one almost everywhere, so equality of its integral forces
$$ p(z)=\frac{q}{f(X_p(z))} $$
almost everywhere.

The profile must consequently equal
$$ \frac{\sqrt3}{2} \quad\text{on the first cell preimage}, \qquad \frac{\sqrt3}{6} \quad\text{on the second}. $$
Both preimages have positive population measure. A finite profile with rational constants cannot have these required values.

Thus a universal algorithm producing the stipulated rational schedule encoding cannot exist—even for factor-one feasibility.

8. A two-cell formula and square-root-sum hardness

Consider two half-cells, $\sigma=1/2$, and a uniform type of mass $1/2$. Other types have total mass $1/2$ and heights
$$ 0<h_i^-<h_i^+, \qquad h_i^-+h_i^+=2. $$
Their benchmark equation gives
$$ q_i^2=\frac{h_i^-h_i^+}{4}. $$
Define
$$ a_i=\frac{q_i}{h_i^+} =\frac12\sqrt{\frac{h_i^-}{h_i^+}}<\frac12, \qquad W=\sum_i\mu_i a_i<\frac14. $$

Two-cell formula.
$$ \rho^*=\frac{1/2}{1/4+W}. $$

The maximum-height bound proves the upper bound. Write the displayed value as $R$, so $1<R<2$. At factor $R$, give the uniform type profile $R/2$, and type $i$ profile $Ra_i$ entirely in the second cell.

Their resource lengths are
$$ U=\frac{1+R}{4}>\frac12, \qquad V=\frac14+RW<\frac12, \qquad U+V=1. $$
Use uniform population mass $1/(1+R)$ to traverse the first half-cell. Then place all other types in the second cell, followed by the remaining uniform population. The schedule ends at one and gives every type its required utility. This proves the formula.

Now take a square-root-sum instance consisting of positive integers $a_1,\ldots,a_n$ and a nonnegative integer $b$. Choose a power of two $C>\sqrt{\max_i a_i}$, and set
$$ r_i=\frac{a_i}{C^2}, \qquad h_i^-=\frac{2r_i}{1+r_i}, \qquad h_i^+=\frac2{1+r_i}, \qquad \mu_i=\frac1{2n}. $$
The uniform type has mass $1/2$. These are positive normalized rational densities, with polynomial encoding length. Their benchmarks satisfy
$$ q_i=\frac{\sqrt{r_i}}{1+r_i}, \qquad \frac{q_i}{h_i^+}=\frac{\sqrt{a_i}}{2C}. $$
Thus the two-cell formula gives
$$ \rho^*= \frac{2nC}{nC+\sum_i\sqrt{a_i}}. $$
For the rational threshold
$$ \rho_b=\frac{2nC}{nC+b}, $$
we obtain
$$ \rho_b\text{ feasible} \iff \sum_i\sqrt{a_i}\le b. $$

This is a polynomial-time many-one reduction with $m=2$ and support size at most $n+1$. It proves square-root-sum hardness under general rational encoding. It supplies neither a polynomial-time algorithm nor an $\mathrm{NP}$-hardness proof. The cited square-root-sum literature identifies its polynomial-time exact comparison as an open problem. [Eisenbrand, Haeberle, and Singer](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54)

9. Exponential algebraic degree with dyadic input

The following obstruction applies even under the stricter dyadic reading.

Let $n\ge8$ be a power of two. Choose $n$ distinct odd primes
$$ r_1,\ldots,r_n\le2n^3. $$
Such primes exist, and can be found by a polynomial-time sieve. For completeness, the elementary bound
$$ \binom{2N}{N}\ge\frac{4^N}{2N+1}, \qquad \binom{2N}{N}\le(2N)^{\pi(2N)} $$
implies
$$ \pi(2N)\ge \frac{N\log4-\log(2N+1)}{\log(2N)}. $$
The upper bound follows because, for each prime, every summand in its factorial-valuation difference is zero or one, so its contribution to the binomial coefficient is at most $2N$. Taking $N=n^3$ gives $\pi(2n^3)>n+1$ for $n\ge8$: use $\log4>1$, $\log(2n^3+1)<3n$, $\log(2n^3)<3n$, and $n^2>3n+6$.

Put
$$ M_i=2^{r_i}-1. $$
Use the two-cell society of Section 8, with
$$ h_i^-=2^{-(r_i-1)}, \qquad h_i^+=2-2^{-(r_i-1)}, \qquad \mu_i=\frac1{2n}. $$
All inputs are dyadic, and their total bit length is $O(n^4)$. The heights satisfy
$$ q_i=\frac{\sqrt{M_i}}{2^{r_i}}, \qquad \frac{q_i}{h_i^+}=\frac1{2\sqrt{M_i}}. $$
Therefore
$$ \rho^*= \frac{2n}{n+\sum_{i=1}^n1/\sqrt{M_i}}. $$

Independence of the square classes

The identity
$$ \gcd(2^r-1,2^s-1)=2^{\gcd(r,s)}-1 $$
follows by applying the Euclidean algorithm to the exponents. Hence the $M_i$ are pairwise coprime.

Each $r_i$ is odd and at least three, so $M_i$ is congruent to seven modulo eight and is not a square. Each therefore has a prime divisor occurring to an odd exponent; pairwise coprimality makes that prime absent from every other $M_j$. Consequently, no nonempty product of the $M_i$ is a rational square.

It follows that
$$ \mathbb F=\mathbb Q(\sqrt{M_1},\ldots,\sqrt{M_n}) $$
has degree $2^n$, with all independent sign changes as automorphisms. Here is an induction proof of the needed fact.

Suppose the first $k-1$ square roots give a field with the expected monomial basis and sign changes. If $M_k$ were a square in that field, a square root $\alpha$ would satisfy $g(\alpha)=\pm\alpha$ under every sign change. Expanding $\alpha$ in the monomial basis shows it must be a rational multiple of one basis monomial: the independent sign characters distinguish all monomials. Squaring would express $M_k$ as a rational square times a product of earlier $M_i$, contradicting the odd valuation at a prime unique to $M_k$. Thus adjoining $\sqrt{M_k}$ doubles the degree. Existing sign changes extend while fixing the new root, and its own sign change supplies the additional automorphism.

Now put
$$ S=\sum_i\frac1{\sqrt{M_i}} =\sum_i\frac{\sqrt{M_i}}{M_i}. $$
No nonidentity sign change fixes $S$, since the individual square-root monomials are linearly independent and all their coefficients here are nonzero. Hence $S$ has $2^n$ distinct conjugates and degree $2^n$.

Finally,
$$ \rho^*=\frac{2n}{n+S}, \qquad S=\frac{2n}{\rho^*}-n, $$
so $\mathbb Q(\rho^*)=\mathbb Q(S)$. Therefore
$$ \deg_{\mathbb Q}\rho^*=2^n=2^{\tau-1}. $$

Any nonzero rational polynomial defining this optimum has degree at least $2^n$. A dense coefficient-list encoding therefore has superpolynomial output length relative to the input length $O(n^4)$.

There is a corresponding schedule obstruction. At the optimum, the maximum-height resource bound is equality. The nonnegative difference between the profile and its type-specific lower bound must integrate to zero, so the uniform type must receive
$$ p=\rho^*/2 $$
almost everywhere. Thus any finite algebraic schedule represented by dense defining polynomials also requires a coefficient of degree $2^n$.

These are unconditional output-size lower bounds for the specified dense algebraic encoding. They do not classify computation in a compact expression encoding.

10. Exact optimization and algebraic witness construction

This section specifies an exact upper bound and its output encoding.

Put
$$ S_0=m+\tau+2. $$

The elimination theorem used

The one-block specialization of Basu’s Theorem 2.18 eliminates $k$ existential variables with at most one free variable, using $s$ integer polynomials of degree at most $d$ and coefficient bit length $H$, in
$$ (sd)^{O(k+1)}\operatorname{poly}(H) $$
bit time. Output degrees are at most $d^{O(k+1)}$, and intermediate coefficient bit lengths at most $H d^{O(k+1)}$. [Basu, Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf)

For univariate root isolation, a square-free degree-$d$ integer polynomial with coefficient bit length $H$ has all real roots isolated in
$$ \widetilde O(d^3+d^2H) $$
bit operations. Taking square-free parts also has polynomial bit complexity. [Sagraloff–Mehlhorn, Theorem 2](https://arxiv.org/pdf/1308.4088)

Eliminating benchmark variables after basis enumeration

Use the standard-form matrix from Section 5. It has $r=\tau+K$ rows and $v+K$ columns, where $v\le m\tau$ is the number of allowed population variables. There are at most
$$ \binom{v+K}{r}\le S_0^{O(m+\tau)} $$
bases.

Replace positive benchmarks by variables $Q_t$. For each basis $B$, form its determinant $\Delta_B(Q,R)$ and Cramer numerators $E_{B,i}(Q,R)$. The basis is feasible precisely when
$$ \Delta_B(Q,R)\ne0, \qquad \Delta_B(Q,R)E_{B,i}(Q,R)\ge0 $$
for every basic coordinate.

The signs are correct because
$$ E_{B,i}/\Delta_B\ge0 \iff E_{B,i}\Delta_B\ge0. $$
Nonbasic coordinates are zero, and the basis equations automatically enforce all standard-form equalities.

Add
$$ P_t(Q_t)=0,\qquad Q_t>0 $$
for every positive benchmark, and $R>0$. These benchmark conditions identify exactly the intended roots.

Only $K$ matrix rows contain benchmark or factor variables. Consequently, determinants and numerators have total degree at most $2K$, and the sign products degree at most $4K$. Each basis formula has $O(m+\tau)$ polynomials, degree $O(m)$, coefficient bit lengths polynomial in $m,\tau,L$, and at most $\tau$ quantified variables.

Eliminating those benchmark variables, separately for every basis, and taking the union gives a univariate description of feasible positive factors in
$$ S_0^{O(m+\tau)}\operatorname{poly}(L) $$
bit time.

When some benchmark is positive, Section 4 proves that this set is $(0,\rho^*]$. Its finite endpoint must be a root of a nonconstant output polynomial: otherwise all relevant polynomial signs would be locally constant there. Univariate root isolation and evaluation on rational interval samples identify the endpoint exactly, within the same running-time bound.

An explicit algebraic schedule encoding

Use the following extended encoding:

• Each positive benchmark is specified by its integer polynomial and isolating interval.
• The finite optimum is specified by an integer polynomial $G$ and a rational interval containing exactly that root.
• Schedule coordinates are finite arithmetic-expression graphs, using rational constants, these specified roots, and the operations of addition, subtraction, multiplication, and division by certified nonzero quantities.

This encoding defines each number uniquely. It is an algebraic extension of the question’s rational encoding.

To select a feasible basis at the optimum, test the corresponding formula together with
$$ G(R)=0,\qquad R\in I. $$
There are at most $\tau+1$ quantified variables. The polynomial $G$ has degree $S_0^{O(\tau)}$ and coefficient bit length $S_0^{O(\tau)}\operatorname{poly}(L)$ by the elimination bounds above. Thus all basis tests take, in total,
$$ S_0^{O(m+\tau^2)}\operatorname{poly}(L) $$
bit operations.

A feasible basis exists because the attained feasible polytope is nonempty and bounded. Its Cramer expressions give the exact vector. Additional sign tests identify its positive coordinates, allowing selection of occupied blocks and donor entries.

Apply the explicit repair from Section 2. Its formulas require only arithmetic operations with positive denominators; no witness-sampling theorem is needed. Distribute the unused cell lengths to selected positive entries, omit zero entries, and form the constant profiles and cumulative population boundaries.

The output has at most $m\tau$ blocks. Expanded Cramer polynomials have degree $O(m)$ in at most $\tau+1$ variables, hence at most $S_0^{O(\tau)}$ coefficients; the subsequent expression graph has polynomially many arithmetic operations. Including root encodings, its output size is bounded by the stated construction time.

For a rational threshold instead of an optimum, the same basis construction takes
$$ S_0^{O(m+\tau)}\operatorname{poly}(L+B) $$
time.

11. What is settled and what remains open

The proved running times are:

| Task | Bit-time bound |
|---|---:|
| Factor-one decision on valid inputs | Constant time |
| Input validation and common refinement | $\operatorname{poly}(m,\tau,L)$ |
| Exact individual benchmark encodings | $\tau\,\operatorname{poly}(m,L)$ |
| Exact rational-threshold decision | $m^{O(\tau)}\operatorname{poly}(m,\tau,L+B)$ |
| Exact finite optimum in polynomial-and-interval encoding | $(m+\tau+2)^{O(m+\tau)}\operatorname{poly}(L)$ |
| Algebraic schedule at a rational threshold | $(m+\tau+2)^{O(m+\tau)}\operatorname{poly}(L+B)$ |
| Algebraic schedule attaining the finite optimum | $(m+\tau+2)^{O(m+\tau^2)}\operatorname{poly}(L)$ |

The unbounded case is detected in polynomial time by checking whether every initial positive-density run has length at most $\sigma$.

Thus factor-one decision, finite attainment, and the failure of universal rational schedule output are settled. Threshold decision is polynomial for fixed support size. Dense algebraic exact-value output has an unconditional superpolynomial size obstruction.

What remains unresolved is whether unrestricted threshold decision is in $\mathrm P$ or is $\mathrm{NP}$-hard, and the corresponding classification of exact value computation in a compact representation supporting exact rational comparison. Square-root-sum hardness alone does not settle either classification.

⟨structured verdict parsed — rendered above⟩

Verification report

Overall assessment: partial resolution, with substantial correct results. The argument establishes factor-one feasibility, finite attainment, exact threshold decision for fixed support size, representation obstructions, and exponential-time algebraic constructions. It does not settle the requested unrestricted threshold or exact optimization complexity classifications.

I found no false central mathematical step. The principal blocking issue is incomplete coverage of USER_TASK, which the prover explicitly acknowledges.

1. Individual benchmarks

Verified.

The inequality $X_p'\ge\sigma>0$ makes $X_p$ continuous and strictly increasing. Consequently, breakpoint preimages have measure zero, and traversing a positive-length resource cell requires positive population mass.

For a positive homogeneous target $v$, traversing a zero-density cell is impossible. Thus restricting the necessary integral bound to the initial positive-density run is justified, including when that run is empty.

On a positive-density cell, the displayed inequality follows correctly from $p\ge v/h$. Cellwise integration yields
$$ 1\le F_t(v). $$
The monotonicity, continuity, endpoint value, and limiting behavior of $F_t$ are correct. These establish the zero-benchmark criterion and uniqueness of the positive root.

The proposed attaining profile traverses each initial positive cell exactly, has total population length one, and satisfies the utility requirement. It therefore establishes the benchmark as a maximum when positive.

The denominator-clearing polynomial has the stated degree bound. Its denominators cannot introduce positive extraneous roots. The calculation $F_t(1)<1$ correctly places the unique positive root in $(0,1)$.

The polynomial coefficient and benchmark approximation bounds are adequate. Exact equality during bisection can be detected by rational arithmetic.

2. Finite-dimensional characterization

Verified in both directions.

Necessity

The type-cell sets account for all population outside finitely many breakpoint preimages. Forbidden pairs have zero mass.

The inaccessible-cell argument is sound: entering a positive length of a cell without any allowed type would create a positive-measure population interval on which no type could satisfy its requirement.

Integrating $p+\sigma\ge c_{tj}(\rho)$ over the measurable type-cell sets gives the capacity inequalities. This does not require those sets to be intervals.

Sufficiency

The empty-cell repair is valid:

• An allowed type has positive prescribed mass and therefore an original positive donor entry.
• Each transfer is positive and consumes at most its stated share of donor mass and recipient capacity.
• Even if several empty cells use the same donor, total withdrawal is at most half the original donor mass.
• Originally occupied cells remain occupied.
• Type totals and capacity inequalities survive.

After repair, every cell has an entry to receive its residual resource length. For every retained block,
$$ p_{tj}=\frac{a_{tj}}{\widehat y_{tj}}-\sigma\ge0, $$
and the utility inequality follows from the definition of $c_{tj}(\rho)$.

The concatenation has population length one, ends at $b_K\le1$, and has finitely many finite constant profiles. Thus measurable feasibility really does imply finite real representability.

The argument does not assert rational representability; that distinction is essential and is respected.

3. Factor-one feasibility

Verified.

Each homogeneous benchmark schedule provides
$$ D_{tj}=c_{tj}(1)w_{tj},\qquad D_{tj}\le d_j. $$
For a zero benchmark, the proposed profile $p=0$ supplies the same identity on its traversed cells.

The accessible-prefix justification is correct. A positive-benchmark type uses only its initial positive run; a zero-benchmark type makes every cell allowed.

The weighted construction $y_{tj}=\mu_tw_{tj}$ preserves type totals and satisfies every capacity constraint because $\sum_t\mu_t=1$. Section 2 then supplies a schedule.

Thus the conclusion that every valid input is feasible at factor one is established. Constant-time decision applies only to the promised valid-input domain, as the prover states; validation and refinement require polynomial time.

The polynomial-size arithmetic-expression description is also consistent with the explicit repair formulas.

4. Unboundedness and attainment

Verified.

Normalization guarantees $H_t>0$, including for zero-benchmark types. The maximum-height bound gives
$$ \rho A\le1-\sigma. $$
Hence a positive benchmark makes the optimum finite. If all benchmarks vanish, $p=0$ satisfies every finite factor.

For a finite optimum, the cell vectors lie in a bounded finite-dimensional set. The allowed pairs and accessible prefix remain fixed for positive factors, so the limiting argument preserves all constraints.

Since factor one is feasible, the finite endpoint is positive. Section 2 therefore applies at that endpoint and constructs an attaining schedule.

The exclusion of a finite unattained supremum is established.

5. Algebraic degree bound

Verified.

Successive field adjunction gives
$$ [\mathbb K:\mathbb Q]\le D_0. $$
The standard-form matrix has full row rank: slack columns isolate cell-row coefficients, and allowed population columns then isolate type-row coefficients. Every type has an allowed first-cell pair.

The determinant and Cramer numerator degrees in $R$ are at most $K$, since only the cell rows depend on $R$.

The feasible standard-form polytope at the finite optimum is nonempty and bounded, so a feasible basic solution exists. Its basis determinant is nonzero there.

The local continuation argument is correct: unless a nonzero basic-coordinate numerator vanishes at the optimum, the same basis remains feasible just above it. This contradicts maximality.

Thus the claimed degree bound follows. It is an upper bound on the algebraic degree, not a polynomial-time exact optimization result.

6. Exact rational-threshold algorithm

Verified, including equality cases.

The assignment polytope is compact and nonempty. Introducing $w$ correctly turns maximum capacity violation into a linear program, with feasibility equivalent to $v=0$.

The optimal face is compact. Its vertices are vertices of the feasible polyhedron, and the active-row argument justifies a Cramer representation of $v$.

Only capacity rows contain benchmark coefficients, so the numerator and denominator have benchmark degree at most $K$.

The algebraic-integer construction and norm argument are valid. Reducibility of the benchmark polynomials causes no problem: the selected roots remain algebraic, their conjugates obey the root bound, and the field-degree estimate remains an upper bound.

The determinant magnitude estimate accommodates denominator clearing and all embeddings. The resulting positive-gap bound is conservative but sufficient:
$$ v=0\quad\text{or}\quad v\ge2^{-ZD_0}. $$

The perturbation estimate correctly uses
$$ \sum_t y_{tj}\le1 $$
to avoid an additional support-size error factor. Therefore the rational linear program distinguishes zero from positive violation even at an exact equality threshold.

The running time
$$ m^{O(\tau)}\operatorname{poly}(m,\tau,L+B) $$
follows. This proves polynomial time for fixed support size, not polynomial time for unrestricted support size.

7. Failure of rational schedule encoding

Verified.

The two-cell benchmark equation gives
$$ q=\frac{\sqrt3}{4}. $$
For one type, no factor above one can be feasible by the benchmark definition, while benchmark attainment gives feasibility at one.

The equality chain is valid. Positivity of the resource integrand forces the endpoint to be one, and equality in the population integral forces the pointwise lower bound to be attained almost everywhere.

The resulting profile values are correctly computed:
$$ \frac{\sqrt3}{2},\qquad \frac{\sqrt3}{6}. $$
Both occur on positive-measure population sets.

A finite profile using only rational constants cannot equal these values almost everywhere. This disproves universal output in the stipulated rational schedule representation, even for factor-one feasibility.

8. Two-cell formula and hardness reduction

Verified for the stated positive square-root-sum comparison problem.

The benchmark calculation
$$ q_i^2=\frac{h_i^-h_i^+}{4} $$
is correct.

The maximum-height resource bound yields the displayed upper bound. The proposed schedule attains it: the uniform type traverses the first cell, all other types fit in the second, and the remaining uniform population fills the residual length. Its population masses and resource lengths agree with the stated formulas.

The reduction produces positive normalized rational densities with polynomial encoding length. Substitution gives
$$ \rho^*=\frac{2nC}{nC+\sum_i\sqrt{a_i}}, $$
and the threshold equivalence has the correct inequality direction.

This establishes the advertised reduction from positive square-root-sum comparison. It does not establish $\mathrm{NP}$-hardness. The cited [square-root-sum paper](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54) supports the statement that polynomial-time exact comparison remains open.

The restriction to general binary-encoded rationals is explicitly stated; the reduction is not claimed to preserve dyadic heights.

9. Exponential degree with dyadic input

Verified.

The binomial-coefficient argument supplies enough distinct odd primes within the stated polynomial bound. The resulting dyadic input has total encoding length $O(n^4)$.

The benchmark and ratio calculations are correct:
$$ q_i=\frac{\sqrt{M_i}}{2^{r_i}}, \qquad \frac{q_i}{h_i^+}=\frac1{2\sqrt{M_i}}. $$

The gcd identity makes the $M_i$ pairwise coprime. Their residue modulo eight excludes squares, so each has a prime with odd valuation unique to that $M_i$. This establishes independence of their rational square classes.

The supplied induction justifies the multiquadratic field degree and independent sign automorphisms. Linear independence of the square-root monomials then shows that no nonidentity sign change fixes the sum $S$.

The rational relations between $S$ and $\rho^*$ establish equal generated fields. Hence the degree is exactly
$$ 2^{\tau-1}. $$

The dense-polynomial output-size obstruction follows. Equality in the resource lower bound also forces the uniform type’s profile to be $\rho^*/2$ almost everywhere, giving the claimed obstruction for dense algebraic schedule coefficients.

These are representation-specific output lower bounds, not computational hardness results for compact expressions.

10. Exact optimization and algebraic witnesses

The construction and bounds are supported, with one minor procedural omission.

The one-block specialization used matches [Basu’s Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf). Its arithmetic-operation and integer bit-size bounds yield the stated bit-time form for integer-coefficient formulas with at most one free variable.

The root-isolation bound matches [Sagraloff–Mehlhorn’s Theorem 2](https://arxiv.org/pdf/1308.4088). The prover correctly requires square-free input and allows polynomial-time square-free preprocessing.

Basis enumeration, determinant degree bounds, coefficient bounds, and feasibility signs are correct. Positive benchmark-root constraints identify the intended benchmarks uniquely.

The union of the eliminated basis formulas describes feasible positive factors. Attainment and boundedness justify extracting a finite endpoint. The exponential bounds accommodate basis enumeration and polynomial postprocessing.

The algebraic witness construction is concrete: basis selection produces Cramer expressions, and the empty-cell repair uses only arithmetic operations with nonzero denominators. The larger bound for selecting an optimum basis accounts for introducing the optimum’s defining polynomial.

Minor issue: the endpoint-extraction paragraph does not specify how roots of different output polynomials are ordered or identified when their isolating intervals overlap or they share roots. Isolation separately followed by unspecified “rational interval samples” is not a fully specified procedure.

Minimum clarification: state the joint root-ordering and coincident-root handling used before choosing samples, and confirm that its bit complexity is included in the stated bound. This is routine univariate algebraic postprocessing; it does not require a new mathematical argument.

The output is explicitly an extended algebraic representation. It does not satisfy the original rational schedule encoding, which Section 7 proves impossible in general.

11. Coverage of the assigned task

The output correctly labels itself partial. It establishes:

• Factor-one decision in $\mathrm P$.
• Attainment of every finite optimum.
• Exact threshold decision in polynomial time for fixed $\tau$.
• Failure of universal rational schedule output.
• Square-root-sum hardness under general rational encoding.
• Representation-specific exponential degree lower bounds.
• Explicit exponential-time exact algebraic algorithms and witnesses.

Major scope issue: the requested unrestricted complexity classifications remain unsettled. Neither the threshold upper bound nor the square-root-sum reduction decides whether unrestricted threshold feasibility is in $\mathrm P$ or is $\mathrm{NP}$-hard. Likewise, the dense-output obstruction and exponential algorithm do not classify compact exact value computation.

This is acknowledged incompleteness, not a false claimed theorem. Another verification round can address the minor algorithm-description issue, but completing the original classification would require additional mathematical results.

⟨structured verdict parsed — rendered above⟩