Answer: Polynomial-time solvable in \(m,\tau,L\), with \(O(\tau)\) arithmetic and output operations and exactly zero type queries. The proposed \(2(\tau-1)\lceil\log_2 D\rceil\) upper bound holds, but the proposed \(\Omega(\tau\log D)\) lower bound is false.
Theorem 4.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any 2 ≤n and n < D, the number of queries in our n-player protocol on a cake of total value D is T(n, D) ≤2(n −1) · ⌈log2 D⌉.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), masses \(\mu_t\) with \(\sum_t\mu_t=1\), aggregate demands \(w_t\in\mathbb{Z}_{>0}\), atomless valuation oracles \(v_t\) on a cake \(X\) with \(v_t(X)=D=\sum_t w_t\), and type-level cut/evaluation access, compute measurable allocation densities \(a_t:X\to[0,1]\) satisfying \(\sum_t a_t(x)=1\) and \(\int_X a_t\,dv_t\ge w_t\) for every \(t\), while determining the worst-case number of type queries; in particular, whether \(2(\tau-1)\lceil\log_2D\rceil\) queries suffice and whether \(\Omega(\tau\log D)\) are necessary.
A society is given by its support \(T\): the list of its \(\tau\ge2\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a binary-encoded aggregate demand \(w_t\in\mathbb Z_{>0}\); set \(D=\sum_t w_t>\tau\). These are total type demands, so they are not multiplied by \(\mu_t\).
The cake is a known Lebesgue-measurable \(X\subseteq\mathbb R^m\), with \(m\ge1\) and \(0<\lambda(X)<\infty\). Each unknown valuation \(v_t\) is a nonnegative finite measure absolutely continuous with respect to \(\lambda\), with \(v_t(X)=D\).
For a measurable piece \(I\subseteq X\), an evaluation query returns \(v_t(I)\). A moving knife is a measurable-set-valued mapping \(f:[0,\lambda(I)]\to2^I\) with \(f(s)\subseteq f(u)\) for \(s\le u\) and \(\lambda(f(s))=s\).
An absolute cut query returns any \(s\) satisfying \(v_t(f(s))=\alpha\), for \(\alpha\ge0\), or reports impossibility. A proportional cut query returns any \(s\) satisfying \(v_t(f(s))=r v_t(I)\), for rational \(r\in[0,1]\). Each evaluation, absolute cut, or proportional cut counts as one type query; arbitrary valid cut answers must be tolerated.
Compute a finite symbolic description of measurable densities \(a_t:X\to[0,1]\) satisfying \(\sum_t a_t(x)=1\) throughout \(X\) and \(\int_X a_t\,dv_t\ge w_t\) for every \(t\). Fractional densities are permitted, and no connectedness condition is imposed.
Use deterministic protocols with exact oracle answers; oracle calls, arithmetic, comparisons, and symbolic set operations have unit cost. Let \(L\) be the bit length of the finite numerical input; state bounds in \(m,\tau,L,D\). Hardness reductions must provide polynomial-time simulable type oracles.
Is this density-allocation search problem solvable in polynomial time in \(m,\tau,L\) in this oracle model, or is it NP-hard?
What is its worst-case type-query complexity: do \(2(\tau-1)\lceil\log_2D\rceil\) queries suffice, and are \(\Omega(\tau\log D)\) queries necessary?
For finitely many players receiving disjoint measurable pieces, the verified [algorithmic bound](https://hpi.de/friedrich/docs/publications/2020/TALG.pdf) is \(2(n-1)\lceil\log_2D\rceil\) under the proportional-cut convention, for \(2\le n<D\); the same source proves a deterministic worst-case lower bound of \(\Omega(n\log D)\), even with generalized queries.
Those results require disjoint pieces rather than fractional allocation densities; no result settling this exact density-output problem was identified in the search.
The problem is polynomial-time solvable, with exactly zero type queries in the worst case.
Fractional densities permit a valuation-independent solution for every instance. This applies throughout the stated parameter range, rather than only to a degenerate case.
Compute \(D=\sum_{t\in T}w_t\), and output the constant functions
\(a_t(x)=w_t/D\quad\text{for every }t\in T\text{ and }x\in X.\)
These formulas are finite symbolic descriptions of measurable functions.
Because all demands are positive and \(\tau\ge2\), we have \(0<w_t<D\). Thus each \(a_t\) takes values in \([0,1]\). At every point \(x\in X\),
\(\sum_{t\in T}a_t(x)=D^{-1}\sum_{t\in T}w_t=1.\)
For every admissible valuation \(v_t\), integration of a constant gives
\(\int_X a_t\,dv_t=(w_t/D)v_t(X)=(w_t/D)D=w_t.\)
Hence every demand is satisfied exactly. The construction uses the aggregate demands as given; the masses \(\mu_t\) do not enter the allocation.
No oracle is queried, so arbitrary valid cut answers have no effect on correctness.
Computing \(D\) takes \(\tau-1\) additions. Recording the \(\tau\) rational constants takes \(O(\tau)\) further operations. The symbolic output can share the denominator \(D\).
Thus the protocol uses \(O(\tau)\) arithmetic and output operations, independently of \(m\) and the numerical magnitude of \(D\). Including input reading gives a polynomial bound in \(m,\tau,L\).
For an explicit encoding bound, let \(b\) be the maximum bit length of a demand. Since \(D<\tau\,2^b\), its bit length is at most \(b+\lceil\log_2\tau\rceil+1\). Even writing each numerator-denominator pair separately therefore uses \(O(L+\tau\log D)\) bits, which is polynomial in the input parameters.
Consequently:
The polynomial-time construction settles the computational alternative. Any NP-hardness reduction with polynomial-time simulable oracles and polynomial-time solution decoding would, when composed with this construction, imply \(\mathrm{P}=\mathrm{NP}\).
Proven claim. Any fixed feasible density tuple that succeeds for every admissible valuation tuple must satisfy \(a_t=w_t/D\) almost everywhere for each type.
To prove this, put \(p_t=w_t/D\). Suppose \(E=\{x\in X:a_t(x)<p_t\}\) has positive Lebesgue measure. Since
\(E=\bigcup_{k\ge1}\{x\in X:a_t(x)\le p_t-1/k\},\)
some measurable set \(E_k=\{x\in X:a_t(x)\le p_t-1/k\}\) has positive measure. Define, for measurable \(B\),
\(v_t(B)=D\,\lambda(B\cap E_k)/\lambda(E_k).\)
This is a nonnegative finite measure, absolutely continuous with respect to \(\lambda\), with \(v_t(X)=D\). However,
\(\int_X a_t\,dv_t\le D(p_t-1/k)<w_t,\)
contradicting universal success. Thus \(a_t\ge p_t\) almost everywhere.
There are finitely many types, so these inequalities hold simultaneously outside one null set. There, \(\sum_t a_t=\sum_t p_t=1\); the nonnegative differences \(a_t-p_t\) must therefore all vanish. This proves the claim.
The constant allocation is consequently the unique universal allocation up to null sets.
The cited [Cseh–Fleiner result](https://hpi.de/friedrich/docs/publications/2020/TALG.pdf) concerns allocations by disjoint measurable pieces. Such an allocation has indicator densities \(a_t=\mathbf{1}_{I_t}\).
Here the successful constants satisfy \(0<a_t<1\) everywhere, so they are not indicator densities. Allowing fractional output changes the admissible solutions and removes the need to learn the valuations. The disjoint-piece lower bound therefore does not establish a lower bound for the stated task.
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the task. The constant-density construction is valid for every admissible instance, runs in polynomial time, and uses exactly zero type queries. No mathematical errors or gaps were found.
The proposed output is \(a_t(x)=w_t/D\) for every \(x\in X\). These are measurable constant functions with finite symbolic descriptions.
Since each demand is positive and there are at least two types, \(D-w_t=\sum_{u\ne t}w_u>0\). Consequently, \(0<w_t/D<1\), so every density has the required range. Moreover,
\[
\sum_{t\in T}a_t(x)=\frac{\sum_{t\in T}w_t}{D}=1
\]
at every point of \(X\), as required—not merely almost everywhere.
For each admissible valuation, integration of a constant against a finite measure yields
\[
\int_X a_t\,dv_t=\frac{w_t}{D}v_t(X)=w_t.
\]
Every hypothesis needed for this calculation is explicitly supplied: measurability of the density, finiteness of the measure, and the normalization \(v_t(X)=D\).
The construction correctly uses aggregate demands without multiplying them by the masses \(\mu_t\). It works for every allowed dimension and cake, regardless of the valuations’ distributions.
Computing \(D\) requires \(\tau-1\) additions. Producing the constants requires \(O(\tau)\) further operations in the stipulated unit-cost model. The output can reference the given domain \(X\); it does not require constructing a geometric representation of that domain.
The encoding calculation is also valid. If \(b\) is the maximum demand bit length, then each \(w_t<2^b\), hence \(D<\tau 2^b\). The stated bit-length bound for \(D\) is conservative but correct.
Separately encoding all numerator-denominator pairs requires \(O(L+\tau\log D)\) bits. Since \(\log D=O(L+\log\tau)\), this is polynomial in the requested input parameters. Thus the numerical magnitude of \(D\) does not create a pseudopolynomial running-time requirement.
The protocol makes no oracle calls. Therefore it automatically tolerates arbitrary valid cut answers.
Zero queries satisfy the proposed upper bound, and nonnegativity of query counts establishes that the optimal worst-case complexity is exactly zero. This directly contradicts any positive \(\Omega(\tau\log D)\) lower bound for the stated density-output problem.
The NP-hardness observation is correctly conditional: a reduction with polynomial-time oracle simulation and polynomial-time solution decoding, composed with this algorithm, would imply \(\mathrm{P}=\mathrm{NP}\). The prover does not claim an unconditional separation.
This claim is correct under its stated quantifier: one fixed feasible density tuple must succeed for every admissible valuation tuple.
If \(E=\{x\in X:a_t(x)<p_t\}\) has positive measure, where \(p_t=w_t/D\), the displayed countable union is exact. Countable subadditivity then guarantees a positive-measure \(E_k\).
The constructed measure is well defined because \(0<\lambda(E_k)\le\lambda(X)<\infty\). It is finite, nonnegative, absolutely continuous, and normalized to total value \(D\). Its integral satisfies the stated strict violation of type \(t\)’s demand.
Thus each \(a_t\ge p_t\) almost everywhere. Finiteness of \(T\) permits a common exceptional null set. Outside it, the pointwise sum constraint forces all nonnegative differences \(a_t-p_t\) to vanish. The resulting uniqueness up to null sets is justified.
The cited source concerns allocation of disjoint pieces, consistent with the prover’s description. [Cseh–Fleiner, *The Complexity of Cake Cutting with Unequal Shares*](https://hpi.de/friedrich/docs/publications/2020/TALG.pdf).
Such allocations have indicator densities. The proposed constants lie strictly between zero and one, so they belong to the broader fractional-output class. The prover correctly concludes that the disjoint-piece lower bound does not establish a lower bound here.
None required. Both the requested resolution and the supplementary structural claim are rigorously established.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.