Answer: —
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Quest Draft is a deterministic polynomial- time course allocation algorithm.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite course catalog \(C\), rational per-capita capacities \(\kappa_c\), and a finite set of student types \(T\) with rational masses \(\mu_t\) summing to \(1\), compute the mass \(x_{t,B}\) of each type receiving each bundle \(B\). Each type records its wishlist, caveats, and priority cohort; the cohorts follow the four round orders of the cyclically shifted snake draft. Apply the draft with integral bundles for each individual, splitting a type's mass when a course reaches capacity and applying the paper's rollback rule to if-and-only-if caveats.
Let \(C\) be a catalog of \(m\geq1\) course offerings, each with a fixed block in \(\{1,2,3,4\}\), an underlying course identifier, and nonnegative binary-rational capacity \(\kappa_c\). A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each type specifies a strict wishlist, a priority cohort, and a conjunction of caveats: \(|B\cap S|\leq r\), where \(S\subseteq C\) and \(r\in\{0,\ldots,4\}\), or \(c\in B\Longleftrightarrow d\in B\), where \(c\ne d\).
Represent each cohort by an interval carrying Lebesgue mass, with types occupying consecutive subintervals in input order. Process cohorts in their supplied priority order, completing all four rounds of one before starting the next. Within a cohort, using normalized coordinate \(u\in[0,1)\), the round orders are increasing \(u\), decreasing \(u\), increasing \((u+\tfrac12)\bmod1\), and the reverse of the third order.
Initially partition at type boundaries and cohort midpoints. Retain every subsequent split, without merging cells. Each cell has a common assignment and deletion history; process cells in the current round order. At its turn, give its members their highest eligible wishlist offering, splitting off the leading subinterval if residual capacity is insufficient. The remaining subinterval continues its turn with the exhausted offering unavailable. Each member receives an integral bundle, with at most one offering per block and at most one offering of each underlying course; eligibility also enforces every at-most caveat. A turn with no eligible offering is skipped.
Before each cell's turn, exclude both members of an if-and-only-if pair if neither is held and either is unavailable. If exactly one is held and the other is unavailable, backtrack; also backtrack for an unsatisfied pair after that cell's fourth turn. Resolve simultaneous failures by input caveat order. Permanently delete the failed pair for precisely that cell, undo its earliest selection of either member and every chronologically subsequent selection throughout the draft, restore capacities and other transient state, and replay from that position. Permanent deletions and cell boundaries survive every rollback; exclusions caused solely by current assignments or capacities are recomputed.
Compute exactly all nonzero bundle masses \(x_{t,B}\), where \(B\subseteq C\) is a final integral bundle and \(x_{t,B}\) is the mass of type \(t\) receiving it. Let \(q\) be the total number of caveats and \(L\) the total binary input length.
Is this mass-allocation function computable in time polynomial in \(m,\tau,q,L\), or is it NP-hard?
For an explicitly listed society of \(n\) students, the deterministic wishlist draft with caveat backtracking has a verified \(O(n^5)\) bound when \(m=O(n)\). [Hoshino and Raible-Clark](https://www.khoury.northeastern.edu/home/rhoshino/papers/quest1.pdf)
No complexity result for this exact interval-mass rollback convention was located.
The general complexity classification remains unresolved. I prove two additional results concerning the final masses:
The first result allows arbitrary catalogs, wishlists, at-most caveats, and supported societies.
I first establish the facts needed to justify reasoning about the completed execution.
Write all input masses and capacities as fractions with positive integer denominators $b_1,\ldots,b_s$, and define
$$
D=2\prod_{i=1}^{s}b_i.
$$
Its binary length is $O(L)$.
Concatenate the cohort intervals into an absolute mass coordinate on $[0,1)$. Each interval’s length is its Lebesgue mass.
Every retained boundary and every residual capacity is an integer multiple of $1/D$.
Proof. Each input mass is a multiple of $1/D$, and its numerator when expressed with denominator $D$ is even. Thus type boundaries, cohort boundaries, and cohort midpoints lie on this grid.
Within each half of a cohort, every prescribed round order is monotone. The shifted third order introduces only the already present midpoint discontinuity.
Initially, capacities are grid multiples. A whole-cell allocation subtracts a grid-aligned mass. If a cell $[a,b)$ is split because the positive residual capacity is $\rho<b-a$, its new boundary is either $a+\rho$ or $b-\rho$, according to the processing direction. Both are grid points.
Rollback restores previously attained capacity values and retains existing boundaries. Induction proves the assertion. $\square$
Consequently, there are at most $D$ positive-mass cells.
There are at most $Dq$ backtracks.
Proof. Use the $D$ fixed intervals of length $1/D$ as bookkeeping atoms. For each atom and each if-and-only-if caveat of its type, record whether that caveat has failed for a cell containing the atom.
A failure adds at least one previously absent record. Indeed, if that pair had already failed for an atom in the failing cell, both offerings would remain permanently deleted for that atom. The earlier rollback would have removed its selections of those offerings, and it could not subsequently select either. It therefore could not now hold exactly one member of the pair.
The cell has a common deletion history, so every atom in it receives a new record. Records survive rollback, and there are at most $Dq$ possible records.
Between backtracks, processing advances through the prescribed cohort and round orders. Splits increase the cell count, which is at most $D$. Hence each forward portion is finite, proving termination. $\square$
These atoms are an accounting device; this argument does not replace cell backtracking by individual-student backtracking.
An exact implementation can store the retained partition and chronological history. Each atom has at most four live selections, so refining live selection records at retained boundaries produces at most $4D$ records. Forward processing, suffix rollback, and replay therefore take time polynomial in $D,m,\tau,q,L$. All arithmetic can use denominator $D$, with $O(L)$-bit numerators. This gives an exact upper bound of
$$
2^{O(L)}.
$$
The requested output nevertheless has polynomial length. Each final bundle contains at most four offerings, so there are at most
$$
\tau\sum_{j=0}^{\min(4,m)}\binom{m}{j}=O(\tau m^4)
$$
possible nonzero entries. Every output mass is $a/D$ for some $0\leq a\leq D$, and thus has an $O(L)$-bit representation.
For a type $t$, let $W_t$ be its wishlist set. Define an undirected graph $G_t$ on the catalog: each if-and-only-if caveat contributes its edge $\{c,d\}$. Call a connected component linked if it contains an edge.
Ignoring capacities, call a set $B$ feasible for $t$ if:
These conditions imply $|B|\leq4$.
A linked component $K$ is statically impossible if no feasible set contains $K$.
A linked component $K$ is statically impossible exactly when at least one of the following holds:
Proof. Each listed obstruction persists in every superset of $K$.
Conversely, if none occurs, $K$ itself is feasible. Distinct blocks also imply $|K|\leq4$. Thus $K$ supplies the required feasible set containing it. $\square$
All these tests take polynomial time in the explicitly listed input.
Suppose that, for every supported type, every linked component of $G_t$ is statically impossible. Then all nonzero masses $x_{t,B}$ are computable in time polynomial in $m,\tau,q,L$.
Proof.
For each type $t$, let $R_t$ be the union of its linked components. Construct a reduced instance by:
I prove that the reduced instance has exactly the same final bundles, pointwise up to interval endpoints.
Step 1: the original final bundles avoid $R_t$.
At termination, every final bundle satisfies every if-and-only-if caveat: an unsatisfied pair at the fourth turn would cause another backtrack.
If a final bundle contains one vertex of a linked component $K$, equality along the edges propagates through every path in $K$. It must therefore contain all of $K$. Static impossibility rules this out. Hence
$$
B\cap R_t=\varnothing
$$
for every final bundle of type $t$.
Step 2: chronological rollback erases all effects of the forbidden selections.
Consider the final surviving execution trace. A rollback removes a chronological suffix and replays from its starting position. Thus every retained selection was made with exactly the retained selections preceding it as its assignment and capacity history.
Every selection of an offering in $R_t$ has disappeared from this final trace, by Step 1. Furthermore:
Neither operation directly removes an offering from the reduced wishlist.
At any retained choice, the assignments and capacities relevant to reduced offerings are therefore precisely those determined by the preceding retained choices. At-most eligibility agrees with the reduced instance, because no preceding retained assignment contains an offering forbidden for its recipient’s type.
Consequently, an original retained selection is the highest eligible reduced wishlist offering. A retained empty turn also has no eligible reduced offering: any such offering would have been eligible in the original turn.
This reasoning includes skipped turns. If a temporary selection had caused a later turn to skip, undoing that selection also rewound past the later turn. That skip could not survive solely because of the undone selection.
The final surviving trace therefore executes the reduced draft on the final retained refinement.
Step 3: refinement does not change a draft without backtracking.
For a draft without if-and-only-if caveats, subdividing a cell preserves its allocation. Its subdivisions encounter the same wishlist choice until the relevant capacity is exhausted; if exhaustion occurs, the boundary is at the same mass coordinate. The remaining portion then continues with the same residual capacities and eligibility.
Induction through the four round orders proves that arbitrary retained refinements leave the resulting pointwise allocation unchanged. This applies because all cells lie within the monotone pieces of those orders.
Thus the original final allocation equals the reduced allocation.
Step 4: the reduced draft is polynomial-time computable.
Let $g$ be the number of nonempty cohorts. Initially there are at most
$$
\tau+g\leq2\tau
$$
cells, including midpoint cuts.
Without backtracking, capacities never increase. Every proper capacity split exhausts one offering, and that offering cannot cause another proper split. There are therefore at most $m$ such splits and at most $2\tau+m$ retained cells.
Processing four rounds, checking the explicitly listed eligibility conditions, and aggregating masses takes polynomial time. Lemma 1 supplies polynomial arithmetic bit complexity. $\square$
This theorem genuinely includes instances with if-and-only-if caveats. For example, a type may require $a\Longleftrightarrow b$ while also imposing
$$
|B\cap\{a,b\}|\leq1.
$$
The pair can be selected temporarily by the original execution, but neither offering can occur in that type’s final bundle. The theorem permits removing both before computing the output.
Assume the catalog contains exactly two offerings, $a$ and $b$, in distinct blocks and with distinct underlying course identifiers.
Suppose every type:
Every subset of $\{a,b\}$ consequently satisfies its at-most caveats.
Consider one cohort of mass $M$, entered with residual capacities $A$ for $a$ and $B$ for $b$.
The cohort’s total final mass receiving $\{a,b\}$ is
$$
z=\min(M,A,B).
$$
This conclusion holds even when different types rank the offerings differently.
Proof. Write
$$
z_*=\min(M,A,B).
$$
A member whose pair has been permanently deleted remains empty: rollback removes its earliest selection of the pair, and permanent deletion prevents any subsequent selection.
Let $U$ be the region whose pair has not been permanently deleted, and let $s$ be its mass. Initially $s=M$.
Step 1: every failure has an exhausted partner.
Within a forward portion, capacities cannot increase.
An undeleted member who receives no offering during round one has encountered unavailability of at least one member of the pair. At subsequent turn starts, the neither-held rule continues to exclude both, so that member cannot acquire a first offering in a later round.
Thus every cell that can fail received its first offering in round one. Its partner is eligible whenever the partner has positive residual capacity: it is on the wishlist, lies in a distinct block, has a distinct underlying identifier, and satisfies every at-most caveat together with the first offering.
During round two, such a cell therefore receives its partner unless that capacity is exhausted. A remainder left by a partial partner allocation also faces zero partner capacity. Hence both the before-turn failure and any eventual fourth-turn failure occur with an exhausted partner.
This argument does not require an immediate failure check on the remainder of a split turn.
Step 2: permanent deletion cannot reduce $s$ below $z_*$.
Suppose a failing cell $F$ has mass $f>0$, holds $c$, and lacks its exhausted partner $d$. Let $K_d$ be the residual capacity of $d$ on entry to this cohort, so $K_d$ is either $A$ or $B$.
At that instant, exactly $K_d$ mass within the cohort holds $d$. Those recipients lie in $U$ and are disjoint from $F$. Therefore
$$
s\geq K_d+f.
$$
Deleting the pair on $F$ reduces the undeleted mass to
$$
s-f\geq K_d\geq z_*.
$$
Induction over failures proves
$$
s\geq z_*
$$
throughout the execution.
Step 3: termination attains the bottleneck.
At termination, every bundle is either empty or $\{a,b\}$. Let $z$ be the paired mass. Capacity and mass constraints give
$$
z\leq z_*.
$$
Suppose that $z<z_*$. Both final residual capacities are then positive:
$$
A-z>0,\qquad B-z>0.
$$
In the final surviving execution trace, capacities only decrease. Thus both were positive at every retained turn. Each member of $U$ had neither offering at its first turn, had no permanent pair deletion, and had an eligible wishlist offering. It therefore received an offering at that turn. Its retained selection belongs to its final bundle, which must be the pair.
Consequently every member of $U$ is finally paired, giving
$$
z=s\geq z_*,
$$
a contradiction. Hence $z=z_*$. $\square$
Earlier completed cohorts are unaffected by a later cohort’s rollback: the failed cell’s earliest selection belongs to its own cohort. Therefore this theorem applies successively in priority order.
Let the cohort masses in priority order be $M_1,\ldots,M_g$, and put
$$
K=\min(\kappa_a,\kappa_b).
$$
The paired mass in cohort $i$ is
$$
z_i=
\min\left(
M_i,\,
\max\left(K-\sum_{j<i}M_j,0\right)
\right).
$$
Proof. Each paired recipient consumes equal mass from the two capacities. After paired mass $Y$ has been allocated, their minimum residual capacity is $K-Y$.
Theorem 5 therefore gives the recurrence
$$
z_i=\min\left(M_i,K-\sum_{j<i}z_j\right).
$$
Induction yields
$$
\sum_{j\leq i}z_j=\min\left(K,\sum_{j\leq i}M_j\right),
$$
which gives the stated formula. $\square$
All cohort totals are consequently computable with polynomially many rational operations.
Under the hypotheses of Theorem 5, suppose each cohort contains exactly one supported type. Then the complete mass-allocation function is polynomial-time computable.
For the type $t$ in cohort $i$, its only possible bundles are empty and the pair, and
$$
x_{t,\{a,b\}}=z_i,\qquad
x_{t,\varnothing}=\mu_t-z_i.
$$
Zero entries are omitted.
This permits arbitrary positive rational type masses, arbitrary priority order, and either wishlist order in each cohort.
For example, with one type of mass $1$ and capacities
$$
\kappa_a=2^{1-k},\qquad \kappa_b=2^{-k},
$$
the output follows immediately:
$$
x_{t,\{a,b\}}=2^{-k},\qquad
x_{t,\varnothing}=1-2^{-k}.
$$
The computation uses the final-mass formula without enumerating the rollback trajectory.
The static-impossibility theorem relies on the reduced process having no if-and-only-if caveats. Its proof does not establish that removing impossible components preserves the output when other, feasible linked components remain.
The bottleneck theorem determines cohort totals, but those totals alone do not determine the separate masses of several types within the same cohort.
Thus a general polynomial-time algorithm, or an $\mathrm{NP}$-hardness reduction concerning the exact final bundle masses, is still missing.
⟨structured verdict parsed — rendered above⟩
The output establishes genuine special-case results, but does not resolve the general complexity question in USER_TASK. The two tractable regimes are supported by the arguments given. The termination, arithmetic, and output-size arguments also stand.
I found no false central step or substantive gap in the special-case proofs. The blocking issue is the expressly acknowledged absence of a general polynomial-time algorithm or an $\mathrm{NP}$-hardness reduction.
Lemma 1: verified.
The denominator
$$
D=2\prod_{i=1}^{s}b_i
$$
has binary length $O(L)$. Expressing any input mass with denominator $D$ gives an even integer numerator, so taking cohort midpoints remains within the grid of spacing $1/D$.
The initial partition includes the discontinuity of the shifted order. Within each resulting half-cohort, each round order is monotone. Consequently, the two stated split coordinates,
$$
a+\rho
\qquad\text{and}\qquad
b-\rho,
$$
cover the possible processing directions. Both remain grid-aligned. Restoring earlier capacity values and retaining boundaries preserves the invariant.
The bound of at most $D$ positive-mass cells follows from their minimum possible length $1/D$.
Lemma 2: verified.
The bookkeeping records are monotone because permanent deletions survive rollback and are inherited by subsequent subdivisions.
An already failed pair cannot fail again on the same atom: its offerings remain deleted, and its earlier selections were undone. In particular, neither a before-turn failure nor a fourth-turn failure can occur without an unsatisfied pair containing exactly one held offering. Thus each backtrack creates at least one new atom-caveat record.
The bound $Dq$ is valid, although coarse: $q$ bounds the number of relevant caveats for each atom. Between backtracks, the bounded number of retained cells and the finite round schedule ensure finite forward processing.
Exact implementation and arithmetic: verified at the stated level of detail.
Refining live selections at retained boundaries gives at most $4D$ live selection records. Together with the retained partition and turn state, this supports the stated implementation using time polynomial in $D,m,\tau,q,L$.
The common-denominator arithmetic has polynomial bit length. Capacities may exceed total society mass, so their numerators need not be bounded by $D$, but their bit lengths are still $O(L)$, as claimed.
Since $D=2^{O(L)}$ and the explicitly listed input parameters are bounded by the input length, the resulting upper bound
$$
2^{O(L)}
$$
is justified. It does not imply polynomial-time computability or hardness.
Output-size bound: verified.
Every final bundle has at most four offerings. Therefore
$$
\tau\sum_{j=0}^{\min(4,m)}\binom{m}{j}
=
O(\tau m^4)
$$
bounds the number of possible output entries.
Every output mass is a sum of grid-aligned cell masses and lies in $[0,1]$. Its representation as $a/D$, with $0\leq a\leq D$, therefore has $O(L)$ bits.
Lemma 3: verified in both directions.
Each listed obstruction prevents every superset of $K$ from being feasible. This uses the downward-closed nature of the block, underlying-course, and at-most restrictions.
Conversely, if none of the obstructions occurs, $K$ itself satisfies every condition in the supplied definition of feasibility. Distinct blocks also imply $|K|\leq4$.
The characterization and its polynomial-time recognition are valid.
Theorem 4, Step 1: verified.
Termination leaves every if-and-only-if caveat satisfied. Satisfaction propagates along paths in a connected component: a final bundle containing one vertex must contain the entire component.
Static impossibility therefore excludes every offering in $R_t$ from the final bundle of type $t$.
Theorem 4, Step 2: verified.
The chronological-suffix rollback rule is essential here, and the argument uses it correctly. When a temporary selection is undone, later selections and skips affected by its assignment or capacity consumption are also undone.
Under this theorem’s hypothesis, all permanent pair deletions and pair-generated exclusions concern offerings in the recipient type’s removed set $R_t$. They cannot directly exclude an offering retained in that type’s reduced wishlist.
In the final surviving trace, preceding assignments contain no selections forbidden for their recipients. Consequently, eligibility and capacities for reduced choices agree with those determined by the preceding retained choices. A surviving choice is therefore the highest eligible reduced choice; a surviving empty turn has no eligible reduced choice.
This establishes the required correspondence without assuming that temporary forbidden selections had no effects during execution.
Theorem 4, Step 3: verified.
The refinement argument applies because each cell lies within a monotone piece of every round order. Subdividing a cell preserves the sequence of wishlist choices and the mass coordinate at which a capacity is exhausted.
The argument concerns subdivision without reordering members or crossing type boundaries, which is precisely the retained refinement used here.
Theorem 4, Step 4: verified.
There are initially at most $\tau+g\leq2\tau$ cells. Without backtracking, each proper capacity split exhausts an offering permanently. Thus there are at most $m$ additional splits and at most $2\tau+m$ cells.
Four rounds over these cells, explicit eligibility checks, and rational aggregation give a polynomial-time algorithm for this restricted regime.
The example requiring a pair while imposing an at-most-one restriction on that pair satisfies the theorem’s hypothesis.
The hypotheses ensure that both offerings are individually legal and that the pair is legal apart from capacity constraints. Because the additional at-most caveats hold for the pair, they also hold for each subset.
Theorem 5, Step 1: verified.
An undeleted member who obtains no offering in round one encounters an unavailable pair member. Within forward processing, that unavailability persists because capacities only decrease.
Chronological rollback does not preserve a later turn whose outcome depended on an undone earlier selection. Thus replay does not invalidate the reasoning about the retained round-one history.
A cell holding its first offering has an eligible partner whenever the partner has positive residual capacity. Accordingly, a failure occurs with an exhausted partner. The proof also handles a remainder created by partial partner allocation without requiring an immediate failure check during that same turn.
Theorem 5, Step 2: verified.
At a failure with exhausted partner $d$, the cohort has consumed exactly its entry residual capacity $K_d$ of that offering. Previously completed cohorts remain fixed.
All current holders of $d$ belong to $U$: permanent deletion would already have removed their pair selections. Those holders are disjoint from the failing cell $F$, which lacks $d$. Hence
$$
s\geq K_d+f
$$
and, after deletion,
$$
s-f\geq K_d\geq z_*.
$$
This correctly establishes the invariant $s\geq z_*$.
Theorem 5, Step 3: verified.
The upper bound $z\leq z_*$ follows from mass and capacity constraints.
If $z<z_*$, both final residual capacities are positive. In the surviving chronological trace, capacities decrease from the cohort’s entry capacities to those final values. Thus neither offering was exhausted at any retained turn.
Every undeleted member consequently receives an offering at its first turn. Since every final bundle satisfies the pair requirement, each such member must finally hold the pair. This gives $z=s\geq z_*$, contradicting the assumed strict inequality.
The edge case $z_*=0$ is already covered by $0\leq z\leq z_*$.
Corollary 6: verified.
Later-cohort rollbacks begin within the later cohort, so previously completed cohorts are unaffected. Each completed paired allocation consumes equal mass from the two capacities.
The recurrence and its stated solution,
$$
z_i=
\min\left(
M_i,\,
\max\left(K-\sum_{j<i}M_j,0\right)
\right),
$$
are consistent, including exhaustion before a cohort and capacities exceeding total society mass.
Corollary 7: verified.
When a cohort contains one supported type, its cohort total determines that type’s paired mass. Its remaining mass receives the empty bundle. The formulas therefore compute the complete requested output in this restricted regime.
The final numerical example has the stated bottleneck and is correct for nonnegative capacities of the displayed form.
The output correctly identifies its own limitations:
USER_TASK.This is a major scope issue, rather than an error in the special-case arguments. A further round must supply a result covering the unrestricted task. Termination, an exponential simulation bound, polynomial output length, and tractable subclasses do not settle that classification.
The minimum necessary addition is either a general algorithm with a polynomial running-time proof under the exact retained-boundary rollback convention, or a hardness reduction concerning the requested final masses.
⟨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.