Answer: Polynomial-time solvable (\(\mathrm{P}\)).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven S, C, R, p, and q, checking whether a feasible matching exists or not is NP-complete. This holds even for the case where (i) there exist only maximum quotas, or (ii) there exist only minimum quotas.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite school set \(C\), a listed family of regions \(R\subseteq 2^C\), and rational lower-quota fractions \(p_r\), does a nonatomic unit-mass population of one feasibility-relevant type admit an assignment to schools in which each individual receives one whole school place and every region \(r\) receives at least mass \(p_r\)?
Let \(C\) be a nonempty school set with \(m=|C|\), and let \(R\subseteq 2^C\setminus\{\varnothing\}\) be explicitly listed, with arbitrary overlaps and binary rational lower-quota fractions \(p_r\in[0,1]\). Every school is acceptable to every individual; there are no binding upper quotas.
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=1\) and its mass is \(1\); support size means listed positive-mass types, not the number of possible types.
Represent the nonatomic population by \([0,1]\) with Lebesgue measure \(\lambda\). An assignment is a measurable map \(a:[0,1]\to C\): every individual receives exactly one school place, and individuals of the same type may attend different schools. It is feasible when \(\lambda(a^{-1}(r))\ge p_r\) for every \(r\in R\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,|R|,L\).
Is deciding whether a feasible assignment exists solvable in polynomial time in \(m,\tau,|R|,L\), or is it NP-hard?
For a finite population with all schools acceptable, feasibility with arbitrary overlapping regions is NP-complete even when only minimum quotas are imposed ([Goto et al., 2014](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p1225.pdf)). No result settling exactly the continuous problem above was located in the literature search.
The continuous feasibility problem is polynomial-time solvable. The essential point is that individuals of the single type may attend different schools: every nonnegative school-mass vector summing to \(1\) can be realized by a measurable assignment.
Enumerate the schools as \(C=\{c_1,\ldots,c_m\}\), and write \(k=|R|\). Consider the following rational linear feasibility problem in \(m\) real variables:
\(x_i\ge 0\quad (1\le i\le m),\)
\(\displaystyle \sum_{i=1}^{m}x_i=1,\)
\(\displaystyle \sum_{\{i:c_i\in r\}}x_i\ge p_r\quad (r\in R).\)
We prove that this system is feasible if and only if the assignment problem is feasible.
Let \(a:[0,1]\to C\) be a feasible measurable assignment, and define
\(x_i=\lambda(a^{-1}(\{c_i\})).\)
Each coordinate is nonnegative. Because every individual receives exactly one school, the measurable sets \(a^{-1}(\{c_i\})\) form a partition of \([0,1]\). Finite additivity of Lebesgue measure therefore gives
\(\displaystyle \sum_{i=1}^{m}x_i=\lambda([0,1])=1.\)
For each region \(r\), its preimage is the disjoint union of the preimages of its schools. Hence
\(\displaystyle \sum_{\{i:c_i\in r\}}x_i=\lambda(a^{-1}(r))\ge p_r.\)
Thus the vector satisfies every constraint.
Conversely, suppose \(x\) satisfies the linear system. Define cumulative sums
\(s_0=0,\qquad s_i=\sum_{j=1}^{i}x_j\quad (1\le i\le m).\)
Nonnegativity and normalization imply
\(0=s_0\le s_1\le\cdots\le s_m=1.\)
For each \(i\), assign every individual in the half-open interval \([s_{i-1},s_i)\) to \(c_i\). Assign the endpoint \(1\) to \(c_m\).
These intervals partition \([0,1)\); zero-length intervals are simply empty. Thus the rule defines an assignment on all of \([0,1]\). Every school preimage is an interval, possibly with the singleton endpoint added, so the assignment is measurable. Since a singleton has measure zero,
\(\lambda(a^{-1}(\{c_i\}))=s_i-s_{i-1}=x_i.\)
Consequently, for every region,
\(\displaystyle \lambda(a^{-1}(r))=\sum_{\{i:c_i\in r\}}x_i\ge p_r.\)
All schools are acceptable, and there are no binding upper quotas, so there are no additional assignment restrictions to check. The assignment is feasible. This proves the equivalence.
We use the standard rational linear-programming theorem: feasibility of an explicitly given system of rational linear inequalities can be decided exactly in time polynomial in its dimensions and total binary encoding length. This is the polynomial-time solvability established by [Khachiyan](https://www.mathnet.ru/eng/dan42319). The theorem concerns exact feasibility, including systems whose feasible set has empty interior.
To apply it, replace the normalization equality by two inequalities. The resulting system has:
Thus every coefficient is rational and explicitly available, as the theorem requires.
A dense encoding of this system has binary length
\(B=O\!\left(L+m(k+m+2)\right).\)
The bound accounts for the input quota encodings and the additional constant-size matrix entries. Constructing this encoding takes polynomial time in the same parameters.
If \(T_{\mathrm{LP}}(n,h,B)\) denotes the running time of a fixed polynomial-time rational linear-feasibility algorithm, the total running time is bounded by
\(O(B)+T_{\mathrm{LP}}(m,k+m+2,B).\)
In particular, it is
\((m+\tau+|R|+L)^{O(1)},\qquad \tau=1.\)
The type description contributes only to reading the input; feasibility uses the school masses alone. Arbitrary overlaps merely determine the zero-one coefficients of the regional constraints.
Therefore the decision problem belongs to \(\mathrm{P}\). An NP-hardness result for this exact problem, under polynomial-time reductions, would imply \(\mathrm{P}=\mathrm{NP}\).
The cited finite-population result establishes NP-completeness even with only minimum quotas ([Goto et al., Theorem 2](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p1225.pdf)). Finite students impose integrality restrictions on school counts. The continuous model imposes no such restriction, as the interval construction proves.
A concrete example demonstrates the distinction. Let
\(C=\{c_1,c_2,c_3,c_4\},\qquad R=\{r\subseteq C:|r|=2\},\qquad p_r=\tfrac12\quad(r\in R).\)
The continuous vector \(x_i=\tfrac14\) is feasible: every two-school region receives mass \(\tfrac12\).
Now consider two finite students, with minimum quota one student in every two-school region. These are exactly the same quotas after normalization by population size. Any assignment occupies at most two schools. At least two schools are therefore empty, and their pair is a listed region receiving zero students. The finite instance is infeasible.
Thus continuous feasibility is exactly rational linear feasibility, while the finite model requires integral school counts.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated continuous feasibility problem with a correct polynomial-time decision procedure. No major or minor issues were found.
The proof uses the intended model: \(\tau=1\), total population mass \(1\), every individual receives exactly one school, and individuals of the same type may attend different schools. It imposes neither integrality nor an unstated restriction that a type must attend a single school.
The variables \(x_i\) represent school masses. The proposed system includes exactly the required conditions: nonnegativity, total mass \(1\), and every regional lower quota. Arbitrary overlaps introduce no additional assignment restrictions.
Every singleton school preimage is measurable because the assignment is measurable into the finite school set. These preimages are pairwise disjoint and cover \([0,1]\), since the assignment is a function defined everywhere.
Consequently, finite additivity gives both the normalization and the regional identities:
\(\sum_{i=1}^{m}x_i=1\) and
\(\lambda(a^{-1}(r))=\sum_{\{i:c_i\in r\}}x_i\).
The feasibility inequalities therefore transfer correctly. No independence or disjointness of the regions is assumed or needed.
The cumulative sums are nondecreasing, start at \(0\), and end at \(1\). Thus the half-open intervals in the construction partition \([0,1)\), including when some coordinates vanish.
Assigning the endpoint \(1\) to \(c_m\) is valid because the task assumes \(m\ge1\). Each school preimage is measurable, and adding the endpoint changes no measure. The resulting school masses are exactly \(x_i\), so all regional inequalities hold.
The construction establishes existence for every feasible real vector; it does not require the vector to be rational. This is sufficient for the stated decision problem.
The theorem invoked is stated with the necessary precision: exact feasibility of an explicitly encoded rational system of linear inequalities is decidable in polynomial time in its dimensions and binary encoding length. This standard theorem applies to lower-dimensional feasible sets as well, so the normalization equality causes no interior-point assumption.
After replacing that equality by two inequalities, the stated dimensions are correct:
Every hypothesis of the invoked theorem is satisfied. No strict inequalities, irrational input data, or implicit exponentially large constraint family appears.
The dense matrix has \(m(k+m+2)\) entries of constant binary size. The quota encodings are already counted in \(L\); the additional constants and structural encoding fit the claimed bound
\(B=O(L+m(k+m+2))\).
Because the regions are explicitly listed, their incidence rows can be constructed in polynomial time. The expression
\(O(B)+T_{\mathrm{LP}}(m,k+m+2,B)\)
therefore yields the claimed running time
\((m+\tau+|R|+L)^{O(1)}\), with \(\tau=1\).
The task requests polynomial dependence on these parameters, not a particular polynomial exponent, so the stated bound meets the requirement. The conclusion that NP-hardness under polynomial-time reductions would imply \(\mathrm{P}=\mathrm{NP}\) is also correct.
The argument covers all permitted boundary cases:
No missing edge case affects the result.
The attribution to Goto et al. is accurate: Theorem 2 states NP-completeness even when only minimum quotas exist, and the paper’s model assumes universal acceptability. [Goto et al., 2014](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p1225.pdf).
The illustrative computation is correct. With four schools and all two-school regions, masses \(1/4\) give regional masses \(1/2\). Two finite students occupy at most two schools, leaving at least two empty schools whose listed pair violates its minimum quota of one student.
This comparison correctly illustrates the integrality distinction. The continuous classification is independently established by the preceding equivalence and polynomial-time theorem.
Repair feedback: None required.
⟨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.