Answer: polynomial-time solvable
Theorem 3.7 — class: hardness
The ARH problem is NP-complete even if the topol- ogy is a graph of maximum degree 3 and all inhabitants approve intervals.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite host types \(H\), housing types \(P\), rational capacities \(b_p\), refugee mass \(\rho\), costs \(c_p\), exposures \(w_{hp}\), and host acceptance intervals \([\ell_h,u_h]\) with \(d_h=\sum_{p\in P}w_{hp}b_p>0\), decide whether there is \(x\in\mathbb{R}_{\geq0}^{P}\) such that \(x_p\leq b_p\), \(\sum_{p\in P}x_p=\rho\), and \(\ell_h\leq \sum_{p\in P}w_{hp}x_p/d_h\leq u_h\) for every \(h\in H\); optionally minimize \(\sum_{p\in P}c_px_p\).
Definitions. An instance has finite sets of host types \(H\) and housing types \(P\), rational \(b_p,\rho\ge0\), \(w_{hp}\ge0\), and \(\ell_h\le u_h\), with \(\sum_p w_{hp}b_p>0\) for every \(h\). A feasible housing is a real vector \(x\) satisfying \(0\le x_p\le b_p\), \(\sum_p x_p=\rho\), and \(\ell_h\le \frac{\sum_p w_{hp}x_p}{\sum_p w_{hp}b_p}\le u_h\) for every \(h\).
Target. Is continuous interval-housing feasibility solvable in polynomial time, or is it NP-hard?
Nearest known results. The discrete counterpart, obtained by requiring \(x_p\in\{0,1\}\) for individual empty housing vertices and using adjacency incidences as \(w_{hp}\), is NP-complete even when the topology has maximum degree three and every host approves an interval of refugee counts.
Continuous interval-housing feasibility with rational input data is solvable in polynomial time.
For each host type $h\in H$, define the constant
$$ D_h=\sum_{p\in P}w_{hp}b_p. $$
By hypothesis, $D_h>0$. Therefore multiplying the host constraint by $D_h$ preserves both inequality directions:
$$ \ell_h \le \frac{\sum_{p\in P}w_{hp}x_p}{D_h} \le u_h $$
is equivalent to the pair of linear inequalities
$$ \sum_{p\in P}w_{hp}x_p\le u_hD_h $$
and
$$ -\sum_{p\in P}w_{hp}x_p\le-\ell_hD_h. $$
The denominator depends only on the input data, not on the variables. Thus the normalized host constraints introduce no nonlinearity.
The instance is feasible exactly when the following rational linear system has a solution:
$$ -x_p\le0 \qquad\text{for every }p\in P, $$
$$ x_p\le b_p \qquad\text{for every }p\in P, $$
$$ \sum_{p\in P}x_p\le\rho, $$
$$ -\sum_{p\in P}x_p\le-\rho, $$
and, for every $h\in H$,
$$ \sum_{p\in P}w_{hp}x_p\le u_hD_h, $$
$$ -\sum_{p\in P}w_{hp}x_p\le-\ell_hD_h. $$
The two inequalities involving $\rho$ are equivalent to the equality $\sum_p x_p=\rho$. Hence this system is equivalent to the original definition in both directions.
It has $|P|$ variables and
$$ 2|P|+2+2|H| $$
linear inequalities.
Assume, as required for a standard complexity-theoretic formulation, that all numbers $b_p,\rho,w_{hp},\ell_h,u_h$ are rational numbers encoded in binary.
Each $D_h$ is obtained using $|P|$ rational multiplications and additions. Products and sums of binary-encoded rationals can be computed exactly in polynomial time, and the resulting numerator and denominator have bit length polynomial in the total input length. Multiplication by $\ell_h$ or $u_h$ also increases the bit length by at most a polynomial amount.
Consequently, the displayed rational linear system can be constructed in polynomial time and has encoding length polynomial in the original instance size.
The feasibility of a system of rational linear inequalities
$$ Ax\le c $$
is decidable in time polynomial in the numbers of rows and columns and in the binary encoding length of $A$ and $c`, for example by the rational ellipsoid method.
Applying this theorem to the equivalent system above gives a polynomial-time algorithm:
This is an exact decision procedure; it does not rely on numerical approximation or on the existence of an interior point.
The continuous formulation is a rational linear-programming feasibility problem and therefore belongs to $\mathrm{P}$. The NP-completeness of the discrete counterpart arises from the integrality restrictions $x_p\in\{0,1\}$; those restrictions are absent here.
Strictly speaking, membership in $\mathrm{P}$ does not unconditionally exclude NP-hardness, since a problem in $\mathrm{P}$ could be NP-hard if $\mathrm{P}=\mathrm{NP}$. The unconditional classification established here is polynomial-time solvability.
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces continuous interval-housing feasibility to rational linear-program feasibility. The reduction is exact, has polynomial encoding size, and invokes the standard polynomial-time solvability of rational linear programming with the required hypotheses satisfied.
The argument establishes the claimed polynomial-time classification. The only issue is a harmless formatting typo in the statement of the linear-programming theorem.
For each $h$, the prover defines
$$ D_h=\sum_{p\in P}w_{hp}b_p. $$
This is exactly the denominator appearing in the definition. The stated hypothesis gives $D_h>0$, so multiplication by $D_h$ is valid and preserves both inequality directions.
The equivalence between
$$ \ell_h\le \frac{\sum_p w_{hp}x_p}{D_h}\le u_h $$
and the two displayed linear inequalities is correct. In particular, $D_h$ depends only on input data, so no nonlinear variable products are introduced.
The bounds $0\le x_p\le b_p$ are correctly represented by $-x_p\le0$ and $x_p\le b_p$.
The pair
$$ \sum_p x_p\le\rho, \qquad -\sum_p x_p\le-\rho $$
is exactly equivalent to $\sum_p x_p=\rho$.
The two inequalities for each host are likewise exactly equivalent to its original interval constraint. Thus every feasible housing satisfies the displayed linear system, and every solution of the displayed system is a feasible housing.
The count $2|P|+2+2|H|$ of displayed inequalities is correct.
The prover appropriately interprets the rational inputs as binary-encoded, as required for a complexity classification.
Exact multiplication and addition of the input rationals can be performed in polynomial time. Even without cancellation, the bit length of a common denominator formed from the input denominators is bounded by the sum of their bit lengths, hence by the total input length. Therefore each $D_h$, $u_hD_h$, and $\ell_hD_h$ has polynomially bounded encoding length.
Since the input explicitly contains the $|H||P|$ weights, constructing all coefficients and right-hand sides also takes polynomial time in the total input size.
The invoked result—that feasibility of a binary-encoded rational system $Ax\le c$ is decidable in polynomial time—is standard. The constructed system has rational coefficients, polynomially many rows and columns, and polynomial total encoding length, so all relevant hypotheses are met.
The presence of equality constraints encoded as pairs of inequalities, possible lower-dimensional feasible regions, and lack of strict feasibility do not invalidate the rational linear-programming feasibility theorem.
It follows correctly that the continuous problem belongs to $\mathrm P$. The observation that this does not logically rule out NP-hardness unless $\mathrm P\ne\mathrm{NP}$ is accurate.
The distinction from the cited discrete problem is also correctly identified: the continuous formulation lacks the binary integrality constraints responsible for the combinatorial problem.
The theorem statement contains the malformed fragment $A$ and $c` rather than a correctly closed mathematical delimiter. This is purely typographical and does not create uncertainty about the theorem being invoked.
⟨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.