Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions; \(\mathrm{NP}\)-hard under polynomial-time Turing reductions.
Theorem 14 — class: hardness
Continuous-EJR-Verification: given candidates \(C\), committee size \(k\), an explicit finite support \(T\subseteq 2^C\) with rational masses \(\mu_A\) summing to \(1\), and an integral committee \(W\subseteq C\) of size \(k\), decide whether for every \(1\le \ell\le k\) and every \(S\subseteq C\) with \(|S|=\ell\), \(\sum_{A\in T:S\subseteq A,\ |A\cap W|<\ell}\mu_A<\ell/k\).
A Continuous-EJR-Verification instance consists of a candidate set \(C\), a committee size \(k\), an explicitly listed finite set \(T\subseteq 2^C\) of approval types with rational masses \((\mu_A)_{A\in T}\) summing to \(1\), and a size-\(k\) committee \(W\subseteq C\). It is a yes-instance if, for every \(1\le \ell\le k\) and every \(S\subseteq C\) with \(|S|=\ell\),
\[
\sum_{A\in T: S\subseteq A,\ |A\cap W|<\ell}\mu_A<\ell/k.
\]
Target. Is Continuous-EJR-Verification solvable in polynomial time, or is it NP-hard?
For finite approval profiles, deciding whether a given committee provides extended justified representation is coNP-complete. No result for the rational-mass type-distribution formulation is assumed here.
The rational-mass formulation is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. Thus it is polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\). It is also \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. Under many-one reductions, calling it \(\mathrm{NP}\)-hard would require \(\mathrm{NP}=\mathrm{coNP}\).
Here is a complete proof, using the finite-profile hardness result supplied in the question.
Membership in \(\mathrm{coNP}\). Assume \(k\geq 1\), as required for the defining fractions. A certificate that the instance is a no-instance consists of an integer \(\ell\) and a candidate subset \(S\) satisfying
\[
1\leq \ell\leq k,\qquad |S|=\ell,\qquad
\sum_{\substack{A\in T:\ S\subseteq A\\ |A\cap W|<\ell}}\mu_A\geq \frac{\ell}{k}.
\]
This certificate has polynomial length because \(k\leq |C|\).
The verifier scans all explicitly listed approval types, tests the two conditions selecting terms, and compares the resulting rational sum with \(\ell/k\). This comparison can be performed exactly in polynomial time. Specifically, write each mass as \(\mu_A=p_A/q_A\), with \(q_A>0\), and let \(D=\prod_{A\in T}q_A\). The binary length of \(D\) is at most the sum of the binary lengths of the denominators. The required comparison is equivalent to the integer comparison
\[
k\sum_{\substack{A\in T:\ S\subseteq A\\ |A\cap W|<\ell}}
p_A(D/q_A)\geq \ell D.
\]
All integers involved have polynomial binary length, and there are polynomially many arithmetic operations. Consequently, the complement belongs to \(\mathrm{NP}\), so Continuous-EJR-Verification belongs to \(\mathrm{coNP}\).
Reduction from finite-profile verification. Consider a finite approval profile with voters \(N=\{1,\ldots,n\}\), where \(n\geq 1\), approval sets \(A_i\subseteq C\), and a size-\(k\) committee \(W\). For each distinct approval set \(A\), define
\[
n_A=|\{i\in N:A_i=A\}|,\qquad
T=\{A_i:i\in N\},\qquad
\mu_A=\frac{n_A}{n}.
\]
These masses are nonnegative and sum to \(1\). There are at most \(n\) distinct types, and each mass has an encoding of length \(O(\log n)\). Thus the constructed instance has polynomial size and is computable in polynomial time.
We verify that the reduction preserves the answer. In a finite profile, a violation of EJR consists of an integer \(\ell\in\{1,\ldots,k\}\) and a group \(X\subseteq N\) such that
\[
|X|\geq \frac{\ell n}{k},\qquad
\left|\bigcap_{i\in X}A_i\right|\geq \ell,\qquad
|A_i\cap W|<\ell\quad\text{for every }i\in X.
\]
Suppose first that such a group exists. Choose an \(\ell\)-element subset \(S\) of its common intersection. Every voter in \(X\) belongs to
\[
B_{\ell,S}=\{i\in N:S\subseteq A_i,\ |A_i\cap W|<\ell\}.
\]
By construction of the masses,
\[
\sum_{\substack{A\in T:\ S\subseteq A\\ |A\cap W|<\ell}}\mu_A
=\frac{|B_{\ell,S}|}{n}
\geq\frac{|X|}{n}
\geq\frac{\ell}{k}.
\]
Hence the constructed continuous instance is a no-instance.
Conversely, suppose the continuous instance is a no-instance, witnessed by \(\ell\) and \(S\). Set \(X=B_{\ell,S}\). The same counting identity gives
\[
|X|
=n\sum_{\substack{A\in T:\ S\subseteq A\\ |A\cap W|<\ell}}\mu_A
\geq\frac{\ell n}{k}.
\]
Every voter in \(X\) approves all of \(S\), so their common intersection has size at least \(\ell\). Every voter in \(X\) also satisfies \(|A_i\cap W|<\ell\). Thus \(X\) witnesses a finite-profile EJR violation.
Therefore the finite committee satisfies EJR if and only if the constructed rational-mass instance is a yes-instance. Notice that the reverse implication simply takes all eligible voters; no assumption about indivisibility of approval types is needed.
By the supplied \(\mathrm{coNP}\)-completeness of finite-profile EJR verification, this polynomial-time many-one reduction proves \(\mathrm{coNP}\)-hardness. Together with membership, it proves the asserted classification.
Meaning of the requested dichotomy. The distinction between \(\mathrm{NP}\)-hardness and \(\mathrm{coNP}\)-hardness matters for a verification problem.
If this problem were polynomial-time solvable, its \(\mathrm{coNP}\)-hardness would imply \(\mathrm{coNP}\subseteq\mathrm{P}\). Closure of \(\mathrm{P}\) under complementation would then imply \(\mathrm{NP}\subseteq\mathrm{P}\). Conversely, \(\mathrm{P}=\mathrm{NP}\) implies \(\mathrm{P}=\mathrm{coNP}\), giving a polynomial-time algorithm by the membership proof.
Under polynomial-time many-one reductions, the problem is \(\mathrm{NP}\)-hard if and only if \(\mathrm{NP}=\mathrm{coNP}\): hardness and membership would imply \(\mathrm{NP}\subseteq\mathrm{coNP}\), hence equality by complementation; equality would make its established \(\mathrm{coNP}\)-hardness also \(\mathrm{NP}\)-hardness.
Under polynomial-time Turing reductions, it is unconditionally \(\mathrm{NP}\)-hard. For any language \(L\in\mathrm{NP}\), its complement belongs to \(\mathrm{coNP}\) and therefore many-one reduces to this problem. One oracle query followed by negating the answer decides membership in \(L\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the complexity question, with the necessary distinction between many-one and Turing reductions. It establishes \(\mathrm{coNP}\)-completeness under polynomial-time many-one reductions and \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions. No major or minor mathematical issues were found.
Step-by-step verification
The proof explicitly assumes \(k\geq 1\), consistent with the task’s use of division by \(k\). Since \(W\subseteq C\) has size \(k\), necessarily \(k\leq |C|\).
Negating the defining universal condition gives exactly the certificate stated: an integer \(\ell\) and a set \(S\subseteq C\) with \(1\leq\ell\leq k\), \(|S|=\ell\), and qualifying mass at least \(\ell/k\). In particular, the proof correctly changes the strict inequality to a non-strict inequality. The certificate has polynomial length.
The verifier can check set containment and committee intersection sizes in polynomial time because approval types are explicitly listed.
The common-denominator argument is valid. The positive integer \(D=\prod_{A\in T}q_A\) has binary length bounded by the total denominator encoding length. Each quotient \(D/q_A\) is an integer, and multiplying the rational inequality by the positive quantity \(kD\) preserves its direction.
Products, partial sums, and both sides of the final comparison have polynomial binary length. The number of arithmetic operations is polynomial in the input length. Thus the no-instances have polynomially verifiable certificates, establishing membership in \(\mathrm{coNP}\). Zero masses and equality at the threshold cause no difficulty.
Grouping voters with identical approval sets produces an explicitly listed set \(T\) with at most \(n\) members. Each mass \(n_A/n\) is positive and rational, and the masses sum to \(1\).
Both numerator and denominator have binary length \(O(\log n)\). Identifying equal approval sets and counting their occurrences can be performed in polynomial time in the explicitly listed finite profile. Keeping \(C\), \(k\), and \(W\) preserves the remaining instance requirements.
The reduction therefore produces a valid instance in polynomial time and with polynomial output size.
The stated characterization correctly expresses a violation: an \(\ell\)-cohesive group of at least \(\ell n/k\) voters, every member of which approves fewer than \(\ell\) committee members.
The numerical threshold need not be an integer; comparing the integer \(|X|\) against the rational threshold is correct. Since \(n\geq 1\), \(k\geq 1\), and \(\ell\geq 1\), any such group is nonempty, so no empty-intersection convention is needed.
The common intersection contains an \(\ell\)-element subset \(S\). Every member of \(X\) then belongs to \(B_{\ell,S}\), so \(X\subseteq B_{\ell,S}\).
The counting identity is exact: every voter of a given approval type satisfies the same two eligibility conditions. Consequently, the summed type mass is precisely \(|B_{\ell,S}|/n\).
The displayed inequality chain follows from this identity, the inclusion, and the finite violation’s size threshold. It establishes a continuous no-instance, including the equality case.
Taking \(X=B_{\ell,S}\) is valid. The same counting identity proves \(|X|\geq \ell n/k\), which also guarantees \(X\neq\varnothing\).
By definition, every member approves all of \(S\) and has fewer than \(\ell\) approved committee members. Hence the common intersection has size at least \(\ell\), and all three conditions for a finite EJR violation hold.
This direction requires no division of types or selection of fractional voters.
The two implications establish equivalence of no-instances and therefore equivalence of yes-instances. Thus this is an answer-preserving many-one reduction from finite EJR verification itself.
The task supplies the \(\mathrm{coNP}\)-completeness of finite-profile EJR verification. Its use here is justified: the construction accepts precisely the finite-profile data described and preserves the EJR answer. Together with membership, it establishes the claimed \(\mathrm{coNP}\)-completeness.
All three subsequent complexity claims are correct:
The proof therefore correctly qualifies the target’s wording rather than conflating \(\mathrm{NP}\)-hardness with \(\mathrm{coNP}\)-hardness.
Feedback to the prover
No repair or additional clarification is required. Retain the explicit reduction conventions when reporting the result.
⟨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.