Answer: polynomial-time solvable (in \(P\))
Theorem 1.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe CUM-SIGN-Q problem is NP-hard even when preferences of all applicants are strict and 𝑞(𝑝) = 1 for every post 𝑝∈𝑃. The CUM-SIGN-Q problem admits a randomized polynomial time algorithm when the number of ranks is 𝑂(1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite posts \(P\), finite applicant types \(T\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), rational normalized capacities \(q_p\), strict preference and eligibility data assigning each eligible pair \((t,p)\) a rank \(r_t(p)\in\{1,\ldots,r\}\), and a target signature \(\rho=(\rho_1,\ldots,\rho_{r+1})\), decide whether there exist masses \(x_{t,p}\ge0\) and unmatched masses \(u_t\ge0\) such that \(\sum_p x_{t,p}+u_t=\mu_t\), \(\sum_t x_{t,p}\le q_p\), \(z_j=\sum_{t,p:r_t(p)=j}x_{t,p}\), \(z_{r+1}=\sum_tu_t\), and \(\sum_{j=1}^{\ell}z_j\ge\sum_{j=1}^{\ell}\rho_j\) for every \(\ell\); output such an allocation if one exists.
Given finite sets of posts \(P\) and applicant types \(T\), rational type masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), rational post capacities \(q_p\), and eligible type--post pairs with strict ranks \(r_t(p)\in\{1,\ldots,r\}\), an allocation consists of \(x_{t,p}\ge0\) and \(u_t\ge0\). It is feasible when \(\sum_p x_{t,p}+u_t=\mu_t\) for every \(t\) and \(\sum_t x_{t,p}\le q_p\) for every \(p\).
Its signature is \(z=(z_1,\ldots,z_{r+1})\), where \(z_j=\sum_{t,p:r_t(p)=j}x_{t,p}\) for \(j\le r\), and \(z_{r+1}=\sum_tu_t\). For a rational target signature \(\rho\), \(z\) is cumulatively at least \(\rho\) if \(\sum_{j=1}^{\ell}z_j\ge\sum_{j=1}^{\ell}\rho_j\) for every \(\ell\in\{1,\ldots,r+1\}\).
Is deciding whether such a feasible allocation exists, and producing one when it does, NP-hard or in \(P\)?
For indivisible applicants with fixed quotas, the analogous cumulative-signature matching problem is NP-hard even with unit post quotas and strict preferences.
No verified result is recorded here for this exact distributional formulation.
The distributional cumulative-signature problem is polynomial-time solvable. Moreover, whenever a feasible allocation exists, an exact rational allocation can be produced in polynomial time.
Let \(E\subseteq T\times P\) be the set of eligible type–post pairs, and define the cumulative targets
\[ R_\ell=\sum_{j=1}^{\ell}\rho_j \]
for every \(\ell\in\{1,\ldots,r+1\}\).
Use one variable \(x_{t,p}\) for every \((t,p)\in E\), and one variable \(u_t\) for every \(t\in T\). Consider the following rational linear system.
For every type \(t\),
\[ \sum_{p:(t,p)\in E}x_{t,p}+u_t=\mu_t. \]
For every post \(p\),
\[ \sum_{t:(t,p)\in E}x_{t,p}\le q_p. \]
For every \(\ell\in\{1,\ldots,r\}\),
\[ \sum_{\substack{(t,p)\in E\\r_t(p)\le\ell}}x_{t,p}\ge R_\ell. \]
Finally,
\[ x_{t,p}\ge0,\qquad u_t\ge0. \]
The cumulative constraint for \(\ell=r+1\) can be checked separately as
\[ 1\ge R_{r+1}. \]
Indeed, summing all type-mass equalities gives
\[ \sum_{(t,p)\in E}x_{t,p}+\sum_{t\in T}u_t =\sum_{t\in T}\mu_t=1. \]
Thus every feasible allocation has total signature mass exactly \(1\).
For \(\ell\le r\), the definition of the signature gives
\[ \sum_{j=1}^{\ell}z_j = \sum_{j=1}^{\ell} \sum_{\substack{(t,p)\in E\\r_t(p)=j}}x_{t,p} = \sum_{\substack{(t,p)\in E\\r_t(p)\le\ell}}x_{t,p}. \]
Consequently, the linear inequality indexed by \(\ell\) is exactly the cumulative-signature requirement
\[ \sum_{j=1}^{\ell}z_j\ge\sum_{j=1}^{\ell}\rho_j. \]
For \(\ell=r+1\),
\[ \sum_{j=1}^{r+1}z_j=1, \]
so the last cumulative condition is exactly \(1\ge R_{r+1}\).
Therefore:
Hence the original problem is precisely rational linear feasibility.
The linear system has
\[ |E|+|T| \]
variables and \(O(|T|+|P|+r+|E|)\) constraints, counting nonnegativity constraints. Its coefficients are \(0\), \(1\), or \(-1\), while its right-hand sides are rational numbers obtained from the input by polynomially many rational additions.
Under the standard binary encoding of rational numbers, rational linear-program feasibility is decidable in time polynomial in the number of variables, the number of constraints, and the total coefficient bit length. The applicable theorem also returns an exact rational feasible point when one exists.
There is no output-size obstruction here. Every feasible variable satisfies
\[ 0\le x_{t,p}\le\mu_t,\qquad 0\le u_t\le\mu_t, \]
so the feasible region is bounded. If it is nonempty, it has a vertex. A vertex is determined by a nonsingular square subsystem of rational equalities. Cramer’s rule together with the determinant bit-size bound shows that its coordinates have bit length polynomial in the input length. Thus an exact rational allocation of polynomial encoding length exists and can be produced by an exact rational LP algorithm.
Because \(\rho\) explicitly contains \(r+1\) coordinates, constructing all \(r\) cumulative inequalities is polynomial in the stated input size.
The indivisible hardness result does not transfer: indivisibility imposes implicit integrality constraints, whereas the distributional formulation permits arbitrary splitting of each type mass and all its requirements are linear.
Thus the exact distributional feasibility-and-construction problem is in \(P\). In particular, it is not an NP-hardness analogue of the indivisible problem unless \(P=NP\).
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces the distributional problem to rational linear-program feasibility. The formulation is equivalent to the requested cumulative-signature constraints, has polynomial encoding length, and supports exact rational construction in polynomial time.
No mathematical gap affecting the conclusion was found.
The variables \(x_{t,p}\) are introduced exactly for eligible pairs, with \(u_t\) for each type. The type-mass equalities and post-capacity inequalities coincide with the definition of feasibility. Nonnegativity is explicitly imposed.
The identity
\[ \sum_{j=1}^{\ell}z_j = \sum_{\substack{(t,p)\in E\\r_t(p)\le\ell}}x_{t,p} \]
follows directly from the strict rank assignments \(r_t(p)\in\{1,\ldots,r\}\). Therefore each displayed LP inequality is exactly the corresponding cumulative-signature condition.
Summing the type-mass equalities gives
\[ \sum_{(t,p)\in E}x_{t,p}+\sum_tu_t=1. \]
Since the signature counts every assigned mass at its rank and all unassigned mass in coordinate \(r+1\), this proves
\[ \sum_{j=1}^{r+1}z_j=1. \]
Thus the condition at \(\ell=r+1\) is indeed equivalent to \(1\ge R_{r+1}\). Checking this scalar condition separately is valid.
Both directions are established:
No integrality condition is present in the distributional formulation, so no omitted discrete constraint undermines this equivalence.
There are \(|E|+|T|\) variables and polynomially many constraints. Constructing \(R_\ell\) and the cumulative coefficient rows requires polynomially many rational operations. Their binary encoding lengths remain polynomial in the total input length.
The observation that \(\rho\) explicitly has \(r+1\) coordinates correctly prevents a hidden exponential dependence on a compactly encoded \(r\).
Rational linear-program feasibility is solvable in polynomial time in the Turing model. Standard exact postprocessing can return a rational feasible point of polynomial encoding length.
The supplementary output-size argument is sound: the type equations and nonnegativity imply
\[ 0\le x_{t,p}\le\mu_t,\qquad 0\le u_t\le\mu_t, \]
so the feasible polyhedron is bounded. A nonempty bounded rational polyhedron has a vertex, and standard determinant bounds give polynomial coordinate bit length.
The conclusion that the problem lies in \(P\), including production of an exact rational allocation, follows. The comparison with the indivisible problem is also accurate: the cited hardness does not transfer merely from the indivisible model because its integrality requirement is absent here.
⟨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.