Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a subset of hospitals $H_{\open}\subseteq H$, deciding whether there exists a stable matching in an \HRLUQI instance $(H,R)$ in which exactly the hospitals from $H_{\open}$ are open is NP-complete, even if $|H_{\open}|=4$, each resident accepts at most five hospitals, all hospitals have lower quota at most two, and we know that if there exists a stable matching, then it opens exactly the hospitals from~$H_{\open}$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite hospital set \(H\), prescribed \(H_{\mathrm{open}}\subseteq H\), rational population-scale quotas \(0\le \ell_h\le u_h\), and rational type masses \(\mu_t\ge0\) summing to \(1\), where each type \(t\) has a strict preference order over acceptable hospitals, decide whether there are masses \(x_{t,h},x_{t,\bot}\ge0\) with \(\sum_{h\in H}x_{t,h}+x_{t,\bot}=\mu_t\), zero mass at \(H\setminus H_{\mathrm{open}}\), and \(\ell_h\le\sum_t x_{t,h}\le u_h\) for each \(h\in H_{\mathrm{open}}\), such that every undersubscribed open hospital \(h\) satisfies \(\sum_t\sum_{g\in H\cup\{\bot\}:\,h\succ_t g}x_{t,g}=0\) and every closed hospital satisfies \(\sum_t\sum_{g\in H\cup\{\bot\}:\,h\succ_t g}x_{t,g}<\ell_h\).
Given a finite hospital set \(H\), let \(m=|H|\), prescribe \(H_{\mathrm{open}}\subseteq H\), and give binary rational quotas \(0<\ell_h\le u_h\) for every hospital. Hospitals are indifferent among acceptable residents.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type strictly ranks an acceptable subset \(A(t)\subseteq H\); acceptability is mutual, and every acceptable hospital is preferred to being unmatched, denoted \(\bot\).
An assignment consists of divisible real masses \(x_{t,g}\ge0\), for \(g\in H\cup\{\bot\}\), satisfying \(\sum_g x_{t,g}=\mu_t\), with \(x_{t,h}=0\) whenever \(h\notin A(t)\cap H_{\mathrm{open}}\). Write \(s_h=\sum_t x_{t,h}\); require \(\ell_h\le s_h\le u_h\) for every prescribed open hospital.
Define \(D_h(x)=\sum_{t:h\in A(t)}\sum_{g\in A(t)\cup\{\bot\}:h\succ_t g}x_{t,g}\). An assignment is stable if \(s_h<u_h\Rightarrow D_h(x)=0\) for every open hospital, and \(D_h(x)<\ell_h\) for every closed hospital; equality at the lower quota permits a blocking coalition.
Is deciding whether such a stable assignment exists in \(\mathrm{P}\), or is it NP-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\).
The discrete counterpart is NP-complete even with four prescribed open hospitals, at most five acceptable hospitals per resident, and lower quotas at most two. [Boehmer–Heeger](https://arxiv.org/pdf/2009.14171).
No result settling this exact divisible-mass problem was located in the literature search.
The problem is \(\mathrm{NP}\)-complete, even when every type accepts at most five hospitals and every hospital accepts at most three types.
Writing \(k=|H_{\mathrm{open}}|\), there is an exact algorithm with running time
\(2^k\operatorname{poly}(m,\tau,L)\).
Consequently, the divisible problem is polynomial-time solvable for a constant number of prescribed open hospitals, including four. This differs from the discrete fixed-open hardness in [Boehmer–Heeger, Theorem 3](https://arxiv.org/pdf/2009.14171).
The hardness proof below uses a gadget whose stability conditions force exactly two allocations, despite allowing arbitrary real masses.
Let \(F\subseteq H_{\mathrm{open}}\) be a guessed set of full hospitals. Retain all assignment and quota constraints, and impose
\(s_h=u_h\quad(h\in F),\qquad D_h(x)=0\quad(h\in H_{\mathrm{open}}\setminus F).\)
Introduce a variable \(\delta\), impose \(0\le\delta\le1\), and impose
\(D_h(x)+\delta\le\ell_h\quad(h\notin H_{\mathrm{open}}).\)
Maximize \(\delta\) by rational linear programming. Accept this branch exactly when its optimum is positive.
Soundness. A solution with \(\delta>0\) satisfies every closed-hospital condition strictly. Every open hospital is either forced full or has zero demand. Thus the assignment is stable. Hospitals outside \(F\) are allowed to be full as well; this does not affect soundness.
Completeness. Given a stable assignment, choose \(F\) to be its actual set of full open hospitals. Every other open hospital has zero demand. If there are closed hospitals, their finitely many strict inequalities have a positive minimum margin; choose \(\delta\) to be the smaller of that margin and one. If there are no closed hospitals, choose \(\delta=1\). Hence this branch has positive optimum.
Each branch has at most \(\tau(k+1)+1\) variables: acceptable open assignment variables, unmatched variables, and \(\delta\). It has \(O(\tau+m)\) constraints apart from nonnegativity bounds, and its encoding length is polynomial in \(m,\tau,L\). Exact rational linear programming therefore solves each branch in polynomial bit complexity. Enumerating all \(2^k\) branches gives the stated running time.
For membership in \(\mathrm{NP}\), a verifier can guess \(F\) and solve its linear program in polynomial time. Alternatively, there is a polynomial-size rational assignment certificate: the branch polytope is bounded because \(0\le x_{t,g}\le\mu_t\) and \(0\le\delta\le1\); a positive optimum is attained at a rational vertex of polynomial encoding length, by the determinant bounds underlying Cramer’s rule.
We first describe a polynomial transformation of ordinary three-literal conjunctive normal form satisfiability.
For a variable with \(d\) literal occurrences, introduce separate copies \(y_1,\ldots,y_d\), one for each occurrence, retaining its sign. When \(d\ge2\), add the cyclic implication clauses
\((\neg y_j\lor y_{j+1})\quad(j=1,\ldots,d),\qquad y_{d+1}=y_1.\)
These clauses force all copies to have the same truth value: if any copy is true, successive implications force every copy true; otherwise all are false. Thus satisfiability is preserved in both directions.
Each copy appears once in an original clause, once positively in the implication cycle, and once negatively in that cycle. Consequently, each variable appears at most twice positively and at most twice negatively. Every clause has two or three literals on distinct copy variables. For \(d=1\), no implication clause is needed.
It follows that satisfiability remains \(\mathrm{NP}\)-hard for formulas with these properties. Let such a formula have variables \(y_1,\ldots,y_n\) and clauses \(C_1,\ldots,C_p\), where clause \(C_j\) has \(r_j\in\{2,3\}\) literals. We may assume \(n\ge1\).
We describe masses and quotas in unnormalized units, whose total mass will be \(6n\). At the end, divide every mass and quota by \(6n\).
For each variable \(y_i\), create four prescribed open hospitals \(c_i,d_i,a_i,b_i\), with quotas:
| Hospital | Lower quota | Upper quota |
|---|---:|---:|
| \(c_i\) | \(2\) | \(2\) |
| \(d_i\) | \(1\) | \(1\) |
| \(a_i\) | \(1\) | \(2\) |
| \(b_i\) | \(1\) | \(2\) |
Create four types:
| Type | Mass | Acceptable open hospitals |
|---|---:|---|
| \(t_i^+\) | \(2\) | \(c_i,a_i,d_i\) |
| \(t_i^-\) | \(2\) | \(c_i,b_i,d_i\) |
| \(e_i^a\) | \(1\) | \(a_i\) |
| \(e_i^b\) | \(1\) | \(b_i\) |
For each clause \(C_j\), create a prescribed closed hospital \(h_j\), with lower and upper quotas both equal to \(r_j\).
The additional acceptabilities and preferences are:
All acceptable hospitals are preferred to \(\bot\). Hospitals accept exactly the types listing them and are indifferent among those types.
The instance has
\(m=4n+p,\qquad \tau=4n,\qquad |H_{\mathrm{open}}|=4n.\)
Each core type accepts at most five hospitals because its associated literal occurs in at most two clauses. Each open hospital accepts two types, and each clause hospital accepts at most three types.
Fix a variable \(y_i\), and consider any feasible assignment satisfying stability at the open hospitals. All four types belonging to this variable can be assigned only within its four open hospitals or to \(\bot\): clause hospitals are prescribed closed.
Their total mass is \(6\), while feasibility forces
\(s_{c_i}=2,\qquad s_{d_i}=1.\)
At most one of \(a_i,b_i\) is full. If both were full, their four hospitals would receive total mass
\(2+1+2+2=7>6,\)
which is impossible.
At least one of \(a_i,b_i\) is full. Hospital \(d_i\) receives mass one from the two core types. Hence at least one core type has positive mass at \(d_i\). That type prefers its choice hospital, \(a_i\) or \(b_i\), to \(d_i\), giving positive demand there. Open-hospital stability forces that choice hospital to be full.
Thus exactly one choice hospital is full.
Suppose \(a_i\) is full. Then \(b_i\) is underfull, so \(D_{b_i}(x)=0\). Every unmatched unit of \(e_i^b\) would contribute to this demand; therefore all its mass one is assigned to \(b_i\). Likewise, type \(t_i^-\) can have mass only at \(c_i\) or \(b_i\), since both \(d_i\) and \(\bot\) are worse than \(b_i\).
The total assigned mass is at least
\(s_{c_i}+s_{d_i}+s_{a_i}+s_{b_i}\ge2+1+2+1=6.\)
Because the local population mass is exactly \(6\), equality holds. Consequently, \(s_{b_i}=1\), and no local mass is unmatched.
Hospital \(b_i\) is therefore occupied entirely by \(e_i^b\). Type \(t_i^-\) must put all its mass two at \(c_i\), filling that hospital. Type \(t_i^+\) consequently puts no mass at \(c_i\). The dedicated type \(e_i^a\) puts its mass one at \(a_i\), leaving exactly one unit there for \(t_i^+\). Its remaining unit goes to \(d_i\).
The case where \(b_i\) is full is symmetric. Hence the only possible allocations are:
| Type | \(a_i\) full | \(b_i\) full |
|---|---|---|
| \(t_i^+\) | Mass \(1\) at each of \(a_i,d_i\) | Mass \(2\) at \(c_i\) |
| \(t_i^-\) | Mass \(2\) at \(c_i\) | Mass \(1\) at each of \(b_i,d_i\) |
| \(e_i^a\) | Mass \(1\) at \(a_i\) | Mass \(1\) at \(a_i\) |
| \(e_i^b\) | Mass \(1\) at \(b_i\) | Mass \(1\) at \(b_i\) |
Both allocations satisfy open-hospital stability. The hospitals \(c_i,d_i\) and the selected choice hospital are full. At the remaining choice hospital, its dedicated type is assigned there, and its core type is entirely at the preferred hospital \(c_i\); hence its demand is zero.
Define the encoded truth value by
\(y_i=\mathrm{false}\ \Longleftrightarrow\ a_i\text{ is full},\qquad y_i=\mathrm{true}\ \Longleftrightarrow\ b_i\text{ is full}.\)
This argument applies to arbitrary real assignment masses. It rules out every fractional intermediate state.
Consider a literal \(y_i\) in clause \(C_j\). Its reporting type is \(t_i^+\). Hospital \(h_j\) lies below both \(c_i,a_i\), and above \(d_i\), in this type’s ranking.
If \(y_i\) is true, the reporting type is entirely at \(c_i\), contributing zero to \(D_{h_j}\). If \(y_i\) is false, it has one unit at \(a_i\) and one at \(d_i\), contributing exactly one unit.
Similarly, the reporting type \(t_i^-\) contributes exactly one unit for a false negative literal, and zero for a true negative literal. Dedicated types do not accept clause hospitals.
Therefore, in unnormalized units,
\(D_{h_j}(x)=\bigl|\{\text{false literals in }C_j\}\bigr|.\)
The closed-hospital stability condition is
\(D_{h_j}(x)<r_j.\)
Since the clause contains exactly \(r_j\) literals, this inequality holds precisely when at least one literal is true. Equality, which occurs when every literal is false, is correctly rejected.
Satisfiable formula implies stable assignment. Choose the corresponding gadget allocation for each variable. Section 4 verifies feasibility and open-hospital stability. Every clause has a true literal, so Section 5 verifies all closed-hospital inequalities.
Stable assignment implies satisfiable formula. Section 4 forces every variable gadget into one of its two states, defining a Boolean assignment. Stability of each closed clause hospital then implies that its clause has a true literal.
Finally, divide every mass and quota by \(6n\). The resulting masses sum to one, and every quota remains a positive binary rational. Loads and demands scale by the same positive factor, so feasibility, fullness, zero demand, and every strict closed-hospital inequality are preserved in both directions.
All normalized numbers have numerators bounded by three and denominator \(6n\), hence \(O(\log n)\) bits. With the bounded preference lists, the constructed input has
\(L=O((n+p)\log(n+p)).\)
The construction is therefore a polynomial-time many-one reduction.
The reduction proves \(\mathrm{NP}\)-hardness, and Section 1 proves membership in \(\mathrm{NP}\). Thus the exact divisible-mass decision problem is \(\mathrm{NP}\)-complete.
Its exact running-time upper bound is
\(2^{|H_{\mathrm{open}}|}\operatorname{poly}(m,\tau,L)\subseteq2^m\operatorname{poly}(m,\tau,L).\)
In particular, a constant number of prescribed open hospitals is tractable, while unrestricted instances are \(\mathrm{NP}\)-hard.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem. The reduction remains valid for arbitrary real masses, and the linear-programming argument establishes membership in \(\mathrm{NP}\) and the stated running time. I found no major or minor mathematical issues.
For each prescribed open hospital, feasibility gives \(s_h\le u_h\). Its stability condition is therefore equivalent to the disjunction \(s_h=u_h\) or \(D_h(x)=0\). The branch indexed by \(F\) correctly selects these alternatives.
Branch soundness is valid even when hospitals outside \(F\) happen to be full: imposing zero demand there is sufficient for stability.
Branch completeness is also valid. Selecting the actual full hospitals imposes zero demand only where stability requires it. For the closed hospitals, finitely many strictly positive margins \(\ell_h-D_h(x)\) have a strictly positive minimum. Consequently, a common positive \(\delta\) exists. The separate treatment of no closed hospitals is correct.
Thus a stable assignment exists exactly when some feasible branch has positive optimum. Infeasible branches necessarily cannot accept.
The variable bound \(\tau(k+1)+1\) is correct: each type needs at most \(k\) acceptable open-hospital variables, one unmatched variable, and the LP has one common slack variable.
There are \(O(\tau+m)\) constraints excluding nonnegativity. All coefficients and right-hand sides are rational, and the encoding length is polynomial in \(m,\tau,L\). The invoked polynomial bit-complexity result for rational linear programming applies, including infeasibility detection and exact comparison of the optimum with zero.
Enumerating the \(2^k\) subsets therefore gives the claimed bound
\(2^k\operatorname{poly}(m,\tau,L)\).
Guessing \(F\) and deciding its LP in polynomial time is a valid \(\mathrm{NP}\) verification procedure. The alternative rational-certificate argument is sound as well: all assignment variables and \(\delta\) are bounded, so a feasible branch is a compact rational polytope; a positive maximum has an optimal vertex with polynomial encoding length.
The occurrence-copy transformation preserves satisfiability in both directions. For \(d\ge2\), the directed implication cycle forces every copy to have the same Boolean value. For \(d=1\), no consistency constraint is necessary.
Each copy occurs once in an original clause, once positively in the cycle, and once negatively in the cycle. Depending on its original sign, its positive and negative occurrence counts are therefore at most two each.
Original clauses use distinct occurrence copies, even if the original formula repeated a variable. The implication clauses also use distinct copies, including when \(d=2\). Hence the claimed clause sizes and distinct-variable condition hold. The transformation has polynomial size.
Each gadget has total mass \(2+2+1+1=6\). Its types can be assigned only to its own open hospitals or to \(\bot\), because every additional acceptable hospital is prescribed closed. Types from other gadgets cannot enter its open hospitals.
The counts \(m=4n+p\), \(\tau=4n\), and \(k=4n\) are correct. Every core type accepts three open hospitals and at most two clause hospitals, giving at most five acceptable hospitals. Every open hospital accepts exactly two types; each clause hospital accepts at most three types because its literals use distinct variables.
All specified preference lists are strict, and every quota satisfies \(0<\ell_h\le u_h\).
Each step forcing the two allocations is valid:
The symmetric case is valid. Both resulting allocations meet the quotas and have zero demand at the sole underfull open hospital. The reasoning uses nonnegativity, mass conservation, and positive demand, without any integrality assumption. It therefore excludes fractional intermediate states as claimed.
For a positive literal, the corresponding clause hospital lies below \(c_i,a_i\) and above \(d_i\). The reporting type consequently contributes zero when the literal is true and exactly one unnormalized unit when it is false. The negative-literal calculation is symmetric.
No dedicated type contributes, and no mass can be assigned to any closed clause hospital. The ordering among clause hospitals therefore does not affect this calculation.
Hence \(D_{h_j}(x)\) equals the number of false literals in the clause. Since \(\ell_{h_j}=r_j\), the strict condition \(D_{h_j}(x)<r_j\) holds exactly when the clause is satisfied. In particular, the all-false equality case is correctly rejected.
Both directions of the reduction follow from the verified gadget and clause calculations.
Dividing every mass and quota by \(6n>0\) gives total population mass one and preserves loads, demands, fullness, and strict inequalities under a common positive scaling. The normalized rational numbers have \(O(\log n)\) encoding length, and the bounded lists give the stated polynomial input-size bound.
Thus the reduction proves \(\mathrm{NP}\)-hardness under both advertised acceptability restrictions. Together with membership in \(\mathrm{NP}\), it proves \(\mathrm{NP}\)-completeness.
The polynomial-time consequence for constant \(k\), including four prescribed open hospitals, follows directly from the algorithm. The cited discrete comparison also matches [Boehmer–Heeger, Theorem 3](https://arxiv.org/pdf/2009.14171), which concerns prescribed four-open-hospital instances.
No repair or additional clarification is needed. The unrestricted divisible-mass problem is proved \(\mathrm{NP}\)-complete, with an exact algorithm running in \(2^{|H_{\mathrm{open}}|}\operatorname{poly}(m,\tau,L)\).
⟨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.