Answer: \(\mathrm{NP}\)-hard
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\egal~and \egalD~are NP-complete in the strong sense. Furthermore, for every $\epsilon > 0$ there is no $(2-\epsilon)$ approximation for either of the problems, unless P=NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational mass vector \(\mu\), population scale \(N\), explicit piecewise-uniform valuation densities \(\nu_t\) on a cake interval \([0,N]\), and threshold \(B\), decide whether there are assignment measures \(\xi_t\) over connected intervals \(I\) such that \(\xi_t(\mathcal I)=N\mu_t\), each mass unit receives one interval, \(\sum_t\int \mathbf{1}_{x\in I}\,d\xi_t(I)\leq 1\) almost everywhere, and \(v_t(I)=\int_I\nu_t(x)\,dx\geq B\) for \(\xi_t\)-almost every assigned interval.
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 input also gives a positive binary rational population scale \(N\), a binary rational threshold \(B\), and explicit densities \(\nu_t\) on \([0,N]\). Each density is a step function taking only values \(0\) and \(c_t>0\), with rational breakpoints and heights, and satisfies \(\int_0^N\nu_t(x)\,dx=1\).
Let \(m\) be the number of cells in the common breakpoint partition and \(L\) the total input bit length. State running times in \(m,\tau,L\), including any dependence on the numerical value of \(N\).
Identify the space \(\mathcal I\) of connected intervals with \(\{(a,b):0\leq a\leq b\leq N\}\), equipped with its Borel sets; degenerate intervals are allowed. Write \(v_t(I)=\int_I\nu_t(x)\,dx\).
An allocation consists of finite nonnegative Borel measures \(\xi_t\) on \(\mathcal I\), with \(\xi_t(\mathcal I)=N\mu_t\): every unit of population mass receives one interval. Require \(\sum_{t\in T}\int_{\mathcal I}\mathbf1_{\{x\in I\}}\,d\xi_t(I)\leq1\) for Lebesgue-almost every \(x\), and \(v_t(I)\geq B\) for \(\xi_t\)-almost every \(I\). Unused cake is permitted.
Is this assignment-measure feasibility problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For a finite list of agents, connected egalitarian threshold feasibility is strongly \(\mathrm{NP}\)-complete, even with explicit piecewise-uniform valuations; the ordered indivisible-item variant is also strongly \(\mathrm{NP}\)-complete. [Aumann–Dombb–Hassidim](https://arxiv.org/pdf/1205.3982)
No complexity classification for exactly the assignment-measure formulation above was located in the literature search.
1. Proven classification. The assignment-measure feasibility problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions.
This holds even when every density is uniform on a single connected support interval, \(m=\tau\), and \(\tau\leq N<2\tau\). The masses and threshold in the construction are dyadic rationals. Consequently, an algorithm running in \(\operatorname{poly}(m,\tau,L,N)\) time would imply \(\mathrm P=\mathrm{NP}\).
The proof below addresses arbitrary finite Borel assignment measures directly.
2. A lemma extracting an exact tiling from fractional coverage. Let \(H>0\), and let \(d_1,\ldots,d_r>0\). For each \(j\), let \(\eta_j\) be a finite nonnegative Borel measure supported on intervals \([a,a+d_j]\subseteq[0,H]\). Suppose their aggregate coverage is exactly one almost everywhere:
\(\displaystyle \sum_{j=1}^r\int \mathbf 1_{\{x\in I\}}\,d\eta_j(I)=1\quad\text{for almost every }x\in(0,H).\)
Then there is a finite sequence of lengths from \(\{d_1,\ldots,d_r\}\), allowing repetitions, whose sum is \(H\).
To prove this, let \(S\) and \(E\) be the aggregate start and end measures. Extend the coverage function \(g\) by zero outside \([0,H]\). For every smooth compactly supported function \(\varphi\), Fubini’s theorem and the fundamental theorem of calculus give
\(\displaystyle \int_{\mathbb R}g(x)\varphi'(x)\,dx =\sum_j\int\bigl(\varphi(a+d_j)-\varphi(a)\bigr)\,d\eta_j =\int\varphi\,d(E-S).\)
On the other hand, the assumed coverage gives
\(\displaystyle \int_{\mathbb R}g(x)\varphi'(x)\,dx=\varphi(H)-\varphi(0).\)
These identities imply the equality of finite signed measures
\(\displaystyle S-E=\delta_0-\delta_H.\)
Indeed, smooth test functions determine finite measures on a compact interval, by their uniform density in the continuous functions.
All interval lengths are positive, so \(E(\{0\})=0\); hence \(S(\{0\})=1\). Some type therefore has a positive start atom at \(0\), producing a positive end atom at its right endpoint \(x_1\).
Whenever a positive end atom occurs at \(x<H\), the measure identity gives \(S(\{x\})=E(\{x\})>0\). Thus an interval with positive atomic mass starts there. Repeatedly following such intervals produces strictly increasing endpoints, each increment at least \(\min_j d_j>0\), and every endpoint lies in \([0,H]\). The process must therefore reach \(H\) after finitely many steps. Those increments give the asserted exact tiling.
This lemma requires neither finite support nor an assumed decomposition into integral allocations.
3. Arithmetic encoding of PARTITION. We reduce from PARTITION with positive integers \(w_1,\ldots,w_n\), where \(n\geq2\) and \(\sum_i w_i=2W\). The question is whether some subset sums to \(W\). PARTITION is \(\mathrm{NP}\)-complete; odd totals and lists with fewer than two entries can be handled by elementary preprocessing, so this restriction preserves hardness. See the [MIT lecture notes on NP-completeness](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf).
Define
\(\displaystyle R=n+1,\qquad D=2nW+1,\qquad e_i=R^{i-1},\qquad E_*=\sum_{i=1}^n e_i.\)
For each \(i\), introduce two numbers
\(\displaystyle a_i^0=De_i,\qquad a_i^1=De_i+w_i.\)
Set
\(\displaystyle A=\max_{i,\epsilon}a_i^\epsilon,\qquad H_*=nA+DE_*+W+1,\)
and define the interval-length integers and target
\(\displaystyle p_i^\epsilon=H_*+a_i^\epsilon,\qquad C=nH_*+DE_*+W.\)
They satisfy
\(\displaystyle \sum_{i=1}^n(p_i^0+p_i^1)=2C.\)
We claim that every nonnegative integer solution of
\(\displaystyle \sum_{i,\epsilon}q_i^\epsilon p_i^\epsilon=C\)
chooses exactly one number from each pair and identifies a PARTITION solution.
Let \(q=\sum_{i,\epsilon}q_i^\epsilon\). If \(q\leq n-1\), then
\(\displaystyle \sum_{i,\epsilon}q_i^\epsilon p_i^\epsilon \leq(n-1)(H_*+A)<nH_*<C,\)
because \(H_*>nA\). If \(q\geq n+1\), then
\(\displaystyle \sum_{i,\epsilon}q_i^\epsilon p_i^\epsilon \geq(n+1)H_*>C,\)
because \(H_*>DE_*+W\). Thus \(q=n\).
Subtracting \(nH_*\) gives
\(\displaystyle D\sum_i(q_i^0+q_i^1)e_i+\sum_iq_i^1w_i=DE_*+W.\)
The quantity \(z=\sum_iq_i^1w_i\) satisfies \(0\leq z\leq2nW<D\), and \(0<W<D\). Reduction modulo \(D\) therefore gives \(z=W\), followed by
\(\displaystyle \sum_i(q_i^0+q_i^1)R^{i-1}=\sum_iR^{i-1}.\)
Every coefficient \(q_i^0+q_i^1\) lies between \(0\) and \(n=R-1\). Uniqueness of base-\(R\) representation gives
\(\displaystyle q_i^0+q_i^1=1\quad\text{for every }i.\)
Consequently, \(\{i:q_i^1=1\}\) sums to \(W\).
Conversely, a subset summing to \(W\) selects one number from each pair with total \(C\). The complementary choices also total \(C\).
4. Construction of the society. Let \(P_*=\max_{i,\epsilon}p_i^\epsilon\), and let \(k\) be the smallest power of two satisfying \(k\geq n+1\). Define
\(\displaystyle N=2k,\qquad B=\frac1k,\qquad d_i^\epsilon=\frac{p_i^\epsilon}{P_*},\qquad \ell=\frac C{P_*}.\)
Since \(C<(n+1)H_*\leq k p_i^\epsilon\), we have
\(\displaystyle 0<\ell<k d_i^\epsilon\leq k<N.\)
There are \(2n+2\) types:
Each density integrates to one. All masses are positive, and their sum is
\(\displaystyle \frac{n}{2k}+\frac12+\frac{k-n}{2k}=1.\)
The required assignment masses are therefore
\(\displaystyle N\mu_i^\epsilon=\frac12,\qquad N\mu_b=k,\qquad N\mu_d=k-n.\)
Every item type values all of \([0,\ell]\) uniformly. An interval contained there meets its threshold precisely when its length is at least \(d_i^\epsilon\).
5. Equivalence of the two instances. First suppose the PARTITION instance is a YES-instance.
Its selected and complementary choices each have total length \(C\) in the integer encoding. After division by \(P_*\), each choice therefore tiles \([0,\ell]\). Construct both tilings, and give every item interval in each tiling assignment mass \(1/2\).
Every item type appears in exactly one tiling, so it receives its required mass \(1/2\). Its interval has length \(d_i^\epsilon\), giving value exactly \(B\). The aggregate item coverage is one almost everywhere on \([0,\ell]\).
For the blocker, partition \([\ell,k]\) into \(k\) equal intervals and place assignment mass one on each. Each has value \(1/k=B\). For the dummy, use \(k-n\) disjoint unit intervals inside \([k,2k]\), each with assignment mass one and value \(1/k=B\).
These measures satisfy all demands and the capacity constraint. The finitely many shared endpoints do not affect the almost-everywhere requirement.
Now suppose the constructed society admits arbitrary feasible assignment measures. Write \(g_t\) for each type’s coverage function.
The blocker’s threshold and required mass imply, by Tonelli’s theorem,
\(\displaystyle 1=kB\leq\int v_b(I)\,d\xi_b(I) =\frac1{k-\ell}\int_\ell^k g_b(x)\,dx\leq1.\)
The final inequality follows from the capacity constraint. Equality throughout implies \(g_b(x)=1\) almost everywhere on \((\ell,k)\). All other types consequently have zero coverage there almost everywhere.
In particular, for each item type,
\(\displaystyle \int |I\cap(\ell,k)|\,d\xi_i^\epsilon(I)=0.\)
Thus almost every item interval has zero-length intersection with the blocker region. Its value is positive, and its valued support is a prefix ending at or before \(k\); consequently, it must be contained in \([0,\ell]\). Indeed, any positive-valued interval extending beyond \(\ell\) would intersect \((\ell,k)\) in positive length.
For such intervals, the threshold requires \(|I|\geq d_i^\epsilon\). Capacity on \([0,\ell]\) now gives
\(\displaystyle \ell \geq\sum_{i,\epsilon}\int |I|\,d\xi_i^\epsilon(I) \geq\frac12\sum_{i,\epsilon}d_i^\epsilon =\frac C{P_*} =\ell.\)
Both inequalities are therefore equalities. Because all excess lengths are nonnegative, item intervals have length exactly \(d_i^\epsilon\) almost surely. Their aggregate coverage is also exactly one almost everywhere on \([0,\ell]\): it is bounded by one and its integral equals \(\ell\).
Apply the tiling lemma from Section 2. It supplies a finite sequence of item lengths summing exactly to \(\ell\). Multiplying by \(P_*\) supplies nonnegative integer counts satisfying
\(\displaystyle \sum_{i,\epsilon}q_i^\epsilon p_i^\epsilon=C.\)
Section 3 proves that these counts select exactly one number from every pair and yield a subset of the original weights summing to \(W\). The PARTITION instance is therefore a YES-instance.
This establishes both directions, including the direction involving arbitrary Borel measures.
6. Encoding size and running-time consequence. Let
\(\displaystyle h=O\bigl(n\log(n+1)+\log(W+1)\bigr).\)
All integers in the arithmetic encoding have \(O(h)\) bits. All constructed rational parameters also have \(O(h)\) bits; for example, item support endpoints and heights are
\(\displaystyle \frac{k p_i^\epsilon}{P_*}\quad\text{and}\quad\frac{P_*}{k p_i^\epsilon}.\)
The reduction runs in \(n\operatorname{poly}(h)\) bit time and produces \(L=O(nh)\) input bits using the explicit step-function descriptions.
The \(2n\) item support endpoints are distinct: within each pair this follows from \(w_i>0\), and between consecutive pairs it follows from \(D(e_{i+1}-e_i)>w_i\). All lie strictly above \(\ell\), and the largest is \(k\). Including \(0,\ell,N\), the common partition therefore has
\(\displaystyle m=2n+2=\tau.\)
Moreover, \(n+1\leq k\leq2n\), so
\(\displaystyle \tau\leq N=2k<2\tau.\)
Hence the hardness persists when the numerical value of \(N\) is linear in both \(m\) and \(\tau\). The established classification is \(\mathrm{NP}\)-hardness; the reduction uses binary rational precision and does not establish strong \(\mathrm{NP}\)-hardness.
⟨structured verdict parsed — rendered above⟩
The claimed \(\mathrm{NP}\)-hardness is established. I found no major or minor mathematical issues. The proof applies to the assignment-measure formulation as stated, including arbitrary finite Borel measures and almost-everywhere capacity constraints.
The lemma and its proof are correct.
\[ S-E=\delta_0-\delta_H. \]
The conclusion supplies precisely the integer multiplicities needed later. It does not assert an integral decomposition of the assignment measures, and none is needed.
The source problem is appropriate. The cited [MIT lecture notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf) state PARTITION’s weak \(\mathrm{NP}\)-completeness. Restricting to positive integers, even total, and at least two entries preserves hardness through the stated elementary preprocessing.
All arithmetic claims check out.
First, summing the two choices for every index gives
\[
\sum_{i=1}^n(p_i^0+p_i^1)
=2nH_*+2DE_*+2W
=2C.
\]
For an integer representation of \(C\), the bounds excluding fewer or more than \(n\) summands are valid:
Consequently \(q=n\). The residual weight contribution satisfies
\[
0\leq z=\sum_iq_i^1w_i\leq 2nW<D.
\]
Since \(0<W<D\), congruence modulo \(D\) forces \(z=W\), rather than merely a congruent value.
Every base-\(R\) coefficient lies in \(\{0,\ldots,R-1\}\). Thus uniqueness of positional representation applies without carries and forces exactly one choice from every pair. The converse and complementary-choice assertions follow from the same definitions and the verified total \(2C\).
The construction satisfies every input requirement.
The support-containment inequality is correct:
\[
C<(n+1)H_*\leq kp_i^\epsilon.
\]
Hence
\[
0<\ell<kd_i^\epsilon\leq k<N.
\]
In particular, the blocker support has positive length, and every item support contains \([0,\ell]\).
All densities have positive rational heights, take only their stated positive height and zero, and integrate to one. All masses are positive: \(k\geq n+1\) ensures positivity of the dummy mass. Their sum and their scaled assignment demands are computed correctly.
The masses and threshold are dyadic because \(k\) is a power of two. The construction does not claim that the density parameters are dyadic; rational parameters suffice.
The proposed assignment is feasible.
The selected choices and complementary choices each tile \([0,\ell]\). Each item type appears exactly once across these two tilings and receives assignment mass \(1/2\), as required. An item interval of length \(d_i^\epsilon\) has value
\[
\frac{d_i^\epsilon}{kd_i^\epsilon}=\frac1k=B.
\]
Each tiling contributes coverage \(1/2\), so their sum gives coverage one almost everywhere.
The blocker receives \(k\) intervals of assignment mass one, each with value \(1/k\). The dummy receives \(k-n\) unit intervals within its support, each also with value \(1/k\). These regions have disjoint interiors. Shared endpoints form a finite set and therefore do not violate the almost-everywhere capacity requirement.
Every step of the converse is justified.
Blocker saturation. Tonelli applies to the nonnegative measurable incidence integrand. The blocker’s threshold and total assignment mass give the lower bound one; capacity gives the upper bound one. Equality forces blocker coverage one almost everywhere on \((\ell,k)\). Nonnegativity then forces every other type’s coverage to vanish there almost everywhere.
Item confinement. Applying Tonelli again gives zero expected intersection length with \((\ell,k)\). Thus almost every item interval avoids this region in positive length. Its positive value requires positive-length intersection with its valued prefix, whose endpoint is at most \(k\). Connectedness therefore excludes any extension beyond \(\ell\). Degenerate intervals cannot satisfy the positive threshold.
Length and coverage saturation. On \([0,\ell]\), the item threshold is exactly the lower bound \(d_i^\epsilon\) on interval length. The displayed chain
\[
\ell
\geq\sum_{i,\epsilon}\int |I|\,d\xi_i^\epsilon(I)
\geq\frac12\sum_{i,\epsilon}d_i^\epsilon
=\ell
\]
is correct. Capacity gives the first inequality; the required assignment masses give the second.
Equality forces every nonnegative excess-length integral to vanish. Hence each item measure is concentrated on intervals of its specified length. Aggregate item coverage is bounded by one and has integral \(\ell\), so it equals one almost everywhere.
Lemma application. After discarding null exceptional sets, the measures satisfy all hypotheses of the exact-tiling lemma: finitely many positive lengths, finite nonnegative Borel measures, confinement to \([0,\ell]\), and exact coverage almost everywhere. Its resulting length sequence gives nonnegative integer counts satisfying the arithmetic target equation. Section 3 then recovers a PARTITION solution.
No finite-support assumption or unproved rounding assertion enters this implication.
The encoding bounds are valid. Powers of \(n+1\), the arithmetic parameters, and all rational numerators and denominators have
\[
O\bigl(n\log(n+1)+\log(W+1)\bigr)
\]
bits. The explicit descriptions therefore have polynomial total length, and the claimed reduction time is polynomial in the source input length.
The breakpoint count is also correct. Within-pair endpoints differ because \(w_i>0\); successive pairs are strictly separated by the stated inequality. There are \(2n\) distinct item endpoints, including \(k\), together with the distinct points \(0,\ell,N\). Thus there are \(2n+2\) cells:
\[
m=\tau=2n+2.
\]
Finally,
\[
n+1\leq k\leq2n
\]
implies
\[
\tau\leq N<2\tau.
\]
Therefore a feasibility algorithm polynomial in \(m,\tau,L,N\), including the numerical value of \(N\), would yield a polynomial-time algorithm for PARTITION.
The output correctly limits its conclusion to \(\mathrm{NP}\)-hardness. It establishes neither membership in \(\mathrm{NP}\) nor strong \(\mathrm{NP}\)-hardness, and neither is required to substantiate its claim.
No repair or additional clarification is needed for the claimed classification.
⟨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.