Answer: \(\mathrm P\): the exact minimum is \(\sum_j\mu_j r_j(1-r_j)\), where \(r_j=a_j-\lfloor a_j\rfloor\), and the decision takes \(O(\tau L^2)\) bit operations.
Theorem 1 — class: other
Given demand types \(d_1,\ldots,d_\tau\in\mathbb{N}\) with atomless masses \(\mu_j>0\), \(\sum_j\mu_j=1\), and rational per-capita supply \(b\le D:=\sum_j\mu_jd_j\), find a symmetric law over measurable allocations that gives each type-\(j\) individual an integer bundle in \(\{0,\ldots,d_j\}\), allocates exactly \(b\) units per capita in every realization, and gives each type-\(j\) individual expected allocation \(a_j:=bd_j/D\). Minimize the population-weighted sum of individual variances over such laws.
The society is given by its support: \(\tau\ge1\) distinct demands \(d_j\in\mathbb Z_{\ge0}\), each with positive binary-rational mass \(\mu_j\), where \(\sum_j\mu_j=1\); \(\tau\) counts supported types, not possible demands. Let \(m=\max_j d_j\), \(D=\sum_j\mu_jd_j\), and let the binary-rational supply satisfy \(0\le b\le D\). Set \(a_j=bd_j/D\) when \(D>0\), and \(a_j=0\) otherwise.
Represent type \(j\) by an atomless copy of \([0,1)\), with population measure \(\mu_j\,ds\). A law is a jointly measurable random allocation \(X_j(s,\omega)\in\{0,\ldots,d_j\}\). Symmetry means that all individuals of a given type have the same marginal distribution; no independence is required.
Require \(\mathbb E[X_j(s,\cdot)]=a_j\) for every \(j,s\), and \(\sum_j\mu_j\int_0^1X_j(s,\omega)\,ds=b\) in every realization. Minimize \(V=\sum_j\mu_j\int_0^1\operatorname{Var}(X_j(s,\cdot))\,ds\).
For a binary-rational threshold \(v\ge0\), consider the decision problem of whether such a law exists with \(V\le v\). Let \(L\) be the total input bit length, including the demands, masses, supply, and threshold.
Is this continuous minimum-variance decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), with polynomial time measured in \(\tau,L\) under binary encoding.
For finitely many agents with integer demands and integer total supply, feasible prescribed expectations admit a law minimizing every individual's variance simultaneously; such laws are exactly those whose realized shares differ from their expectations by less than one ([Tasnádi, 2002](https://doi.org/10.1016/S0165-4896(02)00014-8)). This characterization does not assert a polynomial running time. No result settling the atomless problem defined here was located in the search.
The decision problem is in \(\mathrm P\). Its exact minimum is
\(\displaystyle V_{\min}=\sum_{j=1}^{\tau}\mu_j r_j(1-r_j)\),
where \(r_j=a_j-\lfloor a_j\rfloor\).
Under ordinary binary encoding, the decision can be made in \(O(\tau L^2)\) bit operations using schoolbook integer arithmetic. No iteration over the \(m\) possible allocation levels is needed.
Fix an integer demand \(d\), an expectation \(a\in[0,d]\), and a random variable \(Y\in\{0,\ldots,d\}\) with \(\mathbb E[Y]=a\). Write \(k=\lfloor a\rfloor\) and \(r=a-k\).
For every integer \(n\), the product \((n-k)(n-k-1)\) is nonnegative: its two factors cannot have opposite signs. Therefore
\(\mathbb E[(Y-k)(Y-k-1)]\ge0\).
Expanding this expectation gives
\[
\mathbb E[(Y-k)(Y-k-1)]
=\operatorname{Var}(Y)+r^2-r.
\]
Consequently, \(\operatorname{Var}(Y)\ge r(1-r)\).
Equality holds precisely when \(Y\) is supported on \(\{k,k+1\}\), intersected with its allowed range. Its expectation then forces probabilities \(1-r\) and \(r\), respectively. When \(r=0\), equality means \(Y=k\) almost surely.
Apply this bound to \(X_j(s,\cdot)\) for every \(j,s\). Integrating and summing yields
\(\displaystyle V\ge\sum_j\mu_j r_j(1-r_j)\).
This lower bound does not require symmetry or the realization-by-realization supply constraint.
First suppose \(D>0\). Since \(0\le b\le D\), every prescribed expectation satisfies \(0\le a_j\le d_j\). Put \(k_j=\lfloor a_j\rfloor\) and \(r_j=a_j-k_j\).
Take the probability space \(\Omega=[0,1)\) with Lebesgue probability measure. For \(s,u\in[0,1)\), define
\(\displaystyle X_j(s,u)=k_j+\mathbf 1_{\{\{s+u\}<r_j\}}\),
where \(\{x\}=x-\lfloor x\rfloor\) denotes fractional part.
This is jointly Borel measurable. It also takes values in \(\{0,\ldots,d_j\}\): if \(r_j>0\), then \(k_j+1\le d_j\); if \(r_j=0\), the indicator is always zero.
For every fixed \(s\), the map \(u\mapsto\{s+u\}\) preserves Lebesgue measure. Indeed, splitting its domain at \(1-s\) makes it a translation onto each of the two intervals partitioning \([0,1)\). Thus
\(\mathbb P(X_j(s,\cdot)=k_j+1)=r_j\).
Every individual of type \(j\) has the same marginal distribution, with expectation \(k_j+r_j=a_j\) and variance \(r_j(1-r_j)\).
Likewise, for every fixed realization \(u\), the map \(s\mapsto\{s+u\}\) preserves Lebesgue measure. Hence
\(\displaystyle \int_0^1X_j(s,u)\,ds=k_j+r_j=a_j\)
for every \(u\). It follows that the realized total allocation is
\(\displaystyle \sum_j\mu_j\int_0^1X_j(s,u)\,ds
=\sum_j\mu_j a_j
=\frac bD\sum_j\mu_jd_j=b\).
The construction therefore satisfies all constraints and attains the lower bound simultaneously for every individual. Atomlessness supplies the crucial feature: each type can have exactly the required proportion \(r_j\) receiving its upper allocation in every realization.
If \(D=0\), positivity of the masses and nonnegativity of the demands imply \(d_j=0\) for every \(j\). Also \(b=0\), so the identically zero allocation is feasible and has minimum variance zero.
The preceding proof reduces the decision to comparing an explicitly computable rational number with \(v\). The following integer calculation establishes the claimed bit complexity.
Write the masses, supply, and threshold as binary-encoded fractions. Let \(Q\) be the product of all their denominators, and define integers \(c_j,B,C\) by
\(\mu_j=c_j/Q\), \(b=B/Q\), and \(v=C/Q\).
Set \(N=\sum_jc_jd_j\), so \(D=N/Q\).
If \(N=0\), answer yes, since the minimum is zero and \(v\ge0\). Otherwise, for each supported type perform Euclidean division
\(\displaystyle Bd_j=k_jN+R_j,\qquad 0\le R_j<N\).
Because \(a_j=Bd_j/N\), this gives \(r_j=R_j/N\). Therefore
\(\displaystyle V_{\min}=\frac{S}{QN^2}\),
where
\(\displaystyle S=\sum_jc_jR_j(N-R_j)\).
The decision is exactly the integer comparison \(S\le CN^2\).
All integers in this calculation have \(O(L)\) bits:
There are \(O(\tau)\) additions, multiplications, and divisions of integers having \(O(L)\) bits. Schoolbook arithmetic therefore gives \(O(\tau L^2)\) bit operations.
The dependence on demand magnitude enters through its binary length, at most \(O(\log(m+1))\) per demand, rather than through \(m\) allocation levels. Thus this is polynomial time in \(\tau,L\) under binary encoding. In particular, an \(\mathrm{NP}\)-hardness classification under polynomial-time reductions would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated atomless decision problem correctly. The minimum-variance formula, the construction attaining it, and the polynomial bit-complexity bound are rigorous. No major or minor issues were found.
For integer \(n\), the inequality \((n-k)(n-k-1)\ge0\) is correct, including \(n=k\) and \(n=k+1\), where equality holds. Since \(Y\) has finite support, all expectations used exist.
The expansion
\[
\mathbb E[(Y-k)(Y-k-1)]
=\operatorname{Var}(Y)+r^2-r
\]
is correct using \(\mathbb E[Y-k]=r\). It establishes the claimed lower bound \(\operatorname{Var}(Y)\ge r(1-r)\).
The equality characterization is also correct: the nonnegative product has expectation zero exactly when \(Y\) lies in its zero set almost surely. The prescribed mean then determines the stated probabilities. When \(r=0\), it forces \(Y=k\) almost surely, including the boundary case \(k=d\).
The lower bound applies to every individual because the mean constraint is imposed for every \(j,s\). Integrating against the positive masses gives the asserted lower bound for \(V\).
Joint measurability and boundedness of the allocations ensure that the expectations and variance functions being integrated are measurable and finite. Neither symmetry nor the supply constraint is needed for this lower bound, as claimed.
The proposed allocation is jointly Borel measurable: fractional part is Borel measurable, and the indicator uses a Borel interval.
Its values satisfy the demand restriction. If \(r_j>0\), the inequality \(a_j\le d_j\), together with integer \(d_j\), implies \(k_j+1\le d_j\). If \(r_j=0\), the indicator vanishes everywhere.
The stated interval-splitting argument correctly establishes that rotation modulo one preserves Lebesgue measure. Consequently, for every fixed \(s\), the upper allocation has probability \(r_j\). This verifies the expectation requirement for every individual, symmetry within each type, and the asserted variance.
Applying the same measure-preservation argument with \(u\) fixed establishes
\[
\int_0^1X_j(s,u)\,ds=a_j
\]
for every \(u\), rather than merely almost surely. The subsequent weighted sum equals \(b\) by the definition of \(D\) and \(a_j\).
Thus the construction satisfies the exact realization-by-realization constraint and attains the lower bound. Using one shared random variable introduces dependence, which the task explicitly permits.
The treatment of \(D=0\) is correct: positive masses and nonnegative demands force every supported demand to be zero, and \(0\le b\le D\) forces \(b=0\).
For \(D>0\), the construction also covers zero demands, \(b=0\), \(b=D\), and integer prescribed expectations without exceptions. The zero allocation in the degenerate case satisfies every required constraint.
The common-denominator conversion is valid under the stated ordinary binary fraction encoding. The identities \(D=N/Q\) and \(a_j=Bd_j/N\) are correct. Euclidean division therefore produces the correct fractional parts.
Substituting those remainders gives the stated numerator \(S\), denominator \(QN^2\), and comparison \(S\le CN^2\). Since \(Q,N>0\) in this branch, clearing denominators preserves the inequality.
The size bounds are sufficient. The denominator product has \(O(L)\) bits; \(\sum_jc_j=Q\) gives \(N\le Qm\); and the remainder bounds give \(S\le QN^2\). The scaled input numerators, division operands, and comparison operands likewise have \(O(L)\) bits. Constructing the common denominator and scaled numerators requires only \(O(\tau)\) additional arithmetic operations, already covered by the stated total.
Standard schoolbook multiplication and division yield the claimed \(O(\tau L^2)\) bit-operation bound. There is no iteration proportional to \(m\); its magnitude enters through binary input length. The conclusion that the decision problem is in \(\mathrm P\) follows.
No additional clarification or repair is needed. The proof is self-contained and does not rely on the cited finite-agent theorem.
⟨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.