Answer: \(\mathrm{NP}\)-complete for both fixed choices \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\), already for every fixed \(k'\ge2\); also FPT parameterized by the support size \(\tau\).
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each k′ ≥2, JR-DIFF-COMMITTEES and EJR+-DIFF-COMMITTEES are NP-complete and W[1]-hard when parameterized by the committee size k. We again complement the negative result by giving a polynomial-size ILP formulation in our full version (Boehmer, Glessen, and Peters 2025).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), an approval-ballot support \(\mathcal T\subseteq 2^C\), positive rational masses \(\mu_A\) summing to \(1\), a threshold \(k'\ge 2\), and \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\), are there two size-\(k\) committees \(W_1,W_2\) with \(|W_1\setminus W_2|\ge k'\), both satisfying mass-\(X\)? For each \(W\), mass-\(\mathrm{JR}\) requires \(\sum_{A:\,c\in A,\ |A\cap W|<1}\mu_A<1/k\) for every \(c\notin W\); mass-\(\mathrm{EJR}^+\) requires \(\sum_{A:\,c\in A,\ |A\cap W|<\ell}\mu_A<\ell/k\) for every \(c\notin W\) and \(\ell\in[k]\).
Let \(C\) be a candidate set with \(m=|C|\), and let \(2\le k'\le k\le m\) be integers. Fix \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\).
A society is given by its support: a list \(\mathcal T\subseteq 2^C\) of distinct approval types with positive binary rational masses \(\mu_A\) summing to \(1\). Empty approval types are allowed. The support size is \(\tau=|\mathcal T|\), not the number of possible approval types; let \(L\) be the total input bit length.
A committee is a subset \(W\subseteq C\) with \(|W|=k\). It satisfies mass-\(\mathrm{JR}\) if \(\sum_{A\in\mathcal T:\,c\in A,\,|A\cap W|<1}\mu_A<1/k\) for every \(c\in C\setminus W\).
It satisfies mass-\(\mathrm{EJR}^+\) if \(\sum_{A\in\mathcal T:\,c\in A,\,|A\cap W|<\ell}\mu_A<\ell/k\) for every \(c\in C\setminus W\) and integer \(1\le\ell\le k\).
The decision problem asks whether there exist two committees \(W_1,W_2\), both satisfying mass-\(X\), with \(|W_1\setminus W_2|\ge k'\). State running times in \(m,\tau,L,k,k'\).
For each fixed \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\), is this decision problem solvable in polynomial time or is it NP-hard?
For finite voter lists, the corresponding problem is NP-complete for every fixed \(k'\ge2\), W[1]-hard parameterized by \(k\), and FPT parameterized by the number of voters. [Source](https://arxiv.org/html/2511.09479)
No result explicitly treating this exact rational-mass decision problem was located in the literature search.
For each fixed \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\), the rational-mass problem is NP-complete, already for every fixed \(k'\ge 2\). It is therefore not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
The finite-voter hardness transfers by merging identical ballots. Below I prove this transfer, give explicit verification and exhaustive-search bounds, and establish an FPT algorithm parameterized by the actual support size \(\tau\).
Write each mass as \(\mu_A=p_A/q_A\), where the positive integers \(p_A,q_A\) are encoded in binary. Define
\(\displaystyle Q=\prod_{A\in\mathcal T}q_A,\qquad b_A=p_A(Q/q_A).\)
Then \(\mu_A=b_A/Q\), and the promised normalization gives \(\sum_A b_A=Q\). The binary length of \(Q\) is at most the sum of the binary lengths of the denominators, hence is \(O(L)\). Thus this construction uses integers of polynomial bit length; it does not expand the society into voters.
For a committee \(W\), put \(s_A=|A\cap W|\). Its condition for a candidate \(c\notin W\) and level \(\ell\) is exactly
\(\displaystyle k\sum_{\substack{A\in\mathcal T\\c\in A,\ s_A<\ell}}b_A<\ell Q.\)
Consequently, equality at the threshold is detected exactly.
Let \(B=L+\lceil\log_2(m+1)\rceil+1\). Using elementary integer arithmetic, the denominator preprocessing takes \(O(\tau B^2)\) bit operations. Computing all \(s_A\) takes \(O(m\tau B)\) bit operations using an incidence table.
For JR, only \(\ell=1\) is checked. A verifier therefore runs in
\(\displaystyle V_{\mathrm{JR}}=O\bigl((\tau+m\tau)B^2\bigr).\)
For EJR\(^{+}\), for each candidate \(c\), accumulate the weights of its approving types in buckets indexed by \(s_A\in\{0,\ldots,k\}\). Prefix sums give the relevant weight for every \(\ell\). Including exact comparisons, the running time is
\(\displaystyle V_{\mathrm{EJR}^+}=O\bigl((\tau+m\tau+mk)B^2\bigr).\)
A certificate consists of \(W_1,W_2\). Their sizes, their distance, and both proportionality conditions are verifiable within these polynomial bounds. Hence both problems belong to \(\mathrm{NP}\).
The finite-voter theorem supplied in the question states that, for each fixed \(k'\ge2\), both corresponding problems are NP-complete and W[1]-hard parameterized by \(k\). Its distance is precisely \(|W_1\setminus W_2|\), and its EJR\(^{+}\) definition uses groups of size at least \(\ell n/k\). [Boehmer, Glessen, and Peters, Definition 2.1 and Theorem 3.3](https://arxiv.org/html/2511.09479)
Consider such a finite instance with \(n>0\) voters and ballots \(A_1,\ldots,A_n\). For every distinct occurring ballot \(A\), let
\(\displaystyle n_A=|\{i:A_i=A\}|,\qquad \mu_A=n_A/n.\)
Keep \(C,k,k'\) unchanged and output the support of distinct ballots with these masses.
Every output mass is positive, their sum is \(1\), and their numerators and denominators have \(O(\log(n+1))\) bits. There are at most \(n\) support types. Sorting the ballots, counting multiplicities, and writing these fractions take polynomial time in the explicit finite-instance length. Empty ballots, if present, are treated in exactly the same way.
For every committee \(W\), candidate \(c\), and integer \(\ell\),
\(\displaystyle \sum_{\substack{A\in\mathcal T\\c\in A,\ |A\cap W|<\ell}}\mu_A = \frac{|\{i:c\in A_i,\ |A_i\cap W|<\ell\}|}{n}. \)
To check equivalence with the finite definition, let \(U\) be the voter set in the numerator. A violating group exists precisely when \(|U|\ge\ell n/k\):
Therefore \(W\) satisfies finite JR, respectively finite EJR\(^{+}\), if and only if it satisfies the corresponding mass axiom. The reduction preserves every feasible committee, and hence every feasible pair and its distance.
This proves NP-hardness for both fixed choices of \(X\), already for each fixed \(k'\ge2\). Together with Section 1, it proves NP-completeness. Because \(k\) is unchanged, the same reduction also transfers W[1]-hardness parameterized by \(k\).
For any two committees,
\(\displaystyle |W_1\cup W_2|=k+|W_1\setminus W_2|.\)
Thus an instance with \(m<k+k'\) can immediately be rejected.
Otherwise, enumerating all ordered pairs of size-\(k\) committees and verifying them gives the bound
\(\displaystyle O\left(\binom{m}{k}^{\,2}V_X\right)\subseteq O\left(m^{2k}V_X\right).\)
Here \(V_X\) is the explicit bit-operation bound from Section 1. The distance test takes \(O(m)\) additional operations per pair. This is an XP algorithm parameterized by \(k\).
The finite-voter FPT result cannot simply be applied after expanding rational masses: that expansion might be exponentially large. The following argument works directly with the \(\tau\) support types.
Index the support types as \(A_1,\ldots,A_\tau\). For a nonempty set \(S\subseteq\{1,\ldots,\tau\}\), define
\(\displaystyle \mu(S)=\sum_{i\in S}\mu_{A_i},\)
and define integer thresholds
\(\displaystyle t_{\mathrm{JR}}(S)= \begin{cases} 1,&k\mu(S)\ge1,\\ 0,&k\mu(S)<1, \end{cases} \qquad t_{\mathrm{EJR}^+}(S)=\lfloor k\mu(S)\rfloor. \)
For a candidate \(c\), let \(P(c)=\{i:c\in A_i\}\). For a committee \(W\), let \(s_i=|A_i\cap W|\).
Lemma. The committee \(W\) satisfies mass-\(X\) if and only if, for every \(c\notin W\) and every nonempty \(S\subseteq P(c)\),
\(\displaystyle \max_{i\in S}s_i\ge t_X(S).\)
Proof for EJR\(^{+}\). Suppose \(W\) satisfies the axiom. If \(t=t_{\mathrm{EJR}^+}(S)>0\) and all \(s_i<t\) for \(i\in S\), then the mass of types approving \(c\) with representation below \(t\) is at least \(\mu(S)\ge t/k\). This violates the axiom at level \(t\). The level is permitted because \(1\le t\le k\). When \(t=0\), the inequality is automatic.
Conversely, suppose the axiom fails at \(c\notin W\) and level \(\ell\). Set \(S=\{i\in P(c):s_i<\ell\}\). Its mass is at least \(\ell/k\), so \(S\) is nonempty and \(t_{\mathrm{EJR}^+}(S)\ge\ell\). Every \(s_i\) in \(S\) is smaller than \(\ell\), contradicting the asserted inequality.
Proof for JR. A violation consists precisely of approving types with \(s_i=0\) whose combined mass is at least \(1/k\). Such a set violates the displayed condition with threshold \(1\), and any failed condition with threshold \(1\) supplies such a violation. Conditions with threshold \(0\) are automatic. \(\square\)
Partition candidates according to their signatures \(P(c)\). Let the occurring classes be \(D_1,\ldots,D_r\), with signatures \(P_j\) and sizes \(n_j\). Then
\(\displaystyle r\le\min(m,2^\tau).\)
For each committee index \(b\in\{1,2\}\), guess a set \(F_b\) of classes that the committee includes in full. Also, for every nonempty support subset \(S\), guess a witness \(w_b(S)\in S\).
For each collection of guesses, construct an integer program with \(3r\) variables:
Impose
\(\displaystyle 0\le x_{j,b}\le n_j,\qquad \sum_jx_{j,b}=k, \)
together with
\(\displaystyle x_{j,b}=n_j\quad(j\in F_b),\qquad x_{j,b}\le n_j-1\quad(j\notin F_b). \)
The overlap constraints are
\(\displaystyle 0\le z_j,\qquad z_j\le x_{j,1},\qquad z_j\le x_{j,2},\qquad z_j\ge x_{j,1}+x_{j,2}-n_j, \)
and
\(\displaystyle \sum_jz_j\le k-k'.\)
Finally, whenever a nonempty \(S\) is contained in \(P_j\) for some \(j\notin F_b\), impose
\(\displaystyle \sum_{\substack{h\\w_b(S)\in P_h}}x_{h,b}\ge t_X(S). \)
All variables are required to be integers.
Correctness. Given a feasible committee pair, choose its actual full classes and intersection sizes. The lemma supplies a witness for every relevant subset \(S\); choose arbitrary witnesses for irrelevant subsets. These choices satisfy the program.
Conversely, an integer solution can be realized within each class by selecting \(z_j\) common candidates, \(x_{j,1}-z_j\) candidates only for the first committee, and \(x_{j,2}-z_j\) only for the second. The overlap constraints make all these numbers nonnegative and ensure that their total is at most \(n_j\). The resulting committees have size \(k\) and distance at least \(k'\).
A class has an outside candidate exactly when it is not in \(F_b\). For every such class, the final constraints enforce the lemma for all nonempty subsets of its signature. Hence both realized committees satisfy mass-\(X\).
The number of collections of guesses is at most
\(\displaystyle 2^{2r}\left(\prod_{\varnothing\ne S\subseteq\{1,\ldots,\tau\}}|S|\right)^2 \le 2^{2r}\tau^{\,2(2^\tau-1)}. \)
All thresholds are computed exactly using the common denominator from Section 1. Each program has \(3r\) integer variables, \(O(r+2^\tau)\) constraints, and integer coefficients of polynomial bit length.
The fixed-dimension integer-programming algorithm has running time \(2^{O(d^3)}H^{O(1)}\) for \(d\) integer variables and binary input length \(H\). [Lenstra’s theorem and its running-time bound](https://doi.org/10.1145/800061.808749) Its hypotheses apply here: each branch is a finite system of linear inequalities with integer coefficients and integer variables.
Substituting \(d=3r\) and \(r\le2^\tau\), and including preprocessing and all guesses, gives the conservative bound
\(\displaystyle 2^{O(8^\tau)} \bigl(m+\tau+L+\log(k+1)+\log(k'+1)\bigr)^{O(1)}. \)
Thus both rational-mass problems are FPT parameterized by the support size \(\tau\), even though they are NP-complete in general.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly establishes NP-completeness for each fixed choice of \(X\), already for every fixed \(k'\ge2\). Its additional verification bounds, XP algorithm, W[1]-hardness transfer, and FPT algorithm parameterized by support size are also justified. I found no major or minor mathematical gaps requiring repair.
The common-denominator construction is valid. Each denominator divides \(Q\), so every \(b_A\) is an integer, and normalization gives \(\sum_A b_A=Q\).
The bit-length estimate is correct: the binary length of a product is at most the sum of the binary lengths of its factors. Moreover, positivity and normalization imply \(b_A\le Q\). Thus both individual weights and their subset sums have polynomial bit length.
Multiplying the defining inequality by the positive integer \(kQ\) gives exactly the comparison written by the prover. In particular, equality fails the strict proportionality condition, as required.
The arithmetic bounds are conservative but valid:
The factors \(k\) and \(\ell\) do not invalidate the bit-length bounds because \(1\le\ell\le k\le m\).
Two explicit committees form a polynomial-size certificate. Committee sizes, distance, and both mass conditions are checkable in polynomial time. Membership in NP is established.
The cited finite-voter result matches the target. Definition 2.1 uses an outside candidate and a group of approving voters whose size is at least \(\ell n/k\), requiring some group member to have representation at least \(\ell\). The distance definition is exactly \(|W_1\setminus W_2|\), and Theorem 3.3 states the claimed hardness for each \(k'\ge2\). [Boehmer, Glessen, and Peters](https://arxiv.org/html/2511.09479)
The reduction is polynomial for explicit voter lists. Merging identical ballots produces at most \(n\) distinct types; the fractions \(n_A/n\) have binary encoding length \(O(\log(n+1))\), are positive, and sum to one. Fractions need not be reduced to represent the required rational numbers.
The displayed equality between mass and normalized voter count is exact.
The violating-group equivalence is also correct. For a fixed outside candidate and level, every violating group is contained in the set \(U\) of approvers below that level. Conversely, if \(U\) meets the threshold, it is itself a violating group. The real threshold causes no rounding discrepancy: comparison of an integer count with \(\ell n/k\) is equivalent to comparison of its normalized mass with \(\ell/k\).
Taking \(\ell=1\) yields JR; taking every permitted level yields EJR\(^{+}\). Empty ballots introduce no exception.
Consequently, the reduction preserves every feasible committee and every pair’s distance. Keeping \(k'\) unchanged preserves each fixed-\(k'\) restriction, and keeping \(k\) unchanged preserves the parameter for the W[1]-hardness transfer.
Both NP-hardness claims follow, and together with membership they establish NP-completeness.
For equal-size committees, the union identity is correct. Thus \(m<k+k'\) excludes every pair meeting the distance requirement.
There are exactly \(\binom{m}{k}^{2}\) ordered committee pairs. Verifying both committees changes the bound only by a constant factor. The additional distance computation is absorbed by the displayed verification bounds because normalization ensures \(\tau\ge1\).
The inequality \(\binom{m}{k}^{2}\le m^{2k}\) is valid. The stated exhaustive-search bound and XP classification follow.
The forward implication is valid. If the subset threshold \(t\) is positive, it lies between \(1\) and \(k\), since the subset mass is at most one. If every type in the subset has representation below \(t\), that subset already contributes enough mass to violate the condition at level \(t\).
For \(t=0\), the inequality follows from nonnegative representation counts.
The converse is valid. A violation at level \(\ell\) yields a nonempty subset of approving types with mass at least \(\ell/k\). Its threshold is therefore at least \(\ell\), while every representation count in that subset is below \(\ell\). This contradicts the asserted maximum condition.
This argument handles exact threshold equality correctly.
A failed threshold-one condition means all representation counts in the subset are zero and its mass is at least \(1/k\). Conversely, the complete collection of unrepresented approvers witnessing a JR violation supplies such a subset. Threshold-zero conditions are automatic.
The lemma is proved for both axioms.
Candidate signatures determine all approval incidences, so the partition and bound \(r\le\min(m,2^\tau)\) are correct. The program has exactly \(3r\) variables.
The full-class constraints correctly distinguish classes included entirely from those containing an outside candidate.
The overlap constraints are sufficient for realization within each class. They ensure that the common part and both exclusive parts have nonnegative integer sizes, and that their combined size fits within the class. The total-overlap constraint gives the required committee distance.
The witness constraints correctly express the lemma after branching. A single witness for a support subset can serve all relevant candidate classes: representation counts depend on the committee and support type, rather than on which outside candidate invokes that subset.
Both correctness directions are justified:
Threshold-zero subsets and candidates approved by no support type are handled without additional constraints.
The branching formulation is exact.
The count of full-class guesses and witness choices is correct, including \(\tau=1\). Normalization excludes \(\tau=0\).
Each branch has \(O(r+2^\tau)\) constraints: the final condition requires one constraint for each relevant subset and committee, even if several candidate classes make that subset relevant.
All coefficients and right-hand sides have polynomial bit length. The program is an integer linear feasibility problem, so the stated fixed-dimension theorem applies. The linked paper is by Kannan and explicitly records Lenstra’s bound \(2^{O(d^3)}H^{O(1)}\); the citation supports the claimed running time. [Kannan, *Improved algorithms for integer programming and related lattice problems*](https://doi.org/10.1145/800061.808749)
Substituting \(d=3r\) and \(r\le2^\tau\) gives the stated dimension dependence. The guess count, subset preprocessing, and program encoding sizes are absorbed by the conservative \(2^{O(8^\tau)}\) factor, leaving a polynomial factor in the listed input quantities.
The support-size FPT claim is established directly for rational masses.
No repair is needed. The output resolves the requested general complexity classification, and its supplementary algorithmic claims withstand verification.
⟨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.