Answer: Polynomial-time solvable in \(m,\tau,L\) by rational linear-programming feasibility.
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateChecking whether SB∗(N, J) ≤Z for some input N, J, Z is NP-hard, even when J includes only fixed contracts.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\) with rational masses \(\mu_t\) summing to one, a finite menu \(J\) of fixed contracts with per-consumer reductions \(\ell_j\), rational costs \(b_{tj}\), a required per-consumer reduction \(\rho\), and a per-consumer cost bound \(z\), decide whether there are rational allocations \(x_{tj}\ge 0\) satisfying \(\sum_j x_{tj}\le\mu_t\) for every \(t\), \(\sum_{t,j}\ell_jx_{tj}\ge\rho\), and \(\sum_{t,j}b_{tj}x_{tj}\le z\).
A society is given by its support: a list of \(\tau\) types \(T\) with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a nonempty finite menu \(J\) of \(m=|J|\) offered contracts, nonnegative binary-rational declared reductions \(\ell_j\), nonnegative binary-rational per-consumer bids \(b_{tj}\), and nonnegative binary-rational thresholds \(\rho,z\). Bids are supplied directly; the cost bound concerns their sum.
An allocation \(x_{tj}\in\mathbb{Q}_{\ge0}\) assigns that mass of type \(t\) to contract \(j\). A type's mass may be divided among contracts, with unused mass taking no contract. Feasibility means \(\sum_{j\in J}x_{tj}\le\mu_t\) for every \(t\), \(\sum_{t\in T,j\in J}\ell_jx_{tj}\ge\rho\), and \(\sum_{t\in T,j\in J}b_{tj}x_{tj}\le z\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether a feasible rational allocation exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite consumers, assigning at most one contract per consumer to meet a declared reduction target within a total-bid bound is NP-hard, even for fixed-penalty contracts; with integer reductions, optimization admits a running time polynomial in the consumer count, menu size, and numerical reduction target. [Source](https://arxiv.org/pdf/1705.07300)
No result for exactly this distribution-over-types feasibility problem was identified in the literature search.
The decision problem is polynomial-time solvable in \(m,\tau,L\). Allowing each type’s mass to be divided among contracts makes the stated problem an exact rational linear-programming feasibility problem.
Set \(N=\tau m\), and introduce one real variable \(x_{tj}\) for each explicitly listed pair \((t,j)\in T\times J\). Define the polyhedron \(P\subseteq\mathbb{R}^{N}\) by the following inequalities:
There are exactly \(R=N+\tau+2\) inequalities. Every coefficient and right-hand side is rational and is either an input number, its negative, or one of the constants \(0,1,-1\).
By construction, a rational allocation is feasible in the stated problem if and only if it belongs to \(P\cap\mathbb{Q}^{N}\). In particular, the cost constraint uses the supplied bids directly; no additional cost computation is necessary.
We verify that deciding whether \(P\) is nonempty suffices, despite the requirement that allocations be rational.
For every \(x\in P\), nonnegativity and the type-capacity inequalities imply
\(0\le x_{tj}\le\mu_t\le1\).
Consequently, \(P\) is bounded. It is also closed, since it is defined by finitely many non-strict linear inequalities. Thus, if nonempty, it is compact.
A nonempty compact polyhedron has an extreme point. Here this can be seen directly: successively minimize each of the \(N\) coordinates, restricting at each step to the preceding minimizers. Compactness ensures that each minimum is attained. The final point \(v\) is extreme: if \(v\) were the midpoint of two feasible points, coordinate-by-coordinate minimality would force both points to agree with \(v\) in every coordinate.
Write the defining system as \(Ax\le d\). At an extreme point \(v\), the rows of \(A\) corresponding to tight inequalities span \(\mathbb{R}^{N}\). Indeed, otherwise there would be a nonzero vector \(h\) orthogonal to every tight row. For sufficiently small \(\varepsilon>0\), both \(v+\varepsilon h\) and \(v-\varepsilon h\) would satisfy all inequalities: tight inequalities remain equalities, and every other inequality has positive slack. This contradicts extremality.
Therefore, we can select \(N\) linearly independent tight rows, obtaining a nonsingular rational matrix \(B\) and a rational vector \(d'\) such that \(Bv=d'\). Cramer’s rule gives \(v\in\mathbb{Q}^{N}\). Hence
\(P\ne\varnothing\) if and only if \(P\cap\mathbb{Q}^{N}\ne\varnothing\).
Let \(H\) denote the binary encoding length of the constructed linear system. A dense representation contains \(R(N+1)\) matrix and right-hand-side entries. Each entry has encoding length \(O(L+1)\), so the conservative bound
\(H=O\bigl((\tau m+\tau+2)(\tau m+1)(L+1)\bigr)\)
holds. Constructing this representation takes polynomial time in \(m,\tau,L\).
The rational linear-programming theorem states that feasibility of an explicitly represented system of rational linear inequalities is decidable in deterministic time polynomial in its dimensions and binary encoding length. This is the bit-complexity guarantee of polynomial-time rational LP algorithms; see the introduction of [Adler and Beling’s research paper](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).
Its hypotheses hold here: the system is explicit, finite, linear, and rational. Applying such an algorithm therefore takes
\(\operatorname{poly}(N,R,H)=\operatorname{poly}(m,\tau,L)\)
bit operations. Section 2 proves that its answer is exactly the answer to the requested rational-allocation problem.
This bound uses the listed support size \(\tau\). It requires neither enumeration of unlisted possible types nor expansion of rational masses into individual consumers.
The finite-consumer problem imposes discrete choices that are absent here. Fractional allocation can change feasibility even in the smallest instance.
Take one type with mass \(\mu_t=1\), one contract with \(\ell_j=b_{tj}=2\), and thresholds \(\rho=z=1\). The rational allocation \(x_{tj}=1/2\) meets both thresholds exactly.
If this mass instead represented one indivisible consumer, choosing no contract would fail the reduction constraint, while choosing the contract would fail the cost constraint. Thus, a feasible fractional allocation need not yield a feasible indivisible assignment.
The stated distribution-over-types problem belongs to \(\mathrm{P}\). It could consequently be NP-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: feasibility is decidable in polynomial time in \(m,\tau,L\). The argument is rigorous, and no major or minor mathematical issues were found.
Verified. There is one variable for every explicitly supplied type–contract pair, giving \(N=\tau m\) variables.
The inequalities encode exactly the task’s requirements:
The count \(R=N+\tau+2\) is correct. All coefficients and right-hand sides are rational. Thus the asserted equivalence between feasible allocations and membership in \(P\cap\mathbb{Q}^{N}\) is exact.
Verified. Positive masses summing to one imply \(0<\mu_t\le 1\). Nonnegativity and the capacity constraint yield \(0\le x_{tj}\le\mu_t\) for every coordinate. Hence \(P\) is bounded.
The defining inequalities are non-strict, so \(P\) is closed. In finite-dimensional Euclidean space, closedness and boundedness imply compactness. These statements apply whenever \(P\) is nonempty; the argument does not assume feasibility prematurely.
Verified. Successive coordinate minimization is valid: each minimizer set is nonempty and compact, and after all coordinates have been fixed, it contains exactly one point \(v\).
The midpoint argument establishes extremality. If \(v\) is the midpoint of two points in \(P\), minimality of the first coordinate forces both endpoints to attain that minimum. Repeating this reasoning within each successive minimizer set forces agreement in every coordinate. Neither endpoint can differ from \(v\).
Using the midpoint characterization of extreme points is valid because \(P\) is convex.
Verified. If the tight constraint rows failed to span \(\mathbb{R}^{N}\), a nonzero vector orthogonal to all of them would exist. Perturbations in either direction preserve every tight equality.
The remaining constraints are finite in number and have positive slack, so sufficiently small perturbations preserve them as well. This contradicts extremality. The argument also covers the case where no constraints are slack.
Selecting \(N\) independent tight rows therefore produces a nonsingular rational system \(Bv=d'\). Cramer’s rule implies that every coordinate of \(v\) is rational. Consequently, real feasibility and rational feasibility coincide.
No polynomial bound on this particular witness’s encoding length is needed for the stated decision argument.
Verified. The dense system has \(R(N+1)\) entries, including right-hand sides. Each entry is an input rational, its negative, or a fixed constant, so its encoding length is \(O(L+1)\). The stated bound
\(H=O((\tau m+\tau+2)(\tau m+1)(L+1))\)
is conservative and polynomial in the requested parameters. Writing the explicit system also takes polynomial time.
The invoked theorem is stated sufficiently precisely: explicitly represented rational linear-inequality feasibility is decidable deterministically in polynomial bit complexity. The cited paper’s introduction confirms polynomial-time solvability of rational LPs in the number of coefficients and total binary encoding length. [Adler and Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf)
All hypotheses are satisfied. The algorithm decides exact feasibility, and the preceding rationality argument makes that decision applicable to the required rational allocations. The support representation requires no enumeration of additional types or expansion into individual consumers.
Verified. In the example, assigning mass \(1/2\) gives reduction \(1\) and cost \(1\). For one indivisible consumer, assigning nothing violates the reduction target, while assigning the contract incurs cost \(2>1\).
The example correctly demonstrates that fractional and indivisible feasibility can differ. It does not purport to disprove hardness by itself; the polynomial-time LP argument supplies the complexity conclusion.
The final qualification concerning NP-hardness is correct under polynomial-time many-one reductions.
No repair or additional clarification is needed. The prover establishes the requested polynomial-time classification, including the rational-allocation requirement and dependence on the listed support size.
⟨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.