Answer: Polynomial-time solvable: \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf an item graph is created that consists of two disconnected line graphs, and bidders are permitted to bun- dle one connected component from each line, then determin- ing if the auction can generate revenue r is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two paths with resource categories \(I\), a finite support \(T\) of bid types with rational masses \(\mu_t>0\) summing to \(1\), packages \(S_t\subseteq I\) that are unions of at most one interval from each path, prices \(p_t\), per-capita supplies \(\sigma_i\), and a revenue threshold \(R\), decide whether accepted masses \(y_t\) exist such that \(0\le y_t\le\mu_t\), \(\sum_{t:i\in S_t}y_t\le\sigma_i\) for every \(i\in I\), and \(\sum_{t\in T}p_ty_t\ge R\). Each individual receives the whole package or nothing; \(y_t\) is the accepted mass of type \(t\).
Given two nonempty vertex-disjoint paths whose resource categories form a set \(I\), let \(m=|I|\). A society is given by its support: a list \(T\) of \(\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 \(t\) bids a nonnegative binary-rational price \(p_t\) for a nonempty package \(S_t\subseteq I\), consisting of at most one interval from each path; either interval may be absent. Each individual receives the entire package or nothing.
The input also specifies nonnegative binary-rational per-capita supplies \(\sigma_i\) and a binary-rational revenue threshold \(R\). Unused resources are allowed, and there are no exclusivity constraints between bids beyond resource capacities. Let \(L\) be the total binary encoding length of the input.
Decide whether real accepted masses \(y_t\) exist satisfying \(0\le y_t\le\mu_t\), \(\sum_{t:i\in S_t}y_t\le\sigma_i\) for every \(i\in I\), and \(\sum_{t\in T}p_ty_t\ge R\).
Is this continuous revenue-threshold problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete bids and one unit of each item, deciding whether disjoint accepted packages reach a revenue threshold is \(\mathrm{NP}\)-complete on two disjoint paths, even with bid prices in \(\{1,2\}\). This discrete result does not classify the continuous problem stated here.
The continuous revenue-threshold problem belongs to \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). The proof applies to arbitrary explicitly listed packages; the two-path interval restriction is unnecessary.
Index the resource categories by \(I=\{1,\ldots,m\}\) and the supported types by \(T=\{1,\ldots,\tau\}\). Define the incidence matrix \(A\in\{0,1\}^{m\times\tau}\) by
\(A_{it}=1\) if \(i\in S_t\), and \(A_{it}=0\) otherwise.
Introduce one real variable \(y_t\) for each supported type. Consider the following system:
This system has \(\tau\) variables and \(k=m+2\tau+1\) inequalities.
Its feasibility is exactly the question asked. Indeed, the first two families impose the accepted-mass bounds, the third imposes precisely the resource capacities, and the last is equivalent to the revenue requirement. Thus a vector satisfies this system if and only if it is an admissible accepted-mass vector reaching the threshold.
In particular, there is no enumeration of possible types: only the \(\tau\) types in the supplied support become variables.
The matrix \(A\) can be constructed by checking membership in the listed intervals for every resource-type pair. This takes polynomial time in \(m,\tau,L\).
All coefficients in the feasibility system are either \(0\), \(1\), \(-1\), or rational numbers already present in the input, possibly with their signs reversed. Every such coefficient therefore has encoding length at most \(O(L+1)\). A dense representation of the entire system consequently has total encoding length
\(B=O\bigl((m+2\tau+1)(\tau+1)(L+1)\bigr)\),
which is polynomial in \(m,\tau,L\).
For completeness, rational inequalities can also be converted to integer inequalities without superpolynomial growth. For each row, multiply by the product of the positive denominators occurring in that row. This preserves the inequality because the multiplier is positive. The product’s bit length is at most the sum of the denominators’ bit lengths. Hence every resulting integer coefficient has bit length \(O(B+1)\), and the entire integer system still has polynomial encoding length.
We use the following standard linear-programming theorem:
Polynomial-time linear feasibility theorem. Given an explicitly encoded finite system \(Cx\le d\) with integer coefficients, a deterministic algorithm decides whether it has a solution over the real numbers in time polynomial in its total binary encoding length.
This is the feasibility result established by [Khachiyan’s polynomial-time linear-programming algorithm](https://www.mathnet.ru/eng/dan42319). It applies to arbitrary systems, including infeasible systems and systems whose feasible sets have empty interior. Its conclusion is an exact feasibility decision.
The integer system constructed above meets every hypothesis: it is finite, explicitly represented, and has integer coefficients with polynomial total encoding length. Applying the theorem therefore decides the original problem in time polynomial in \(m,\tau,L\).
Including the revenue inequality directly in the system also handles the boundary case where attainable revenue equals \(R\). No approximation of the optimal revenue or numerical tolerance is needed.
The stated model allows every real mass \(y_t\) in the interval \(0\le y_t\le\mu_t\). These are precisely linear constraints.
Discrete bid acceptance instead requires a binary decision for each bid. Those integrality requirements are absent here. Accepting a fraction of a type’s population is permitted by the continuous model, while each accepted individual still receives the whole package. Consequently, the discrete hardness theorem supplies no hardness classification for this linear feasibility problem.
The requested classification is therefore polynomial-time solvable. As usual, this does not rule out being \(\mathrm{NP}\)-hard under the hypothesis \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The continuous revenue-threshold problem belongs to \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). No major or minor mathematical issues were found.
There is one real variable \(y_t\) for each of the \(\tau\) supported types. The inequalities \(-y_t\le 0\) and \(y_t\le\mu_t\) impose exactly \(0\le y_t\le\mu_t\).
By the definition of \(A\), the resource inequality \(\sum_{t=1}^{\tau}A_{it}y_t\le\sigma_i\) is precisely the capacity constraint for resource \(i\). Negating both sides of the revenue requirement correctly gives \(-\sum_{t=1}^{\tau}p_ty_t\le-R\).
Consequently, feasibility of the constructed system is equivalent in both directions to the requested decision problem. No integrality or additional exclusivity constraint has been introduced.
The system contains \(\tau\) variables and \(m+2\tau+1\) inequalities: \(2\tau\) accepted-mass bounds, \(m\) resource constraints, and one revenue constraint.
Only the supplied support is used. The proof does not confuse \(\tau\) with the number of possible packages or types.
Checking resource membership in each listed interval constructs \(A\) in time polynomial in \(m,\tau,L\). Absent intervals cause no ambiguity: they contribute no membership on their respective paths.
Every coefficient and right-hand side is a constant or an input rational, possibly negated. Thus the stated dense encoding bound
\[
B=O\bigl((m+2\tau+1)(\tau+1)(L+1)\bigr)
\]
is valid. It is conservative but sufficient.
Multiplying an inequality by the product of its positive denominators preserves its direction and solution set. The reference to denominators “occurring in that row” naturally includes the right-hand side.
The product has bit length bounded by the sum of the denominator bit lengths. Each resulting integer coefficient therefore has bit length \(O(B+1)\). Since the number of entries is also polynomially bounded, the entire integer system has polynomial encoding length. Computing these products and scaled coefficients likewise requires only polynomial time using ordinary integer arithmetic.
The stated theorem concerns exact real feasibility of an explicitly encoded finite system of integer linear inequalities, with deterministic running time polynomial in binary encoding length. This is the appropriate theorem, rather than an approximate optimization guarantee.
The cited [Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time decision of linear-inequality feasibility over the reals. The treatment of arbitrary feasible sets, including those with empty interior, is also explicitly covered in [MIT’s presentation of the feasibility theorem](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Every hypothesis is satisfied by the constructed integer system. Its polynomial encoding bound therefore yields the claimed running time polynomial in \(m,\tau,L\).
All inequalities are non-strict, so equality with the revenue threshold is included. Zero supplies, zero prices, negative or zero thresholds, and infeasible thresholds require no separate algorithmic treatment. Lower-dimensional feasible sets are covered by the stated theorem.
The discrete hardness result concerns integrality restrictions absent from this formulation. Fractional accepted population masses are expressly permitted by the task; they do not mean that an accepted individual receives only part of a package. The proof correctly concludes polynomial-time solvability without assuming any separation between \(\mathrm{P}\) and \(\mathrm{NP}\).
None. No additional lemma, hypothesis, or clarification is needed to make the argument verifiable.
⟨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.