Answer: \(\mathrm{NP\text{-}complete}\), and hence \(\mathrm{NP\text{-}hard}\), even for any fixed rational \(\alpha\in[0,1)\)
Theorem 4.5 — class: algorithmic
Given finite \(V\subseteq\mathbb Q\), budget \(b\), \(\alpha\in[0,1)\), finite endpoint types \(\Theta\subseteq V^2\), and rational masses \(\mu\), output \(S\subseteq V\) with \(|S|\le b\) such that for every \(R\subseteq V\), \(\mu(\{\theta:c_\theta(R)<c_\theta(S)\})<2|R|/b\), where \(c_\theta(S)=\min\{r_\theta-\ell_\theta,\min_{x,y\in S}(|\ell_\theta-x|+\alpha|x-y|+|r_\theta-y|)\}\).
Given a finite \(V\subseteq\mathbb{Q}\), a finite type set \(T\subseteq\{(\ell,r)\in V^2:\ell<r\}\), rational masses \((\mu_\theta)_{\theta\in T}\) summing to \(1\), rational \(\alpha\in[0,1)\), binary-encoded costs \(\gamma:V\to\mathbb{N}\), budget \(B\), and threshold \(q\), choose an integral set \(S\subseteq V\).
For \(\theta=(\ell,r)\), let \(c_\theta(S)=\min\{r-\ell,\min_{x,y\in S}(|\ell-x|+\alpha|x-y|+|r-y|)\}\), with \(c_\theta(\varnothing)=r-\ell\). A set is feasible if \(\sum_{v\in S}\gamma(v)\le B\).
Target. Is deciding whether a feasible \(S\) satisfies \(\sum_{\theta\in T}\mu_\theta c_\theta(S)\le q\) NP-hard, or solvable in polynomial time?
For explicitly listed finite agents, the analogous problem with binary-encoded stop-construction costs is NP-complete for every fixed \(\alpha\in[0,1)\).
For uniform stop costs, minimum-total-cost bus-stop selection for finite agent lists is computable in polynomial time; this does not cover binary-encoded \(\gamma\).
The decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when \(\alpha\) is fixed to any rational constant \(\alpha_0\in[0,1)\).
A certificate is the incidence vector of a set \(S\subseteq V\), whose length is \(\lvert V\rvert\).
First compute \(\sum_{v\in S}\gamma(v)\) and verify that it is at most \(B\). For every \(\theta=(\ell,r)\in T\), compute
\[ c_\theta(S)= \min\left\{ r-\ell,\; \min_{(x,y)\in S^2} \bigl( \lvert \ell-x\rvert+\alpha\lvert x-y\rvert+\lvert r-y\rvert \bigr) \right\}. \]
There are at most \(\lvert V\rvert^2\) ordered pairs \((x,y)\) for each type. Thus all values \(c_\theta(S)\) can be computed using \(O(\lvert T\rvert\lvert V\rvert^2)\) rational-arithmetic operations. When \(S=\varnothing\), the prescribed value \(c_\theta(S)=r-\ell\) is used directly.
All input numbers are binary-encoded rationals or integers. Addition, multiplication, absolute value, and comparison of the resulting rationals have polynomial bit complexity: the bit length of a common denominator obtained from polynomially many input rationals is at most the sum of their input bit lengths. Consequently, one can verify exactly whether
\[ \sum_{\theta\in T}\mu_\theta c_\theta(S)\leq q \]
in polynomial time. Hence the problem belongs to \(\mathrm{NP}\).
Use the premise that the analogous finite-agent problem with binary-encoded construction costs is \(\mathrm{NP}\)-complete for every fixed \(\alpha_0\in[0,1)\).
Fix such a rational \(\alpha_0\), for example \(\alpha_0=0\). Consider an instance of that finite-agent problem with agents
\[ \theta_1,\ldots,\theta_n, \]
where every \(\theta_i=(\ell_i,r_i)\) belongs to \(\{(\ell,r)\in V^2:\ell<r\}\). Suppose its objective is the unnormalized total cost
\[ \sum_{i=1}^n c_{\theta_i}(S), \]
and its threshold is \(Q\).
For each distinct type \(\theta\) occurring among the agents, let
\[ m_\theta=\bigl\lvert\{i:\theta_i=\theta\}\bigr\rvert. \]
Construct the type-mass instance by setting
\[ T=\{\theta_i:1\leq i\leq n\}, \qquad \mu_\theta=\frac{m_\theta}{n}, \qquad q=\frac{Q}{n}. \]
Keep \(V\), \(\gamma\), \(B\), and \(\alpha_0\) unchanged. The masses are positive rationals satisfying
\[ \sum_{\theta\in T}\mu_\theta = \frac{1}{n}\sum_{\theta\in T}m_\theta = 1. \]
For every \(S\subseteq V\), repeated agents of the same type have the same travel cost. Therefore
\[ \begin{aligned} \sum_{\theta\in T}\mu_\theta c_\theta(S) &= \frac{1}{n}\sum_{\theta\in T}m_\theta c_\theta(S)\\ &= \frac{1}{n}\sum_{i=1}^n c_{\theta_i}(S). \end{aligned} \]
It follows that
\[ \sum_{\theta\in T}\mu_\theta c_\theta(S)\leq q \quad\Longleftrightarrow\quad \sum_{i=1}^n c_{\theta_i}(S)\leq Q. \]
The feasible sets are identical because the construction costs and budget are unchanged. If the finite-agent formulation already uses average rather than total cost, one simply keeps its threshold unchanged.
The transformation is polynomial-time: \(\lvert T\rvert\leq n\), the multiplicities can be counted in polynomial time, and each rational \(m_\theta/n\) has polynomial encoding length.
Thus every finite-agent instance is represented exactly by a type-mass instance. The target problem is therefore \(\mathrm{NP}\)-hard, even for fixed \(\alpha_0\).
The rational type-mass representation does not remove the finite-agent hardness: explicitly listed agents can be grouped by type without changing the objective. Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness.
The polynomial-time result for uniform construction costs does not apply because the reduction retains arbitrary binary-encoded values of \(\gamma(v)\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes \( \mathrm{NP} \)-completeness, assuming the finite-agent hardness statement supplied in the task. The reduction is an exact aggregation of duplicate agent types and preserves feasibility and the decision threshold.
A set \( S\subseteq V \) has an incidence-vector certificate of polynomial length. The budget can be checked exactly in polynomial time.
For each \( \theta\in T \), enumerating all ordered pairs in \( S^2 \) requires at most \( |V|^2 \) evaluations. The special case \( S=\varnothing \) is handled consistently with the definition.
Every evaluated expression uses polynomially many arithmetic operations on binary-encoded rationals. Numerator and denominator lengths remain polynomially bounded, so the weighted objective and comparison with \( q \) are exactly computable in polynomial time.
The reduction uses precisely the finite-agent \( \mathrm{NP} \)-completeness premise supplied in the task, retaining \( V \), \( \gamma \), \( B \), and the fixed rational value of \( \alpha \).
Assigning \( \mu_\theta=m_\theta/n \) gives masses summing to \( 1 \). The displayed identity
\[
\sum_{\theta\in T}\mu_\theta c_\theta(S)
=
\frac{1}{n}\sum_{i=1}^n c_{\theta_i}(S)
\]
is correct because duplicate agents of the same type have identical costs.
Setting \( q=Q/n \) makes the source and target objective inequalities equivalent for every \( S\subseteq V \). Feasibility is unchanged.
The number of distinct types is at most \( n \), multiplicities are computable in polynomial time, and each mass \( m_\theta/n \) has polynomial binary encoding length.
Hardness holds even after fixing any rational \( \alpha_0\in[0,1) \), while membership in \( \mathrm{NP} \) holds for the general input problem. Thus the claimed \( \mathrm{NP} \)-completeness follows.
No substantive gaps, false statements, or unverified applications remain.
⟨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.