Answer: The threshold problem is in \(\mathrm P\). Feasibility, the exact supremum, attainment, and an optimal rational allocation with a compact finite schedule are computable in \(\operatorname{poly}(m,\tau,B,n,L)\) time. Explicitly listing an attaining schedule can require \(2^{\Omega(L)}\) steps; construction takes polynomial time in the input plus expanded output length.
Theorems 3.1 and 3.2 — class: other
Given a finite goods set \(G\), rational per-capita inventories \(u^{in},u^{out}\), and supplier types \(r\) with rational masses \(\mu_r\) and complete XOR bid menus, maximize \(\sum_{r,b} p_{rb}x_{rb}\) over accepted bid masses \(x_{rb}\ge 0\), subject to \(\sum_b x_{rb}\le\mu_r\). Each bid’s transformations have integral input and output bundles and multiplicities \(a_{rbj}\). Require that their total execution masses \(a_{rbj}x_{rb}\) admit some finite schedule of nonnegative execution masses, with inventory sufficient before every stage and final inventory at least \(u^{out}\). Determine the optimum and a schedule attaining it.
Let \(G\) be a finite goods set, with \(m=|G|\). A society is given by its support: an explicit list of \(\tau\) supplier types with positive binary-rational masses \(\mu_r\), normalized by \(\sum_r\mu_r=1\); \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly listed complete menu \(B_r\) of permitted XOR bids. Bid \(b\) has a signed rational price \(p_{rb}\) and a finite multiset of transformations, represented by pairs \((I_{rbj},O_{rbj})\in\mathbb Z_{\ge0}^{G}\times\mathbb Z_{\ge0}^{G}\) with positive integer multiplicities \(a_{rbj}\). Positive prices are payments to the auctioneer; negative prices are payments to suppliers. Empty input or output bundles are allowed.
Initial and required final per-capita inventories are \(u^{in},u^{out}\in\mathbb Q_{\ge0}^{G}\). Accepted masses satisfy \(x_{rb}\in\mathbb R_{\ge0}\) and \(\sum_{b\in B_r}x_{rb}\le\mu_r\); different fractions of a type may accept different bids, and unallocated mass is allowed.
A schedule is a finite, possibly empty sequence of steps, each executing one transformation \((r,b,j)\) by a real mass \(d\ge0\). From inventory \(v\), the step requires \(v\ge dI_{rbj}\) and updates it to \(v+d(O_{rbj}-I_{rbj})\), componentwise. Transformations may be split across steps and interleaved across bids.
Starting at \(u^{in}\), the total scheduled mass of every \((r,b,j)\) must equal \(a_{rbj}x_{rb}\), and final inventory must be at least \(u^{out}\). Surplus goods are allowed; infinite schedules and their limits are excluded. Revenue is \(\sum_{r,b}p_{rb}x_{rb}\).
Let \(B\) be the total number of bids, \(n\) the number of listed transformation entries, and \(L\) the total binary input length, including multiplicities. State running times in \(m,\tau,B,n,L\).
Is deciding whether a feasible finite schedule achieves revenue at least a given binary-rational threshold \(q\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
What is the complexity of determining the exact optimum and constructing a finite attaining schedule, including deciding feasibility and whether a maximum is attained?
The discrete SCC-based integer formulation preserves the feasible allocations and optimal revenue of the direct sequence formulation ([Giovannucci et al., 2008](https://aamas.csc.liv.ac.uk/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0032.pdf)); discrete winner determination is \(\mathrm{NP}\)-hard ([Cerquides et al., 2007](https://www.ijcai.org/Proceedings/07/Papers/197.pdf)).
Continuous Petri-net reachability and coverability are polynomial-time decidable ([Fraca and Haddad, 2015](https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/FH-fundi15.pdf)); single-place yield thresholds also have a polynomial-time algorithm ([Jordon et al., 2025](https://arxiv.org/html/2509.02371v1)). These results do not study the XOR bid-menu optimization defined above.
The threshold problem is in \(\mathrm P\).
Feasibility, the exact revenue supremum, and whether that supremum is attained are also computable in time polynomial in \(m,\tau,B,n,L\). When a maximum exists, an optimal rational allocation and a compact description of a finite attaining schedule can be constructed in polynomial time.
There is an output-size qualification: explicitly listing every step of an attaining schedule can require exponentially many steps, even when \(m=\tau=B=n=1\). I give both a construction and a matching exponential output-size example below.
Throughout, when a threshold is supplied, its encoding length is included in \(L\); otherwise replace \(L\) by \(L+\operatorname{bits}(q)\).
Index bids by \(\beta=(r,b)\), and transformation entries by \(t=(r,b,j)\). Write \(\beta(t)\) for the bid containing entry \(t\), and write its multiplicity as \(a_t\).
Let \(C\) be the goods-by-entry matrix whose column \(t\) is \(O_t-I_t\). Define the goods-by-bid matrix \(D\) by
\[ D_{g,\beta}=\sum_{t:\,\beta(t)=\beta}a_t C_{g,t}. \]
For an allocation \(x\), the required firing-count vector and final inventory are therefore
\[ y_t=a_t x_{\beta(t)},\qquad z=u^{in}+Cy=u^{in}+Dx. \]
In particular, the final inventory is determined by the allocation, independently of the execution order.
The elementary allocation constraints are
\[ x\ge 0,\qquad \sum_{b\in B_r}x_{rb}\le\mu_r,\qquad z=u^{in}+Dx,\qquad z\ge u^{out}. \]
These constraints alone do not characterize finite schedulability. We need two additional support conditions.
For a nonnegative vector \(v\), define \(\operatorname{supp}(v)=\{g:v_g>0\}\).
Given a set \(S\) of transformation entries and an initial inventory \(v\), compute a set \(F(S,v)\) as follows:
For the reverse system, interchange \(I_t\) and \(O_t\), and denote the corresponding set by \(F^{rev}(S,v)\).
These procedures depend only on the support of \(v\). They are monotone in both the permitted entry set and the initial inventory support.
Lemma. Let \(y\ge0\), let \(S=\{t:y_t>0\}\), and suppose \(z=u^{in}+Cy\ge0\). There is a finite schedule with exactly firing counts \(y\) if and only if
\[ F(S,u^{in})=S \quad\text{and}\quad F^{rev}(S,z)=S. \]
This is the prescribed-count form of the finite-reachability characterization in [Fraca and Haddad, Theorem 20 and its sufficiency proof](https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/FH-fundi15.pdf). Here the net has nonnegative integer input and output matrices, and firing amounts are nonnegative reals, exactly as required. The following constructive proof makes the prescribed counts and schedule representation explicit.
Necessity. Consider any positive-mass step of a finite schedule. Every input good is positive immediately before that step. A good that was initially zero can become positive only through an earlier transformation producing it. Induction over the schedule therefore puts every executed entry in \(F(S,u^{in})\).
A forward step from \(v\) to \(v'=v+d(O_t-I_t)\) satisfies
\[ v'\ge dO_t, \]
because \(v-dI_t\ge0\). Thus the schedule can be reversed in the reverse system, with the same amounts. The preceding argument applied to that reversed schedule gives \(F^{rev}(S,z)=S\).
Sufficiency and construction. If \(S=\varnothing\), the empty schedule suffices. Otherwise, use an order in which the forward closure adds the entries. Fire each entry \(t\) once, choosing
\[ d_t=\min\left\{\frac{y_t}{4}, \ \min_{g:I_{g,t}>0}\frac{v_g}{2I_{g,t}}\right\}, \]
where the inner minimum is interpreted as infinity when there are no inputs.
Every chosen amount is positive. Each step preserves positivity of every currently positive good, and makes every output good positive. Consequently, after these at most \(|S|\) steps, the inventory \(w\) is positive on every good incident to an entry of \(S\). Let their firing-count vector be \(f\). We have \(0<f_t\le y_t/4\) on \(S\).
Apply the same construction in reverse, starting at \(z\). It produces a reverse firing-count vector \(h\), with \(0<h_t\le y_t/4\), and an inventory \(w'\) positive on every incident good. Then
\[ w=u^{in}+Cf,\qquad w'=z-Ch,\qquad \rho=y-f-h,\qquad w'=w+C\rho. \]
In particular, \(\rho_t\ge y_t/2>0\) on \(S\).
Let \(J\) be the set of incident goods. For \(g\in J\), define
\[ \eta_g=\min\{w_g,w'_g\}>0, \qquad R_g=\sum_{t\in S}\rho_t I_{g,t}. \]
Choose a positive integer \(K\) such that \(K\eta_g\ge R_g\) for every \(g\in J\). If \(J\) is empty, take \(K=1\).
Fix any order of \(S\). Repeat \(K\) times the block that fires each \(t\in S\) by amount \(\rho_t/K\).
To verify this block execution, at the beginning of round \(k\), where \(0\le k<K\), the inventory is
\[ w+\frac{k}{K}C\rho = \left(1-\frac{k}{K}\right)w+\frac{k}{K}w', \]
so its coordinate \(g\in J\) is at least \(\eta_g\). Before firing entry \(t\), preceding entries in the round have consumed at most their corresponding shares of \(R_g/K\). Ignoring their outputs gives the lower bound
\[ v_g\ge \eta_g-\frac{1}{K}\sum_{s\text{ preceding }t}\rho_s I_{g,s} \ge \frac{\rho_t I_{g,t}}{K}. \]
Hence the step is enabled. After all \(K\) rounds the inventory is \(w'\), with firing counts \(\rho\). Finally, reverse the reverse prefix to move from \(w'\) to \(z\), with counts \(h\).
The resulting finite schedule has exactly counts \(f+\rho+h=y\). This proves the lemma.
The following algorithm permits an additional rational linear constraint \(\mathcal E\) on the allocation. We will use either no additional constraint, the threshold constraint \(p\cdot x\ge q\), or an optimal-face constraint.
Maintain a permitted bid set \(H\), initially containing all bids. Define the rational polytope
\[ P_H(\mathcal E)= \left\{(x,z): \begin{array}{l} x\ge0,\quad z\ge0,\quad z=u^{in}+Dx,\quad z\ge u^{out},\\ \sum_{b\in B_r}x_{rb}\le\mu_r\ \text{for every }r,\\ x_\beta=0\ \text{for }\beta\notin H,\quad \mathcal E \end{array} \right\}. \]
This polytope is bounded: every \(x_\beta\le\mu_{r(\beta)}\le1\), and \(z\) is an affine function of \(x\).
Each iteration proceeds as follows.
\[
\operatorname{supp}(x)\subseteq\operatorname{supp}(x^*),
\qquad
\operatorname{supp}(z)\subseteq\operatorname{supp}(z^*)
\]
for every \((x,z)\in P_H(\mathcal E)\).
\[
T=\{t:\beta(t)\in A\}.
\]
Compute \(F=F(T,u^{in})\) and \(R=F^{rev}(T,z^*)\).
A bid with no transformation entries passes the entry test vacuously. Thus empty bids, empty bundles, and the empty schedule are all handled.
Deleting bids never removes a feasible allocation. Maintain the invariant that every allocation satisfying \(\mathcal E\) and admitting a finite schedule is still represented in \(P_H(\mathcal E)\).
Suppose such an allocation is \(x\), with final inventory \(z\). By maximality of the support point,
\[ \operatorname{supp}(x)\subseteq A, \qquad \operatorname{supp}(z)\subseteq\operatorname{supp}(z^*). \]
Because all multiplicities are positive, its positive firing-count entries are precisely all entries belonging to its positive bids. Denote this entry set by \(S\); then \(S\subseteq T\).
The scheduling lemma gives forward fireability of \(S\) from \(u^{in}\) and reverse fireability from \(z\). Monotonicity of the closure procedures consequently gives
\[ S\subseteq F(T,u^{in}), \qquad S\subseteq F^{rev}(T,z^*). \]
Therefore no positive bid of this feasible allocation is deleted. This establishes the invariant.
A successful termination supplies a finite schedule. At termination, every bid in \(H\) is positive in \(x^*\), and every entry of these bids lies in both closure sets. Thus the prescribed counts \(y_t=a_t x^*_{\beta(t)}\), together with final inventory \(z^*\), satisfy the scheduling lemma. Its construction supplies a finite schedule.
The algorithm therefore decides feasibility correctly. With \(\mathcal E\) equal to \(p\cdot x\ge q\), it decides the requested threshold problem.
Every unsuccessful iteration deletes a bid, so there are at most \(B+1\) iterations. Each iteration uses at most \(B+m+1\) LP calls.
For an explicit bound, set \(s=m+\tau+B+n+1\). The LPs have \(B+m\) variables, \(O(B+m+\tau)\) constraints, and encoding length \(\ell'=O(s^2(L+1))\). The aggregated coefficients of \(D\) have polynomial encoding length even with binary multiplicities.
Let \(\operatorname{LP}(d,c,\ell)\) denote a polynomial bit-time bound for exact rational linear programming. The running time is bounded by
\[ \operatorname{poly}(s,L)+ O\!\left( (B+1)\left[ (B+m+1)\operatorname{LP}\bigl(B+m,O(B+m+\tau),\ell'\bigr) +(m+1)n(n+1) \right]\right). \]
The closure bound comes from at most \(n\) scans of at most \(n\) entries, checking at most \(m\) input coordinates per entry.
In particular, the threshold problem is in \(\mathrm P\); it could be \(\mathrm{NP}\)-hard only if \(\mathrm P=\mathrm{NP}\).
Run the algorithm without a revenue constraint. If it returns infeasible, there is no feasible schedule.
Otherwise, let \(H_*\) be its terminal bid set, let \(P_*=P_{H_*}\), and let \((x^*,z^*)\) be the terminal support point. Let \(\mathcal F\) denote the feasible allocations under finite-schedule semantics, and let \(Q_*\) be the allocation projection of \(P_*\).
Proposition. The closure of \(\mathcal F\) is exactly \(Q_*\).
Proof. The deletion invariant gives \(\mathcal F\subseteq Q_*\). Since \(Q_*\) is a closed polytope, \(\overline{\mathcal F}\subseteq Q_*\).
Conversely, take any \((x,z)\in P_*\). For \(0<\varepsilon<1\), define
\[ (x^\varepsilon,z^\varepsilon) =(1-\varepsilon)(x,z)+\varepsilon(x^*,z^*). \]
This point remains in \(P_*\). Maximal support of \((x^*,z^*)\) gives
\[ \operatorname{supp}(x^\varepsilon)=\operatorname{supp}(x^*), \qquad \operatorname{supp}(z^\varepsilon)=\operatorname{supp}(z^*). \]
Consequently, the forward and reverse closure tests for this mixture are exactly the successful terminal tests. The scheduling lemma proves that \(x^\varepsilon\in\mathcal F\).
As \(\varepsilon\) tends to zero, \(x^\varepsilon\) tends to \(x\), proving \(Q_*\subseteq\overline{\mathcal F}\). ∎
Because revenue is continuous and \(Q_*\) is compact, its exact supremum is therefore
\[ V=\sup_{x\in\mathcal F}p\cdot x =\max_{(x,z)\in P_*}p\cdot x. \]
One exact rational LP computes \(V\). The value has polynomial binary encoding length: after clearing denominators, vertex coordinates are ratios of determinants of polynomial-size integer matrices, so their bit lengths are polynomially bounded. Signed prices cause no difficulty.
To decide attainment, run the feasibility algorithm again with the additional constraint
\[ p\cdot x=V. \]
A successful result supplies an optimal rational allocation and a finite attaining schedule. An unsuccessful result proves that no maximum exists.
Thus the following tasks all take polynomial time in \(m,\tau,B,n,L\):
The construction in Section 2 consists of a forward prefix, a repeated block, and a suffix. Each prefix and suffix has at most \(n\) steps; the block has at most \(n\) steps.
For the rational allocation returned by the LP algorithm, all parameters of this representation have polynomial bit length. To verify this assertion, begin with a common denominator for the rational inventories and prescribed counts. At each prefix step, the chosen amount is either \(y_t/4\) or \(v_g/(2I_{g,t})\). The common denominator therefore needs multiplication by only \(4\) or \(2I_{g,t}\). Over at most \(n\) steps, its bit length increases polynomially. The reverse prefix has the same property.
Hence \(w,w',\rho,\eta_g,R_g\) all have polynomial bit length. We can take
\[ K=\max\left\{1,\ \max_{g\in J}\left\lceil\frac{R_g}{\eta_g}\right\rceil\right\}, \]
which also has polynomial bit length. The block amounts \(\rho_t/K\) consequently have polynomial bit length.
Thus a polynomial-time construction outputs:
This describes an actual finite schedule. Expanding it produces at most \(nK+2n\) steps, in time polynomial in the input length plus the expanded output length. Since \(K\) has polynomial bit length, the general explicit-output upper bound is \(2^{\operatorname{poly}(m,\tau,B,n,L)}\).
Take one good \(g\), one type of mass \(1\), and one bid of price \(1\). Its sole entry, with multiplicity \(1\), is
\[ Mg\longrightarrow Mg, \]
where \(M\) is a positive binary-encoded integer. Set \(u^{in}_g=u^{out}_g=1\).
Inventory remains \(1\) throughout. Every step must satisfy \(dM\le1\), so \(d\le1/M\). The optimal allocation is \(x=1\), requiring total executed mass \(1\). Any attaining schedule therefore has at least \(M\) positive-mass steps.
Exactly \(M\) steps of mass \(1/M\) attain the maximum. For \(M=2^k\), the input length is \(\Theta(k)\), while every explicit attaining schedule has at least \(2^k\) steps. This holds with \(m=\tau=B=n=1\).
Take one good \(g\), one type of mass \(1\), and one bid of price \(1\), with the single multiplicity-\(1\) entry
\[ 2g\longrightarrow g. \]
Set \(u^{in}_g=1\) and \(u^{out}_g=0\).
From positive inventory \(v\), an enabled step has \(d\le v/2\), so the resulting inventory satisfies \(v-d\ge v/2>0\). Every finite schedule therefore ends with positive inventory.
Since the total firing mass equals \(x\), final inventory is \(1-x\). Thus finite schedulability requires \(x<1\).
Conversely, every \(0<x<1\) is finitely schedulable. Choose a positive integer \(K\) with \(x/K\le1-x\), and execute \(K\) steps of mass \(d=x/K\). Before every step,
\[ v\ge1-x+d\ge2d, \]
so each step is enabled. The allocation \(x=0\) uses the empty schedule.
The feasible revenue set is therefore \([0,1)\): its exact supremum is \(1\), and no maximum exists. In particular, threshold \(q=1\) is infeasible despite being equal to the supremum.
This distinction is why exact optimization needs both the closure LP and the separate finite-schedule feasibility test on its optimal face.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the threshold, feasibility, supremum, attainment, and schedule-construction questions. I found no major or minor mathematical issues. The distinction between polynomial-time construction of a compact schedule and potentially exponential explicit schedule output is justified.
The equations \(y_t=a_t x_{\beta(t)}\) and \(z=u^{in}+Cy=u^{in}+Dx\) correctly express the required execution totals and final inventory. They account for binary-encoded multiplicities without introducing additional allocation choices.
The type constraints correctly allow different fractions to accept different bids and permit unallocated mass. Signed prices affect only the linear objective. The final inequality \(z\ge u^{out}\) correctly permits surplus goods.
The output does not confuse satisfaction of the inventory balance equations with finite schedulability.
The cited finite-reachability characterization requires the state equation and forward and reverse firing-support conditions. The attribution to [Fraca and Haddad, Theorem 20 and its sufficiency proof](https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/FH-fundi15.pdf) is accurate. Although its theorem statement is existential in the firing vector, the sufficiency proof preserves the chosen vector, supporting the prescribed-count interpretation.
The hypotheses match the task: finite sets of places and transitions, nonnegative integer input and output matrices, nonnegative real inventories, and real firing amounts under the stated enabling rule. More importantly, the output supplies its own complete construction, so the scheduling lemma does not rest on an unexplained theorem application.
The forward argument is valid. Every input coordinate of a positive-mass step must already be positive. If it was initially zero, some earlier positive-mass step must have produced it. Induction over the finite sequence therefore places every positively executed entry in the forward closure.
The reverse argument correctly checks enabling, rather than merely reversing the inventory equation. From \(v\ge dI_t\), the resulting inventory satisfies \(v'=v-dI_t+dO_t\ge dO_t\). Thus the reverse step is enabled and restores \(v\). Reversing the whole sequence establishes the reverse support condition.
Zero-mass steps can be disregarded without changing any execution total.
Each prefix amount is positive because the closure order guarantees positivity of every required input coordinate and \(y_t>0\) on \(S\). The bound \(d_t\le v_g/(2I_{g,t})\) preserves positivity of currently positive coordinates. Positive firing also makes every output coordinate positive. Hence both prefixes produce inventories positive on all incident goods.
The identities relating \(w,w',f,h,\rho\) are correct. Since \(f_t,h_t\le y_t/4\), the residual satisfies \(\rho_t\ge y_t/2>0\).
The repeated-block enabling calculation is valid. At each round boundary, inventory is the stated convex combination of \(w\) and \(w'\), giving the lower bound \(\eta_g\). Within a round, ignoring preceding outputs gives a valid lower bound. The condition \(K\eta_g\ge R_g\) reserves enough inventory for the current entry after accounting for preceding consumption.
The block executes exactly \(\rho\) and reaches \(w'\). Reversing the reverse prefix is enabled and executes exactly \(h\). The complete schedule therefore executes exactly \(y\) and ends at \(z\).
The cases \(S=\varnothing\), empty input bundles, empty output bundles, and entries with no incident goods are covered.
The polytope is bounded: each allocation coordinate is at most its type mass, and inventory is an affine function of the allocation.
Coordinate maximization and averaging correctly construct a point whose allocation and inventory supports contain those of every feasible LP point. Nonnegativity is essential here and is explicitly imposed. Averaging preserves all linear constraints, including the revenue threshold or optimal-face equality.
Exact rational LP feasibility and optimization apply to these rational, bounded polytopes. Coordinate positivity can therefore be tested exactly; no numerical tolerance assumption is being used.
The deletion invariant is correct. Any finitely schedulable allocation satisfying the additional constraint has allocation and final-inventory supports contained in those of the maximal-support point.
Positive multiplicities ensure that accepting a bid with positive mass requires positive execution of every listed entry of that bid. Consequently, if one of its entries fails either closure test, that bid cannot be positive in any feasible allocation retained by the invariant.
Monotonicity is applied in the correct direction: enlarging the permitted transition set or initial inventory support can only enlarge the closure. This establishes that deletion never removes a positive bid from a feasible allocation.
When no deletion occurs, all remaining bids have positive allocation and all their entries pass both closure tests. The scheduling lemma therefore supplies a finite schedule. Every unsuccessful iteration deletes at least one bid, so the iteration bound is valid.
Bids with no entries pass vacuously and correctly require no execution.
The bound of at most \(B+1\) iterations and at most \(B+m+1\) LP calls per iteration is correct. The closure scan bound is a valid polynomial upper bound.
Aggregating \(D\) requires integer products and sums whose binary lengths remain polynomial in the supplied parameters and input length. Binary multiplicities do not require expansion into separate transformation copies.
Exact LP solutions and their averages have polynomial encoding length. The additional threshold constraint has polynomial size under the stated convention for the encoding length of \(q\).
Thus the threshold decision algorithm is polynomial in \(m,\tau,B,n,L\).
The closure proposition is correctly proved in both directions. The deletion invariant puts every feasible allocation in the terminal polytope projection. That projection is closed because it is a compact polytope.
Conversely, mixing any terminal LP point with the terminal maximal-support point preserves the constraints and gives exactly the terminal allocation and inventory supports for every \(0<\varepsilon<1\). The successful closure tests therefore apply to each mixture, making it finitely schedulable. Convergence of these allocations proves the claimed closure equality.
Maximizing the continuous revenue functional over this compact closure correctly computes the supremum, without assuming that a feasible allocation attains it. The rational optimum has polynomial encoding length by the stated determinant bound.
Applying the feasibility algorithm to \(p\cdot x=V\) correctly decides attainment and constructs an optimal rational allocation when one exists. Initial feasibility is tested separately, so optimization over an empty feasible set is avoided.
The denominator-growth argument is valid: each prefix step introduces only a factor associated with \(4\) or \(2I_{g,t}\), over at most \(n\) steps. The reverse prefix has the same bound. The remaining arithmetic, including the ceiling defining \(K\), preserves polynomial binary length.
The prefix, repeated block, binary repetition count, and suffix consequently form a polynomial-size description of an actual finite schedule. The construction never substitutes an infinite sequence or limit for a schedule.
The explicit-output lower bound is correct. In the example \(Mg\longrightarrow Mg\), inventory stays at \(1\), so every step has mass at most \(1/M\). Total execution mass \(1\) requires at least \(M\) positive-mass steps. Taking \(M=2^k\) gives exponential output size with all four structural parameters equal to \(1\).
The claimed polynomial time in input length plus expanded output length is consistent with the construction.
For \(2g\longrightarrow g\), every enabled step from positive inventory leaves positive inventory. A finite sequence therefore cannot achieve allocation \(x=1\), whose final inventory would be zero.
The proposed construction for every \(0<x<1\) is also correct: with \(d=x/K\le1-x\), inventory before each step is at least \(1-x+d\ge2d\). The empty schedule handles \(x=0\).
Thus the feasible revenue set is exactly \([0,1)\), confirming both nonattainment and the need for the separate optimal-face feasibility test.
Repair feedback: None required. The argument establishes polynomial-time decision and exact supremum/attainment computation, with the stated and justified qualification for explicit schedule output.
⟨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.