Answer: \(\mathrm{NP\text{-}complete}\)
Proposition 4.4 — class: algorithmic
Given candidates \(C\), committee size \(k\), a supplied candidate order, and rational masses \(\mu_t\) on approval types \(I_t\subseteq C\), each an interval, choose \(W\subseteq C\) with \(|W|=k\) maximizing \(Pairs_\infty(\mu,W)=\sum_{t,u}\mu_t\mu_u\mathbf{1}[I_t\cap I_u\cap W\neq\varnothing]\); equivalently, decide whether this value is at least a rational threshold \(q\).
Given a finite candidate set \(C\), an integer \(k\), and approval types \((A_t,\mu_t)\) with \(A_t\subseteq C\), \(\mu_t\in\mathbb{Q}_{\ge 0}\), and \(\sum_t\mu_t=1\), form the graph on positive-mass types in which \(s,t\) are adjacent when \(A_s\cap A_t\cap W\ne\varnothing\). A \(W\)-connected component has mass equal to the sum of its types' masses, and \(\mathrm{Cons}_\infty(W,\mu)\) is the sum of squared component masses.
Target: Is deciding whether there exists \(W\subseteq C\) with \(|W|=k\) and \(\mathrm{Cons}_\infty(W,\mu)=1\) solvable in polynomial time, or is it NP-hard?
Known discrete result: for a finite list of voters, deciding whether a size-\(k\) committee connects all voters is NP-complete.
Continuous side: no result for this exact finite approval-type distribution problem is stated in the supplied source.
The decision problem is \( \mathrm{NP\text{-}complete} \). In particular, it is \( \mathrm{NP\text{-}hard} \) even when every approval type has the same positive mass.
Fix a committee \(W\). Let the connected components of the graph on positive-mass types be \(K_1,\ldots,K_q\), and define their masses by
\[ x_i=\sum_{t\in K_i}\mu_t. \]
Every \(x_i\) is strictly positive, and, because zero-mass types are excluded and the total type mass is \(1\),
\[ \sum_{i=1}^{q}x_i=1. \]
Consequently,
\[ 1-\mathrm{Cons}_\infty(W,\mu) = \left(\sum_{i=1}^{q}x_i\right)^2-\sum_{i=1}^{q}x_i^2 = 2\sum_{1\leq i<j\leq q}x_ix_j. \]
If \(q=1\), the right-hand side is \(0\), so \(\mathrm{Cons}_\infty(W,\mu)=1\).
If \(q\geq 2\), at least one product \(x_ix_j\) is strictly positive. Hence
\[ \mathrm{Cons}_\infty(W,\mu)<1. \]
Thus
\[ \mathrm{Cons}_\infty(W,\mu)=1 \quad\Longleftrightarrow\quad \text{the positive-mass type graph induced by $W$ is connected.} \]
A certificate is a subset \(W\subseteq C\) of size \(k\).
The verifier checks \(|W|=k\), constructs the graph whose vertices are the positive-mass types, and adds an edge between \(s\) and \(t\) exactly when
\[ A_s\cap A_t\cap W\neq\varnothing. \]
These intersections and graph connectivity can be tested in polynomial time. By the lemma, the graph is connected exactly when \(\mathrm{Cons}_\infty(W,\mu)=1\). Therefore the problem belongs to \( \mathrm{NP} \).
Consider an instance of the supplied \( \mathrm{NP\text{-}complete} \) discrete problem. It consists of candidates \(C\), approval sets
\[ B_1,\ldots,B_n\subseteq C, \]
and a target committee size \(k\). The question is whether some size-\(k\) committee connects all \(n\) voters.
Construct a continuous instance with one indexed type for each voter:
\[ A_i=B_i, \qquad \mu_i=\frac{1}{n} \quad\text{for every $i\in\{1,\ldots,n\}$.} \]
All masses are positive and satisfy
\[ \sum_{i=1}^{n}\mu_i=1. \]
For every committee \(W\subseteq C\) and every pair \(i,j\),
\[ A_i\cap A_j\cap W\neq\varnothing \quad\Longleftrightarrow\quad B_i\cap B_j\cap W\neq\varnothing. \]
Therefore the graph on continuous types is exactly the graph on voters in the discrete instance. It follows that
\[ W\text{ connects all discrete voters} \quad\Longleftrightarrow\quad \mathrm{Cons}_\infty(W,\mu)=1. \]
The reduction preserves \(C\) and \(k\). Each mass \(1/n\) has encoding length \(O(\log n)\), so the construction is polynomial-time.
Hence the continuous problem is \( \mathrm{NP\text{-}hard} \), already under equal masses. Together with membership in \( \mathrm{NP} \), it is \( \mathrm{NP\text{-}complete} \).
If “types” are required to have pairwise distinct approval sets, equal discrete ballots can instead be aggregated. For each distinct approval set \(D_j\), let \(m_j\) be its multiplicity and assign it mass \(m_j/n\).
When there are at least two distinct approval sets, the voter graph is connected if and only if the aggregated type graph is connected:
The case of only one distinct approval set is directly decidable and can be mapped to a fixed yes-instance or no-instance. Thus the hardness conclusion remains valid under the distinct-type convention as well.
⟨structured verdict parsed — rendered above⟩
The reduction correctly transfers the supplied discrete connectivity problem to the finite approval-type distribution problem. The connectivity lemma, NP-membership argument, and reduction are sound. Only minor edge-case and presentation clarifications are missing.
For connected-component masses \(x_1,\ldots,x_q\), the prover correctly establishes:
\[ \sum_{i=1}^q x_i=1 \]
and
\[ 1-\mathrm{Cons}_\infty(W,\mu) =2\sum_{1\leq i<j\leq q}x_ix_j. \]
Each component contains a positive-mass type, so every \(x_i>0\). Therefore:
This proves the claimed equivalence. Since the total mass is \(1\), the positive-mass graph is nonempty, so no empty-graph convention is needed.
A committee \(W\) is a polynomial-size certificate. Under the natural explicit encoding of candidates and approval sets, the verifier can construct the type graph and test its connectivity in polynomial time. By the preceding equivalence, this suffices to verify \(\mathrm{Cons}_\infty(W,\mu)=1\) without performing potentially delicate rational arithmetic.
This part is correct.
Assigning
\[ A_i=B_i,\qquad \mu_i=\frac1n \]
preserves every graph adjacency because the two edge predicates are literally identical. Hence a committee connects all discrete voters exactly when the resulting positive-mass type graph is connected, and therefore exactly when its consistency is \(1\).
The rational number \(1/n\) has polynomial encoding length, and the construction has polynomial size. Thus the reduction proves NP-hardness, including under equal masses.
There is one minor edge case: the construction uses \(1/n\) without explicitly assuming \(n\geq1\). The supplied description says “a finite list of voters” but does not expressly exclude an empty list. The prover should state that the source NP-hardness is restricted to nonempty voter instances or separately dispose of \(n=0\). This is routine and does not affect the substantive reduction.
The main task does not require pairwise distinct approval sets, so this remark is not necessary for the principal conclusion.
Its equivalence argument is substantively sound when there are at least two distinct approval sets. In that situation, connectivity of the aggregated graph forces every aggregated vertex to have a neighbor, which ensures each corresponding approval set meets \(W\); duplicate voters of that type consequently form a clique.
For the one-distinct-type case, however, the write-up merely says that the instance can be mapped to a fixed yes-instance or no-instance. A formally specified many-one reduction should state the exact decision criterion for this exceptional case and identify valid fixed target instances. This is an omitted routine specification, not a mathematical obstruction.
The prover correctly establishes that the problem is NP-complete. The omissions concern only easily isolated boundary cases and the optional distinct-type refinement; no central inference is false or unsupported.
⟨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.