Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateMINSUM-SWITCH-IMPLEMENTATION is NP- complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), room capacities \(\rho_r\), valuations \(v_{tr}\), budgets \(b_t\), rent per resident \(\ell\), and a feasible type-symmetric fractional rent solution \((x,p)\), decide whether there is a finite rational schedule with phase durations \(\lambda_s\) and type-specific distributions over room sequences such that each sequence for type \(t\) spends fraction \(x_{tr}\) in room \(r\), every room has mass \(\rho_r\) in each phase, and total switching mass is at most \(B\). Minimize \(\sum_t \mu_t\) times the expected number of room changes for a resident of type \(t\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types. Residents form a nonatomic population with \(\sum_t\mu_t=1\). There are \(m\geq1\) rooms with positive rational capacities \(\rho_r\) summing to \(1\).
The input includes rational valuations \(v_{tr}\geq0\), budgets \(b_t\geq0\), rent per resident \(\ell\geq0\), threshold \(B\geq0\), and a fixed rational type-symmetric fractional solution \((x,p)\). Payments \(p_t\) may be negative; valuations need not satisfy any sum normalization.
Feasibility means \(x_{tr}\geq0\), \(\sum_r x_{tr}=1\), \(\sum_t\mu_t x_{tr}=\rho_r\), \(\sum_t\mu_t p_t=\ell\), \(p_t\leq b_t\), and, writing \(u_t=\sum_r x_{tr}v_{tr}-p_t\), \(u_t\geq0\) and \(u_t\geq\sum_r x_{t'r}v_{tr}-p_{t'}\) for every \(t,t'\).
A schedule has any finite number \(k\geq1\) of chronologically ordered phases with positive rational durations \(\lambda_s\) summing to \(1\). For each type \(t\), choose a rational probability distribution \(q_t\) over room sequences \(a\in\{1,\ldots,m\}^k\).
Every sequence with \(q_t(a)>0\) must satisfy \(\sum_{s:a_s=r}\lambda_s=x_{tr}\) for every room \(r\); every phase must satisfy \(\sum_t\mu_t\sum_{a:a_s=r}q_t(a)=\rho_r\) for every room \(r\). Fairness and payments apply to the complete lease.
The total switching mass is \(C=\sum_t\mu_t\sum_a q_t(a)\sum_{s=1}^{k-1}\mathbf{1}\{a_s\neq a_{s+1}\}\). Initial placement and departure incur no cost, and returning to a room is allowed. Let \(L\) be the total binary input length.
Is deciding whether such a schedule exists with \(C\leq B\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many individual residents and unit-capacity rooms, minimizing total room changes over all ordered Birkhoff–von Neumann implementations of a given fractional allocation is NP-complete in decision form; ordering a supplied decomposition is also NP-complete. [Source](https://comsoc-community.org/archive/comsoc-2023/comsoc/papers/paper28.pdf)
No result settling the exact nonatomic scheduling problem above was located.
The decision problem is \(\mathrm{NP}\)-hard. This holds even when all type masses and room capacities are equal dyadic rationals, the supplied solution is feasible, and rent, budgets, and payments are zero.
The reduction uses an asymmetric two-room clock. Its possible orientations switch at different times, which prevents mixtures within a type from canceling the event needed for the reduction.
For each type \(t\), define \(d_t=|\{r:x_{tr}>0\}|\).
Every positive-probability sequence must visit exactly these rooms: positive quotas require visits, and zero quotas prohibit visits because every phase has positive duration. Consequently, every such sequence makes at least \(d_t-1\) switches. Thus every schedule satisfies
\(C\geq C_0:=\sum_t\mu_t(d_t-1).\)
If \(C\leq C_0\), equality holds, and every positive-probability sequence visits each supported room in exactly one contiguous block. Indeed, compress consecutive occurrences of the same room. The compressed sequence has at least \(d_t\) blocks; equality in the switching bound forces exactly \(d_t\), so each supported room appears once.
The duration of its block in room \(r\) is then exactly \(x_{tr}\). In particular, every switch time is a sum of the quotas of rooms preceding that switch.
We reduce from the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive binary integers \(a_0,\ldots,a_{N-1}\), decide whether some subset sums to \(S/2\), where \(S=\sum_{j=0}^{N-1}a_j\). See [Karp’s original NP-completeness results](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Set \(n=N+1\), and define positive rational weights
\(w_j=\dfrac{a_j}{15S}\quad(0\leq j<N),\qquad w_N=\dfrac{2}{15}.\)
Their total is
\(\sum_{j=0}^{n-1}w_j=\dfrac{1}{15}+\dfrac{2}{15}=\dfrac15.\)
We will use the following equivalence:
A subset of these weights sums to \(1/30\) or \(1/6\) if and only if the PARTITION instance is a yes-instance.
To prove it, a subset summing to \(1/30\) cannot contain \(w_N=2/15\). Therefore its original indices satisfy
\(\sum_{j\in H}a_j=15S\cdot\dfrac1{30}=\dfrac S2.\)
Conversely, a partition subset gives a weight sum of \(1/30\). Finally, because the total weight is \(1/5\), a subset sums to \(1/6\) exactly when its complement sums to
\(\dfrac15-\dfrac16=\dfrac1{30}.\)
Let \(M\) be the smallest power of two satisfying \(M\geq3n\), and write \(\delta=1/M\). Padding to \(M\) makes all masses and capacities dyadic.
Create rooms \(R_i,P_i,Q_i\) and types \(A_i,D_i,E_i\), for \(0\leq i<n\). Add \(M-3n\) further types, each with its own additional private room. Every type has mass \(\delta\), and every room has capacity \(\delta\). Hence \(m=\tau=M\), and both total mass and total capacity equal \(1\).
All unspecified allocation entries are zero. The positive entries are:
| Type | Allocation |
|---|---|
| \(A_i\) | \(x_{A_i,R_{i+j\bmod n}}=w_j\) for every \(0\leq j<n\); \(x_{A_i,P_i}=x_{A_i,Q_i}=2/5\) |
| \(D_i\) | \(x_{D_i,R_i}=4/5,\quad x_{D_i,P_i}=1/6,\quad x_{D_i,Q_i}=1/30\) |
| \(E_i\) | \(x_{E_i,P_i}=13/30,\quad x_{E_i,Q_i}=17/30\) |
| Each additional type | Allocation \(1\) to its private room |
Every row sums to \(1\). For each room \(R_i\), the sum of the allocation entries across types is
\(\sum_jw_j+\dfrac45=\dfrac15+\dfrac45=1.\)
For the other rooms, those sums are
\(\dfrac25+\dfrac16+\dfrac{13}{30}=1\quad\text{for }P_i,\)
and
\(\dfrac25+\dfrac1{30}+\dfrac{17}{30}=1\quad\text{for }Q_i.\)
Private-room columns also sum to \(1\). Multiplying by \(\delta\) verifies every capacity equation.
To complete the economic input, assign each type a distinct positive integer \(c_t\), and set \(v_{tr}=c_t\) for every room \(r\). Set all budgets, payments, and rent to zero. Then
\(u_t=\sum_rx_{tr}c_t=c_t>0,\)
and the utility type \(t\) obtains from any other type’s complete lease is also \(c_t\). Thus individual rationality, envy-freeness, affordability, and rent balance all hold. The distinct constants ensure that these are distinct types.
Finally, set the switching threshold to
\(B=\delta n(n+4).\)
This is exactly the lower bound from Section 1: each \(A_i\) uses \(n+2\) rooms, each \(D_i\) uses three, each \(E_i\) uses two, and the additional types use one. Hence
\(C_0=\delta\bigl(n(n+1)+2n+n\bigr)=\delta n(n+4)=B.\)
Suppose the original instance has a partition subset \(H\subseteq\{0,\ldots,N-1\}\). Its weights sum to \(1/30\). Let \(J=\{0,\ldots,n-1\}\setminus H\), whose weights sum to \(1/6\).
Choose any ordering of \(J\) and any ordering of \(H\). Give every type a single deterministic trajectory:
The principal intervals are:
| Time interval | \(A_i\) | \(D_i\) | \(E_i\) |
|---|---|---|---|
| \([0,1/6)\) | Item rooms indexed by \(J\) | \(P_i\) | \(Q_i\) |
| \([1/6,17/30)\) | \(P_i\) | \(R_i\) | \(Q_i\) |
| \([17/30,29/30)\) | \(Q_i\) | \(R_i\) | \(P_i\) |
| \([29/30,1)\) | Item rooms indexed by \(H\) | \(Q_i\) | \(P_i\) |
During each item block indexed by \(j\), the map \(i\mapsto i+j\bmod n\) is a bijection. Thus exactly one entire \(A\)-type occupies each \(R\)-room. During the middle interval, each \(D_i\) occupies \(R_i\). The table also shows that each \(P_i\) and \(Q_i\) always has exactly one occupying type.
Therefore every room has occupancy \(\delta\) throughout the lease. All individual quotas hold by construction.
The item blocks and the two middle blocks give \(n+2\) common phases, all with positive rational durations. Taking probability \(1\) on each prescribed trajectory produces distributions of the required form.
Every trajectory visits each supported room once. Its switching cost therefore attains the lower bound, giving \(C=B\).
Suppose a schedule satisfies \(C\leq B\). Since \(B=C_0\), Section 1 implies that every positive-probability trajectory visits each supported room in one contiguous block.
Assume, toward a contradiction, that the PARTITION instance is a no-instance. Consider the two times
\(h_1=\dfrac{13}{30},\qquad h_2=\dfrac{17}{30}.\)
An \(A_i\)-trajectory has two special blocks of duration \(2/5\), together with item blocks of total duration \(1/5\).
At any switch, the elapsed time is a sum of completed blocks. If no special block has been completed, that time is at most \(1/5\). If both have been completed, it is at least \(4/5\).
Both \(h_1\) and \(h_2\) lie strictly between these bounds. Consequently, a switch at either time must occur after exactly one completed special block. The preceding item blocks would then sum respectively to
\(h_1-\dfrac25=\dfrac1{30},\qquad h_2-\dfrac25=\dfrac16.\)
The equivalence in Section 2 would give a partition, contrary to the assumption. Thus no positive-probability \(A_i\)-trajectory switches at either time.
A \(D_i\)-trajectory has block lengths \(4/5,1/6,1/30\). At a switch, a prefix excluding the \(4/5\) block has duration at most \(1/5\), while a prefix including that block has duration at least \(4/5\).
Hence no \(D_i\)-trajectory switches at \(h_1\) or \(h_2\).
Fix any \(i\). An \(E_i\)-trajectory has only two possible compressed orders:
Let \(\alpha_i\) be the total probability assigned to the first order. The probability of the second order is \(1-\alpha_i\).
Only types \(A_i,D_i,E_i\) can visit \(P_i\), since all other types have zero quota there. We proved that \(A_i\) and \(D_i\) cannot switch at either clock time. Therefore the changes in the expected occupancy of \(P_i\) are exactly
\(-\delta\alpha_i\quad\text{at }h_1,\qquad +\delta(1-\alpha_i)\quad\text{at }h_2.\)
Capacity feasibility requires occupancy to equal \(\delta\) in every phase. Its one-sided limits at each interior time must therefore agree, so both changes must be zero. Since \(\delta>0\), this requires simultaneously \(\alpha_i=0\) and \(\alpha_i=1\), a contradiction.
This argument allows arbitrary mixtures within every type and arbitrarily many finite phases. Thus a schedule with \(C\leq B\) can exist only when the PARTITION instance is a yes-instance.
The construction has \(M<6n\) rooms and positive-mass types. Its rational numbers have binary encoding lengths polynomial in the encoding length of the original integers: the only variable denominators arise from \(15S\) and \(M\). The valuation constants can be chosen from \(1\) through \(M\). Writing the complete input therefore takes polynomial time and space.
We have proved the equivalence
\(\text{PARTITION is yes}\quad\Longleftrightarrow\quad \text{the constructed instance admits a schedule with }C\leq B.\)
This is a polynomial-time many-one reduction, establishing \(\mathrm{NP}\)-hardness for the exact nonatomic scheduling problem.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes \(\mathrm{NP}\)-hardness of the exact nonatomic scheduling problem as stated. I found no major or minor issues. In particular, the reverse implication handles arbitrary mixtures within types and every permitted finite number of phases.
The lower bound is correct.
Since phase durations are strictly positive, a trajectory with positive probability cannot visit a room whose quota is zero. Conversely, a positive quota requires visiting that room. Thus every such trajectory visits exactly the supported rooms.
Compressing consecutive identical room assignments produces at least \(d_t\) blocks and therefore at least \(d_t-1\) switches. Averaging gives the claimed bound
\(C\geq C_0=\sum_t\mu_t(d_t-1)\).
The equality argument is also valid. Every trajectory’s excess over its type’s lower bound is nonnegative. All type masses are positive, and every trajectory under consideration has positive probability. Consequently, equality in the aggregate bound forces equality for every positive-probability trajectory.
Exactly \(d_t\) blocks covering \(d_t\) supported rooms means that each supported room appears in one contiguous block. Its duration must equal its quota. The resulting characterization of switch times as sums of completed room quotas follows directly.
The external theorem used is that PARTITION on positive binary integers is \(\mathrm{NP}\)-complete. This is the appropriate source problem; its binary encoding is essential to the claimed polynomial reduction. The stated theorem is also confirmed in [MIT’s complexity lecture material](https://people.csail.mit.edu/rrw/6.1400-2025/lec19-color.pdf).
The weight calculations are correct:
A subset totaling \(1/30\) cannot contain the added weight. Multiplying its sum by \(15S\) gives precisely an original subset totaling \(S/2\). The converse follows from the same identity.
The equivalence for \(1/6\) is valid because complementation changes that total to \(1/5-1/6=1/30\).
This argument also covers odd \(S\): the asserted integer subset sum \(S/2\) is then impossible. No parity assumption is needed.
The construction produces exactly \(M\) positive-mass types and \(M\) rooms. All masses and capacities equal the positive dyadic rational \(\delta=1/M\), so their respective totals are \(1\).
The allocation checks are correct:
For any fixed item room, the cyclic indexing supplies every weight exactly once across the \(A\)-types. Its column sum is therefore \(1/5+4/5=1\). The two other column calculations are likewise correct:
\(2/5+1/6+13/30=1\) and
\(2/5+1/30+17/30=1\).
Multiplying these column sums by \(\delta\) yields the required capacities.
The economic data satisfy every specified condition. Constant-across-room valuations give type \(t\) value \(c_t\) for its own allocation and for every other type’s allocation, since all allocation rows sum to \(1\). Zero payments therefore imply individual rationality, envy-freeness, affordability, and rent balance. Distinct \(c_t\) make the listed types distinct without using any forbidden valuation normalization.
The threshold calculation is correct:
\(C_0=\delta[n(n+1)+2n+n]=\delta n(n+4)=B\).
The proposed trajectories have exactly the prescribed room quotas.
The common principal boundaries are correct:
The \(D_i\) and \(E_i\) trajectories align with those boundaries exactly as displayed.
During an item block, the cyclic map \(i\mapsto i+j\bmod n\) is a bijection, so each item room receives one entire \(A\)-type. During the middle interval, each item room receives its corresponding \(D\)-type. The displayed assignments give exactly one occupying type in each \(P_i\) and \(Q_i\) throughout every phase.
There are \(n\) item blocks and two special blocks, hence \(n+2\) common phases. Their durations are positive rationals. Deterministic distributions are rational distributions of the required kind.
Every trajectory visits each supported room once, so the cost equals \(B\). The forward implication is established.
The equality characterization from Section 1 applies because \(B=C_0\).
For an \(A_i\)-trajectory, a switch at either clock time must follow exactly one completed special block: a prefix with none has duration at most \(1/5\), while a prefix with both has duration at least \(4/5\). The required preceding item totals are correctly computed as \(1/30\) and \(1/6\). Both are excluded in a no-instance by Section 2.
For a \(D_i\)-trajectory, every prefix excluding its \(4/5\) block has duration at most \(1/5\), and every prefix including it has duration at least \(4/5\). Thus neither clock time can be a switch.
The \(E_i\) characterization is exhaustive. At minimum switching cost, its two supported rooms occur in exactly one block each. The two possible orders switch at \(13/30\) and \(17/30\), respectively.
Only \(A_i,D_i,E_i\) can occupy \(P_i\). Therefore its expected occupancy changes by exactly
\(-\delta\alpha_i\) at the first clock time and
\(\delta(1-\alpha_i)\) at the second.
The capacity argument is valid for the stated schedule model. A finite schedule yields piecewise constant expected occupancies, and phase feasibility fixes each of those values to the room capacity. Hence the one-sided occupancy values at either interior clock time must agree. The two changes must both vanish, forcing the incompatible equations \(\alpha_i=0\) and \(\alpha_i=1\).
This rules out every allowed mixture, including deterministic choices of either orientation. The reverse implication is established.
The bound \(M<6n\) is correct. The complete allocation and valuation matrices have polynomially many entries. The quantities involving \(S\), \(M\), and the valuation constants have polynomial binary encoding length. The construction is therefore a polynomial-time many-one reduction.
The proof establishes the claimed \(\mathrm{NP}\)-hardness even with equal dyadic masses and capacities and a feasible supplied economic solution. It does not claim membership in \(\mathrm{NP}\) or strong \(\mathrm{NP}\)-hardness; neither is needed to resolve the assigned hardness question.
Repair feedback: none required. The written argument settles the target.
⟨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.