Answer: \(\mathrm{NP}\)-hard, already for \(\tau=2\), equal masses \(1/2\), and \(u=0\).
Proposition 15 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateOUTCOME(KEMENY)cb parameterized by p is para-Θp 2-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given issues \(I\), an integrity constraint \(\Gamma\), a finite support \(S\subseteq R(I,\Gamma)\) with positive binary-rational masses \(\mu_r\) summing to \(1\), and partial ballots \(\ell,\ell_1,\ldots,\ell_u\), is there a rational ballot \(r^\star\in R(I,\Gamma)\) minimizing \(D_\mu(r^\star)=\sum_{r\in S}\mu_r d(r^\star,r)\) that agrees with \(\ell\) and does not agree with any \(\ell_j\)?
Let \(I=\{x_1,\ldots,x_m\}\) be Boolean issues and \(\Gamma\) an explicitly represented propositional formula over \(I\), of size \(c\). A rational ballot is a Boolean assignment satisfying \(\Gamma\); write \(R(I,\Gamma)\) for their set.
A society is given by its support: a nonempty list \(S\subseteq R(I,\Gamma)\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_r\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible ballots.
The input also contains partial ballots \(\ell,\ell_1,\ldots,\ell_u\in\{0,1,\star\}^m\), where \(u\geq0\). Agreement means equality at every coordinate other than \(\star\); nonagreement means disagreement at some specified coordinate.
Using Hamming distance \(d\), define \(D_\mu(b)=\sum_{r\in S}\mu_r d(b,r)\). Decide whether some global minimizer \(b\in R(I,\Gamma)\) agrees with \(\ell\) and does not agree with any \(\ell_j\). All tied global minimizers are eligible; the partial ballots do not restrict the domain of minimization.
Let \(L\) be the total binary input length. State running times in \(m,\tau,c,u,L\).
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite, equally weighted profiles, this decision problem is \(\Theta_2^p\)-hard even with three individuals, hence para-\(\Theta_2^p\)-hard parameterized by the number of individuals. No separate classification for the binary-rational mass encoding is assumed here.
The problem is \(\mathrm{NP}\)-hard, already when \(\tau=2\), both masses are \(1/2\), and \(u=0\). Thus a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The reduction below respects the requirement that every supplied support ballot satisfies \(\Gamma\), even when the source formula is unsatisfiable.
Let \(\varphi(x_1,\ldots,x_n)\) be a SAT instance. Introduce two additional issues \(y,z\), so that \(m=n+2\), and define
\( \displaystyle \Gamma= \left(\neg y\land\neg z\land\bigwedge_{i=1}^{n}\neg x_i\right) \lor \left(y\land z\land\bigwedge_{i=1}^{n}x_i\right) \lor \left(\neg y\land z\land\varphi\right). \)
Supply the two distinct ballots
\( r^{(0)}=(0^n,0,0),\qquad r^{(1)}=(1^n,1,1), \)
each with mass \(1/2\). They satisfy the first and second disjuncts of \(\Gamma\), respectively. Consequently, the support is valid and nonempty independently of whether \(\varphi\) is satisfiable.
Set
\( \ell=(\star^n,0,1),\qquad u=0. \)
Every rational ballot is a global minimizer. Indeed, the two support ballots are complementary at every coordinate. For every Boolean assignment \(b\), each coordinate contributes exactly one to the sum of its distances from them. Hence
\( \displaystyle d(b,r^{(0)})+d(b,r^{(1)})=m, \qquad D_\mu(b)=\frac m2. \)
In particular, this objective is constant on the entire rational domain.
The query is equivalent to satisfiability of \(\varphi\). An assignment agreeing with \(\ell\) has \(y=0,z=1\). These values make the first two disjuncts of \(\Gamma\) false, and the third disjunct holds exactly when its original coordinates satisfy \(\varphi\). Therefore
\( \displaystyle \varphi\text{ is satisfiable} \iff \text{some rational global minimizer agrees with }\ell. \)
This proves both directions of the reduction. Crucially, \(\ell\) is used only to select eligible minimizers; it never changes the minimization domain.
If \(\varphi\) has formula size \(s\), then the constructed instance has \(\tau=2\), \(u=0\), \(m=n+2\), and \(c=O(s+n)\). Its binary encoding and construction time are polynomial in the SAT input length. The masses have constant encoding length.
For completeness, membership in \(\mathrm{NP}\) also holds for the entire restriction \(\tau=2\), including unequal masses.
Write the support as \(\{r,s\}\), with masses \(\alpha,\beta>0\) and \(\alpha+\beta=1\).
If \(\alpha>\beta\), the triangle inequality gives, for every \(b\),
\( \displaystyle D_\mu(b)-D_\mu(r) = \alpha d(b,r)+\beta\bigl(d(b,s)-d(r,s)\bigr) \geq (\alpha-\beta)d(b,r). \)
Thus \(r\) is the unique global minimizer: it is rational by hypothesis, and the displayed lower bound is strictly positive for \(b\neq r\). The case \(\beta>\alpha\) is symmetric. Eligibility of this unique minimizer can be checked directly.
If \(\alpha=\beta=1/2\), then
\( \displaystyle D_\mu(b)\geq\frac{d(r,s)}2, \)
and this value is attained by the rational ballot \(r\). Equality holds exactly when \(b_i=r_i=s_i\) at every coordinate where \(r_i=s_i\): at such a coordinate, disagreement contributes two instead of zero to the distance sum; at coordinates where \(r_i\neq s_i\), either value contributes one.
Consequently, a certificate in the equal-mass case is a ballot satisfying \(\Gamma\), these shared-coordinate requirements, and all query conditions. Verification takes \(O(c+m(u+1))\) Boolean operations. Comparing the masses takes polynomial time in \(L\).
Together with Section 1, this establishes \(\mathrm{NP}\)-completeness for \(\tau=2\). For \(\tau=1\), the sole support ballot is the unique minimizer, so the problem is polynomial-time solvable.
Suppose the masses are encoded as binary fractions \(\mu_r=p_r/q_r\), with positive integer denominators. Define
\( \displaystyle Q=\prod_{r\in S}q_r,\qquad w_r=p_r(Q/q_r). \)
These are integers satisfying \(\sum_r w_r=Q\). Multiplying the objective by \(Q>0\) preserves all minimizers:
\( \displaystyle F(b)=QD_\mu(b)=\sum_{r\in S}w_r d(b,r). \)
The total denominator encoding length is at most \(L\), so \(Q\) has \(O(L)\) bits. Moreover, \(0\leq F(b)\leq mQ\), so objective values have \(O(L+\log(m+1))\) bits. All comparisons can therefore be exact, with polynomial bit complexity.
An \(\mathrm{NP}\) oracle can answer whether a rational ballot satisfies \(F(b)\leq t\): guess \(b\), evaluate \(\Gamma\), and compute \(F(b)\). Binary search over the integer interval from \(0\) to \(mQ\) finds the unrestricted optimum \(F^*\) using \(O(L+\log(m+1))\) oracle queries. One final query asks for a rational ballot satisfying \(F(b)=F^*\) and all eligibility conditions.
This proves the general upper bound
\( \displaystyle \text{the problem belongs to }\mathrm{P}^{\mathrm{NP}}=\Delta_2^p. \)
The oracle algorithm has polynomial overhead in \(L\); each certificate verification uses polynomial time in \(c+m\tau+m(u+1)\) and \(L\).
A fully deterministic algorithm enumerates all \(2^m\) assignments, retaining the smallest unrestricted objective and whether an eligible ballot attains it. Using elementary exact integer arithmetic, a conservative bit-operation bound is
\( \displaystyle O\!\left( L^3+ 2^m\bigl(c+m(\tau+u+1)\bigr)L^2 \right). \)
Under binary numerator–denominator encoding, the stated \(\Theta_2^p\)-hardness for three equally weighted individuals transfers directly. Replace repeated ballots by one support type with mass equal to its multiplicity divided by three. These masses are positive, have constant encoding length, and preserve the objective exactly:
\( \displaystyle D_\mu(b)=\frac13\sum_{i=1}^{3}d(b,r_i). \)
The resulting support has \(\tau\leq3\). Hence the general problem is also \(\Theta_2^p\)-hard, parameterized hardness persists for support size, and no separate mass-encoding classification is needed for this lower bound. The direct SAT reduction remains sufficient for the requested conclusion and uses only the dyadic mass \(1/2\).
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The reduction proves $\mathrm{NP}$-hardness with two distinct rational support ballots, equal masses, and no exclusion ballots. The additional minimizer characterization and upper bounds are also sound. I found no major or minor issues.
The construction uses $m=n+2$ issues and an explicitly represented formula of size $c=O(s+n)$, where $s$ is the source formula size. The two support ballots are distinct because their $y,z$ coordinates differ, including when $n=0$.
Both support ballots satisfy $\Gamma$ independently of the satisfiability of $\varphi$. Their positive masses sum to one. Thus every constructed instance satisfies the task’s input promises.
The complementarity calculation is correct: at each coordinate, exactly one of the two support ballots differs from any given Boolean ballot. Therefore
$$
d(b,r^{(0)})+d(b,r^{(1)})=m,
\qquad D_\mu(b)=m/2.
$$
Since the rational domain is nonempty, every rational ballot is a global minimizer.
Agreement with $\ell$ forces $y=0,z=1$. This falsifies the first two disjuncts of $\Gamma$ and leaves precisely the requirement that the original coordinates satisfy $\varphi$. Consequently, both directions of the claimed equivalence hold.
The partial ballot selects eligible minimizers without restricting the minimization domain. Setting $u=0$ is permitted. The construction has polynomial encoding length and construction time, with constant-size mass encodings. This establishes the claimed $\mathrm{NP}$-hardness.
For unequal masses, the displayed inequality follows directly from
$$
d(b,s)\geq d(r,s)-d(b,r).
$$
When $\alpha>\beta$, its lower bound is strictly positive for every $b\neq r$. Because $r$ is rational, it is indeed the unique rational global minimizer. The symmetric case is valid.
For equal masses, the minimum possible distance sum is $d(r,s)$, attained by the rational support ballot $r$. The coordinatewise equality characterization is exact: differing support coordinates always contribute one, while shared coordinates contribute zero or two.
Thus a guessed ballot can be verified as both globally optimal and eligible using the stated shared-coordinate conditions. Formula evaluation and query checking take $O(c+m(u+1))$ Boolean operations; exact mass comparison has polynomial bit complexity in $L$. This proves membership in $\mathrm{NP}$ for the entire two-type restriction.
Together with the reduction, this establishes $\mathrm{NP}$-completeness for $\tau=2$. The statement for $\tau=1$ is also correct: distance zero occurs only at the sole support ballot.
Under the stated numerator–denominator encoding, $Q$ has $O(L)$ bits. Each $w_r$ is a positive integer, and normalization gives
$$
\sum_r w_r=Q.
$$
Scaling the objective by $Q>0$ preserves every minimizer. The range $0\leq F(b)\leq mQ$ and the claimed objective bit-length bound are correct.
The threshold predicate is in $\mathrm{NP}$: a certificate specifies a ballot, and rationality and its integer objective are polynomial-time checkable. Binary search uses $O(L+\log(m+1))$ oracle queries. Nonemptiness of the rational domain follows from the supplied support, so an optimum exists.
The final oracle query correctly requires the unrestricted optimum together with all eligibility conditions. This proves membership in $\mathrm{P}^{\mathrm{NP}}=\Delta_2^p$.
The deterministic enumeration algorithm likewise uses the unrestricted objective before deciding whether an eligible ballot attains it. Its stated bit-operation bound is conservative and valid: denominator preprocessing fits within $O(L^3)$, and the per-assignment bound covers formula evaluation, distances, query checks, and exact arithmetic.
Combining repeated ballots into distinct support types with multiplicity masses preserves the normalized profile objective and hence all minimizers. Rationality, positivity, and normalization are preserved, and three individuals yield $\tau\leq3$ with constant-size numerator–denominator encodings.
Accordingly, the supplied $\Theta_2^p$-hardness transfers to this bounded-support restriction under that encoding. The parameterized hardness statement is justified by hardness at a constant support bound. The direct SAT reduction independently establishes the requested conclusion using masses $1/2$.
No additional clarification, missing lemma, or mathematical repair 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.