Answer: Polynomial-time solvable: the decision problem belongs to \(\mathrm{P}\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an instance G of lung exchange, the prob- lem of deciding if G admits a non-trivial solution is NP- complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given patient types \(t\in T\) with rational masses \(\mu_t\) summing to \(1\), each endowed with two donor classes and a set of compatible donor classes, and the resulting donor-class supplies, determine whether a feasible allocation can reassign positive patient mass to pairs of compatible donor units while conserving every donor supply and allowing the remaining mass to keep its endowment. Each patient unit receives a whole pair; assignments may split across units of the same type.
Let \(C\) be an explicitly listed set of \(m\geq 1\) donor classes. A society is given by its support: the list of \(\tau\geq 1\) patient types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types. Let \(L\) be the total input bit length.
Each type \(t\) has an endowment of two distinct donor units with classes \(a_t,b_t\in C\), possibly equal, and an explicitly listed compatibility set \(D_t\subseteq C\). At least one of \(a_t,b_t\) lies outside \(D_t\).
The supply of class \(c\) is \(s_c=\sum_t\mu_t(\mathbf{1}_{a_t=c}+\mathbf{1}_{b_t=c})\).
An allocation may split each type's mass arbitrarily among assignments. Every patient unit either retains its own two donors or receives two distinct donor units whose classes both belong to \(D_t\); those classes may coincide. No donor unit is reused, and total consumption of every class equals its supply. Retained endowments consume their original supplies. Receiving one compatible donor and one incompatible donor is permitted only by retaining the entire endowment.
An allocation is non-trivial when strictly positive patient mass receives compatible pairs; there is no prescribed positive lower bound.
Is deciding whether a non-trivial allocation exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite societies with individually identified donors, existence of a non-trivial allocation is NP-complete, including instances where no endowment is fully compatible ([Luo and Tang, 2015](https://www.ijcai.org/Proceedings/15/Papers/036.pdf)).
No complexity result for this exact mass formulation was located in the literature search.
The decision problem is polynomial-time solvable. In fact, existence depends only on the supported types and their endowment and compatibility data; the values of their strictly positive masses do not affect the answer.
The proof uses a normalized linear program and verifies that its class-level flows can be realized by assignments of distinct donor units.
For each type \(t\) and class \(c\), define its endowment multiplicity
\(e_{tc}=\mathbf{1}_{a_t=c}+\mathbf{1}_{b_t=c}\).
Thus \(e_{tc}\in\{0,1,2\}\) and \(\sum_{c\in C}e_{tc}=2\).
Introduce nonnegative variables:
Consider the following feasibility problem:
\(q_t\geq 0,\qquad u_{tc}\geq 0.\)
\[\displaystyle \sum_t q_t=1.\tag{1}\]
\[\displaystyle \sum_{c\in D_t}u_{tc}=2q_t\qquad\text{for every type }t.\tag{2}\]
\[\displaystyle \sum_{t:\,c\in D_t}u_{tc}=\sum_t e_{tc}q_t\qquad\text{for every class }c.\tag{3}\]
Equation (2) supplies two compatible donors per participating patient. Equation (3) balances donors assigned to participants against the donors released by participants.
Claim. A non-trivial allocation exists if and only if this linear program is feasible.
Suppose a non-trivial allocation exists. Let \(x_t\) be the mass of type \(t\) receiving compatible pairs, and let \(v_{tc}\) be the mass of class-\(c\) donor units received by those patients. When a pair has both donors in class \(c\), it contributes twice its patient mass to \(v_{tc}\).
By the compatibility requirement, \(v_{tc}=0\) for \(c\notin D_t\). Since each participating patient receives two donors,
\(\displaystyle \sum_{c\in D_t}v_{tc}=2x_t.\)
The retained mass of type \(t\) is \(\mu_t-x_t\), and it consumes \(e_{tc}(\mu_t-x_t)\) units of class \(c\). Class conservation therefore gives
\(\displaystyle \sum_t e_{tc}(\mu_t-x_t)+\sum_{t:\,c\in D_t}v_{tc} =\sum_t e_{tc}\mu_t.\)
Subtracting the retained consumption yields
\(\displaystyle \sum_{t:\,c\in D_t}v_{tc}=\sum_t e_{tc}x_t.\)
Non-triviality means \(X=\sum_t x_t>0\). Setting \(q_t=x_t/X\) and \(u_{tc}=v_{tc}/X\) satisfies (1)–(3).
Suppose the linear program is feasible. Its coefficients are integers, so standard rational linear-programming feasibility guarantees a rational feasible point. Choose such a point \((q,u)\).
Because \(\sum_tq_t=1\), at least one \(q_t\) is positive. Define
\(\displaystyle \varepsilon=\min_{t:\,q_t>0}\frac{\mu_t}{q_t}>0,\qquad x_t=\varepsilon q_t,\qquad v_{tc}=\varepsilon u_{tc}.\)
Every supported mass is strictly positive, so the minimum is positive. By its definition, \(0\leq x_t\leq\mu_t\). Equations (2)–(3) imply
\[\displaystyle \sum_{c\in D_t}v_{tc}=2x_t,\qquad \sum_{t:\,c\in D_t}v_{tc}=\sum_t e_{tc}x_t.\tag{4}\]
We now verify that these aggregate quantities can be implemented with two distinct donor units per participating patient.
All the quantities \(\mu_t,x_t,v_{tc}\) are rational. Choose a positive integer \(N\) making all \(N\mu_t,Nx_t,Nv_{tc}\) integers. Under the permitted arbitrary mass splitting, represent type \(t\) by \(N\mu_t\) patient units, each of mass \(1/N\), each endowed with two distinct donor units of its prescribed classes.
For each type \(t\):
The participating donor pool contains exactly \(\sum_t Ne_{tc}x_t\) distinct units of class \(c\). By (4), this equals \(\sum_{t:\,c\in D_t}Nv_{tc}\). Consequently, for each class \(c\), partition its donor pool among types \(t\) in the prescribed integer quantities \(Nv_{tc}\).
Type \(t\) then receives exactly
\(\displaystyle \sum_{c\in D_t}Nv_{tc}=2Nx_t\)
distinct donor units, all with classes in \(D_t\). Partition these units into \(Nx_t\) pairs and give one pair to each participating patient unit.
Every pair contains two distinct donor units, including when their classes coincide. No donor is reused, and every donor is consumed exactly once. Retaining patients keep their original endowments; participating patients receive entirely compatible pairs. Thus the construction satisfies all allocation requirements.
Finally,
\(\displaystyle \sum_t x_t=\varepsilon\sum_tq_t=\varepsilon>0,\)
so the allocation is non-trivial. The hypothesis that no endowment is fully compatible ensures that retained patients do not contribute to this compatible-pair mass.
This proves the claim.
The linear program has
\(\displaystyle \tau+\sum_t|D_t|\leq\tau(m+1)\)
variables and \(\tau+m+1\) equalities, together with nonnegativity constraints. Every coefficient and right-hand side belongs to \(\{-2,-1,0,1,2\}\). Its encoding length is therefore polynomial in \(m,\tau,L\), and rational linear-programming feasibility is decidable in polynomial time.
The algorithm constructs this linear program and answers “yes” exactly when it is feasible. No numerical threshold for a strictly positive exchange is needed: normalization (1) detects a nonzero exchange pattern, and the positive scaling factor \(\varepsilon\) makes it fit the given masses.
Because the linear program does not contain the masses, the proof also establishes the asserted independence from their positive values.
The finite-society NP-completeness result concerns indivisible patients and individually identified donors. [Luo and Tang’s formulation](https://www.ijcai.org/Proceedings/15/Papers/036.pdf) requires each original patient to receive a complete assignment. Here, arbitrary mass splitting permits the refinement used above; its denominator need not be enumerated by the decision algorithm.
⟨structured verdict parsed — rendered above⟩
Result: proved. The normalized linear program correctly decides existence of a non-trivial allocation under the stated arbitrary mass splitting model. The realization argument respects donor identity, complete retention, compatibility, and class conservation. No major or minor mathematical issues were found.
The endowment multiplicities \(e_{tc}\) correctly count donor units, including the case \(a_t=b_t\), when \(e_{tc}=2\). In every case, \(\sum_c e_{tc}=2\).
The variables \(u_{tc}\) measure donor mass rather than patient mass. Consequently, equation (2), \(\sum_{c\in D_t}u_{tc}=2q_t\), has the correct factor of two. Variables exist only for compatible classes, so incompatible donor assignments are excluded.
Equation (3) correctly balances compatible donor consumption against the endowments released by participating patients. Retained endowments cancel from this balance.
The normalization \(\sum_tq_t=1\) excludes the zero exchange pattern. Omitting the upper bounds supplied by the masses is justified by the subsequent scaling argument; it is not an unsupported relaxation.
The hypothesis that at least one endowed class lies outside \(D_t\) ensures that retaining an endowment never counts as receiving a compatible pair. Thus the allocation separates into retained mass \(\mu_t-x_t\) and participating mass \(x_t\), without ambiguity.
The definition of \(v_{tc}\) correctly counts a same-class pair twice. Hence the patient-level requirement gives \(\sum_{c\in D_t}v_{tc}=2x_t\).
The displayed conservation equation includes both retained consumption and compatible-pair consumption. Subtracting retained consumption gives precisely
\[
\sum_{t:\,c\in D_t}v_{tc}=\sum_t e_{tc}x_t.
\]
Non-triviality supplies \(X=\sum_tx_t>0\), so division by \(X\) is legitimate. The resulting \(q_t=x_t/X\) and \(u_{tc}=v_{tc}/X\) satisfy nonnegativity and all three LP equations. This direction is complete.
The rational-feasibility theorem used here states that a nonempty polyhedron defined by rational linear equalities and inequalities contains a rational point. Its hypotheses hold: the LP has finitely many variables and integer coefficients and right-hand sides.
Normalization and nonnegativity ensure that the set of types with \(q_t>0\) is nonempty. It is finite, and every supported \(\mu_t\) is strictly positive. Therefore the stated minimum
\[
\varepsilon=\min_{t:\,q_t>0}\frac{\mu_t}{q_t}
\]
exists and is positive.
For \(q_t>0\), its definition gives \(x_t=\varepsilon q_t\leq\mu_t\). For \(q_t=0\), \(x_t=0\). Equation (2) also forces every \(u_{tc}\) for such a type to vanish, so no donor mass is assigned to a type with zero participating mass.
Scaling preserves both row totals and class conservation. All scaled quantities are rational.
A common denominator \(N\) exists for the finite collection of rational quantities. Both \(Nx_t\) and \(N(\mu_t-x_t)\) are nonnegative integers. The refinement into units of mass \(1/N\) is permitted by the task’s arbitrary mass splitting assumption.
The construction correctly separates retained donors from released donors:
Partitioning each class pool therefore assigns every released donor exactly once. Each type receives exactly \(2Nx_t\) distinct donors, all belonging to compatible classes. Pairing that pool produces \(Nx_t\) pairs of distinct donor units. Equality of the two classes in a pair does not identify the two units.
There is no additional pairing restriction in the task: compatibility depends only on each donor’s class. Thus arbitrary pairing within a type’s assigned pool is valid.
Together with retention, the construction consumes every donor exactly once and satisfies every allocation requirement. Finally, \(\sum_tx_t=\varepsilon>0\) verifies non-triviality. This direction is complete.
The variable and equality counts are correct. The coefficient bound is also correct: after collecting terms, every coefficient and right-hand side belongs to \(\{-2,-1,0,1,2\}\).
The polynomial-time theorem invoked is rational linear-programming feasibility in the binary encoding model. Its hypotheses are satisfied, and the explicitly constructed LP has encoding length polynomial in \(m,\tau,L\).
The decision algorithm only tests LP feasibility. It need not enumerate the refined society or its common denominator \(N\). Consequently, the potentially large refinement does not invalidate the running-time claim.
The masses enter only the positive scaling argument. Their strict positivity therefore establishes the claimed independence from their numerical values.
The argument covers empty compatibility sets: equation (2) forces the corresponding \(q_t\) to vanish. It also covers unused classes, repeated endowment classes, same-class received pairs, and either \(m=1\) or \(\tau=1\). None requires an additional assumption.
The comparison with finite societies is accurate. Luo and Tang’s Definition 1 requires two distinct compatible donors or complete retention, with every donor assigned exactly once. Their indivisible model does not permit the refinement used here. [Luo and Tang, 2015](https://www.ijcai.org/Proceedings/15/Papers/036.pdf).
Required repair or clarification: none.
⟨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.