Answer: Polynomial-time solvable in \(m,\tau,L\).
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate6-APPROVAL-2-PARTITION is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), approval types \(\mathcal T\subseteq\binom{C}{6}\), and positive rational masses \(\mu_S\) summing to \(1\), is there a split \(x_S\in[0,\mu_S]\) and distinct candidates \(p,q\in C\) such that \(p\) uniquely wins the first group and \(q\) uniquely wins the second? Equivalently, can one maximize \(\delta\) subject to \(\sum_{S\ni p}x_S\ge\sum_{S\ni c}x_S+\delta\) for every \(c\ne p\), and \(\sum_{S\ni q}(\mu_S-x_S)\ge\sum_{S\ni c}(\mu_S-x_S)+\delta\) for every \(c\ne q\), with optimum \(\delta>0\)?
Let \(C\) be a candidate set with \(m\ge 6\). A society is given by its support: a nonempty list \(\mathcal T\subseteq\binom{C}{6}\) of \(\tau\) distinct approval types, each with positive binary rational mass \(\mu_S\), with \(\sum_{S\in\mathcal T}\mu_S=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
A split chooses real masses \(x_S\in[0,\mu_S]\), assigning \(x_S\) to the first group and \(\mu_S-x_S\) to the second. Each group must have positive total mass; no prescribed group sizes apply.
For group masses \(y_S\), candidate \(c\) has approval score \(\sum_{S\in\mathcal T:c\in S}y_S\). A unique winner must strictly outscore every other candidate; ties do not qualify.
The decision problem asks whether a split exists with distinct candidates \(p,q\in C\) uniquely winning the first and second groups, respectively; both leaders are chosen as part of the solution.
Is this continuous two-group approval partition problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For indivisible voters, partitioning into two groups with distinct unique approval winners is NP-hard even when every voter approves exactly six candidates ([source](https://www.ijcai.org/Proceedings/16/Papers/042.pdf)). No result settling this exact continuous problem was located in the literature search.
The problem is solvable in polynomial time in \(m,\tau,L\). Enumerate the possible distinct leaders and, for each pair, solve a rational linear program that maximizes a common margin. A strictly positive optimum is equivalent to a valid split.
Fix an ordered pair \(p,q\in C\) with \(p\ne q\). For each candidate \(c\), define its total approval mass and its first-group score by
\(v_c=\sum_{S\in\mathcal T:c\in S}\mu_S,\qquad A_c(x)=\sum_{S\in\mathcal T:c\in S}x_S.\)
Its second-group score is consequently \(v_c-A_c(x)\).
Introduce a real variable \(\varepsilon\), and maximize \(\varepsilon\) subject to the following constraints:
All constraints are linear. In particular, the last family can be written as
\(v_q-v_c-\sum_{S\in\mathcal T}\bigl(\mathbf 1_{\{q\in S\}}-\mathbf 1_{\{c\in S\}}\bigr)x_S\ge\varepsilon.\)
If the program is feasible, its feasible region is closed and bounded: every \(x_S\) lies in a bounded interval, as does \(\varepsilon\). Thus its maximum is attained.
Claim. A split with first-group unique winner \(p\) and second-group unique winner \(q\) exists if and only if this linear program is feasible and has strictly positive optimum.
Proof. Suppose first that such a split \(x\) exists. Both group masses are positive. Moreover, each of the following score differences is positive:
\(A_p(x)-A_c(x)\quad(c\ne p),\)
\((v_q-A_q(x))-(v_c-A_c(x))\quad(c\ne q).\)
Take \(\varepsilon\) to be the minimum of \(1\), the two group masses, and all these score differences. This is the minimum of a finite, nonempty collection of positive real numbers, so \(\varepsilon>0\). Every linear-program constraint holds. Hence the optimum is positive.
Conversely, suppose a feasible solution has \(\varepsilon>0\). The group-mass constraints make both groups positive. Every first-group comparison gives \(A_p(x)>A_c(x)\) for \(c\ne p\), so \(p\) is its unique winner. Every second-group comparison similarly makes \(q\) its unique winner. The box constraints ensure that these groups form an admissible split. Since \(p\ne q\), the split meets every requirement. This proves the claim.
We use the standard polynomial-time theorem for rational linear programming: a linear program with binary-encoded rational data can be tested for feasibility and, when feasible with a finite optimum, optimized exactly in time polynomial in its encoding length.
Here each program has \(\tau+1\) variables and \(2\tau+2(m-1)+4\) inequalities. Its coefficients and right-hand sides have polynomial bit length. To verify the latter explicitly, write each input mass as \(\mu_S=a_S/b_S\), and let \(D=\prod_{S\in\mathcal T}b_S\). The binary length of \(D\) is at most the sum of the input denominator lengths, hence is \(O(L)\). Every \(v_c\) and every difference \(v_q-v_c\) has denominator dividing \(D\). Because \(0\le v_c\le1\), their numerators over denominator \(D\) also have \(O(L)\) bits. All remaining data are input masses or small integers.
Thus each program has encoding length polynomial in \(m,\tau,L\). Exact optimization decides whether its optimum is positive; no numerical tolerance or assumed lower bound on a winning margin is needed.
The algorithm is therefore:
The equivalence proved above establishes correctness, and the number and size of the programs establish polynomial running time. An accepting program also supplies a rational split of polynomial encoding length.
The proof does not use the restriction that each approval type has size six, so it also applies to arbitrary explicitly listed approval types. The [cited hardness result](https://www.ijcai.org/Proceedings/16/Papers/042.pdf) concerns indivisible voters; allowing each type’s mass to split continuously permits the linear-programming algorithm above.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the exact continuous problem in polynomial time in \(m,\tau,L\). The LP formulation, strict-margin equivalence, and bit-complexity argument are correct. No major or minor mathematical issues were found.
The definitions of \(v_c\) and \(A_c(x)\) match the task. The second-group score is exactly \(v_c-A_c(x)\), because each type contributes its remaining mass \(\mu_S-x_S\). The box constraints enforce precisely the permitted continuous allocation.
The first comparison family requires \(p\) to exceed every other candidate by at least \(\varepsilon\). The second family does the same for \(q\) in the second group. Its expanded expression has the correct signs:
\[
(v_q-A_q(x))-(v_c-A_c(x))
=
v_q-v_c-\sum_{S\in\mathcal T}
\bigl(\mathbf 1_{\{q\in S\}}-\mathbf 1_{\{c\in S\}}\bigr)x_S.
\]
Each family includes comparison against the other proposed leader. Thus the formulation does not overlook competition between \(p\) and \(q\).
The two group-mass inequalities correctly enforce positive masses whenever \(\varepsilon>0\). They impose no prescribed group sizes.
The feasible region is an intersection of finitely many closed linear halfspaces with the bounded box specified for \(x\) and \(\varepsilon\). If nonempty, it is compact. The continuous linear objective therefore attains its maximum. The prover correctly conditions this statement on feasibility; feasibility at \(\varepsilon=0\) is not assumed.
For a valid split with the specified leaders, both group masses and all required score differences are positive. There are finitely many such quantities. Consequently, the stated minimum, also including \(1\), is strictly positive.
Choosing this minimum as \(\varepsilon\) satisfies every constraint, including \(\varepsilon\le1\). The argument works for real allocations and does not assume rationality or a uniform positive lower bound on winning margins.
Attainment supplies a feasible solution with positive \(\varepsilon\). The group-mass constraints make both groups nonempty, and the comparison constraints make both winners unique. The box constraints make the allocation admissible, while the enumerated condition \(p\ne q\) makes the winners distinct.
Both directions of the claimed equivalence are therefore established.
The variable count \(\tau+1\) is correct. The inequality count is also correct: there are \(2\tau\) box inequalities, two bounds on \(\varepsilon\), two group-mass inequalities, and \(2(m-1)\) score comparisons.
The denominator argument is valid. For
\[
D=\prod_{S\in\mathcal T}b_S,
\]
its binary length is bounded by the sum of the input denominator lengths, hence is \(O(L)\). Expressing totals over denominator \(D\) gives integer numerators between \(0\) and \(D\). Differences have signed numerators with absolute value at most \(D\). Thus all derived rational constants have \(O(L)\) bits.
The remaining coefficients are small integers or input masses. The whole LP therefore has encoding length polynomial in \(m,\tau,L\); it uses the listed support rather than enumerating all possible approval types.
The invoked theorem is stated sufficiently precisely: binary-encoded rational linear programs admit polynomial-time feasibility testing and exact optimization when feasible with finite optimum. All its hypotheses are verified here: the data are rational with polynomial encoding length, and the objective is bounded by the constraint on \(\varepsilon\).
Exact optimization permits an exact comparison with zero. No numerical tolerance is needed. The additional claim that a rational split of polynomial encoding length can be supplied is consistent with the standard rational LP solution-size guarantee. These standard facts are documented in [MIT’s feasibility and optimization notes](https://www.mit.edu/~gfarina/2024/67220s24_L04B_separation/L04B.pdf) and [LP encoding and solution-size notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html).
Enumerating \(m(m-1)\) ordered pairs covers every permitted choice of distinct leaders. Combining this polynomial number of programs with their polynomial encoding lengths yields the claimed running time.
Ties cannot cause acceptance because acceptance requires a strictly positive optimum. Empty groups are likewise excluded. Candidates with identical approval incidence remain tied in every allocation, so the corresponding strict comparison cannot be satisfied. No nondegeneracy assumption is used.
The argument does not use approval-type size six, so its stated extension to arbitrary explicitly listed approval types is justified. The cited indivisible-voter result concerns a different allocation domain; its definitions and Theorem 8 support the scope distinction made in the output. [Voting-Based Group Formation](https://www.ijcai.org/Proceedings/16/Papers/042.pdf)
Required feedback: None. No missing lemma, unverified hypothesis, or substantive clarification is needed.
⟨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.