Answer: \(\Delta_2^{\mathrm P}\)-complete under polynomial-time many-to-one reductions; hence NP-hard. A requested optimal judgment can be returned in \(\mathrm{FP}^{\mathrm{NP}}\).
Proposition 2.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateOutcome determination is ΘP 2 -complete for the Kemeny, Slater, MaxHamming, Young, Dodgson, and reversal scoring rules, ∆P 2 -complete for the Leximax rule, and ΣP 2 -complete for the Condorcet and ranked agenda rules. 2. Our definition of outcome determination captures the general variant defined by Endriss et al. (2020), where in addition to L ⊆Φ sets L1, . . . , Lu ⊆Φ are given as input, and the task is to decide if there is J ∈R(P) with L ⊆J and Li ̸⊆J for each i = 1, . . . , u. This can be seen from the following construction.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite agenda \(\Phi\), constraints \(\Gamma_{\mathrm{in}}\) and \(\Gamma_{\mathrm{out}}\), complete input judgment types \(T\subseteq\mathcal{J}(\Phi,\Gamma_{\mathrm{in}})\), rational masses \(\mu_t\ge 0\) summing to \(1\), and required literals \(L\subseteq\Phi\), decide whether some \(J^\star\in\mathcal{J}(\Phi,\Gamma_{\mathrm{out}})\) minimizing \(D_\mu(J)=\sum_{t\in T}\mu_t H(J,t)\) contains \(L\), and return such a judgment if one exists.
Let \(X=\{x_1,\ldots,x_m\}\) and \(\Phi=X\cup\{\neg x:x\in X\}\). The input and output constraints \(\Gamma_{\mathrm{in}},\Gamma_{\mathrm{out}}\) are explicitly encoded propositional formulas, possibly containing auxiliary variables outside \(X\).
A complete judgment contains exactly one literal for each issue. Define \(\mathcal J(\Phi,\Gamma)\) as the complete judgments \(J\) for which \(\Gamma\land\bigwedge_{\ell\in J}\ell\) is satisfiable; auxiliary variables are thus existentially quantified. Assume \(\mathcal J(\Phi,\Gamma_{\mathrm{out}})\ne\varnothing\).
A society is given by its support: the list of the \(\tau\) distinct types \(t\in\mathcal J(\Phi,\Gamma_{\mathrm{in}})\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Given required literals \(L\subseteq\Phi\), let \(H(J,t)=|J\setminus t|\) and \(D_\mu(J)=\sum_t\mu_tH(J,t)\). Decide whether some global minimizer \(J^\star\in\mathcal J(\Phi,\Gamma_{\mathrm{out}})\) of \(D_\mu\) contains \(L\), and return one if it exists. All tied minimizers are eligible.
Use \(B\) for the total binary input length, avoiding confusion with the literal set \(L\); state running times in \(m,\tau,B\).
Is this continuous Kemeny outcome-determination decision problem in \(\mathrm P\), or is it NP-hard?
For finite explicitly listed profiles, Kemeny outcome determination is \(\Theta_2^{\mathrm P}\)-complete ([Conati, Niskanen, and Järvisalo, 2024](https://www.cs.helsinki.fi/u/mjarvisa/papers/cnj.jair24.pdf)). No complexity classification for exactly the rational-mass formulation above was verified in the literature search.
Result. The decision problem is \(\Delta_2^{\mathrm P}=\mathrm P^{\mathrm{NP}}\)-complete under polynomial-time many-to-one reductions. In particular, it is NP-hard and has no polynomial-time algorithm unless \(\mathrm P=\mathrm{NP}\). A requested optimal judgment can be returned in \(\mathrm{FP}^{\mathrm{NP}}\).
The proof treats the stated input-validity and nonempty-output assumptions as promises. Every instance constructed below satisfies them.
1. Exact integer objective
Identify each complete judgment \(J\) with its assignment \(b\in\{0,1\}^m\), where \(b_i=1\) means \(x_i\in J\). Define the marginal support
\[ p_i=\sum_{t:x_i\in t}\mu_t. \]
Then
\[ D_\mu(b)=\sum_{i=1}^m\bigl(p_i(1-b_i)+(1-p_i)b_i\bigr). \]
Indeed, if \(b_i=0\), disagreement on issue \(i\) occurs precisely among types containing \(x_i\); if \(b_i=1\), it occurs among the remaining types.
Write each mass as \(\mu_t=a_t/q_t\), with positive integers \(a_t,q_t\). Set
\[ Q=\prod_tq_t,\qquad w_t=a_t(Q/q_t). \]
Thus \(w_t\) is a positive integer and \(\sum_tw_t=Q\). Consequently,
\[ C(J):=QD_\mu(J)=\sum_tw_tH(J,t) \]
is an integer satisfying \(0\le C(J)\le mQ\). Multiplication by \(Q>0\) preserves all minimizers and ties.
The total bit length of the denominators is at most \(B\), so \(Q\) has \(O(B)\) bits. This conversion requires polynomial time, without expanding masses into individual voters.
2. Upper bound and returning a judgment
For an integer \(K\), consider the question:
Does some assignment to the issue and auxiliary variables satisfy \(\Gamma_{\mathrm{out}}\) and have \(C(J)\le K\)?
This question belongs to \(\mathrm{NP}\). A certificate specifies the issue assignment and an assignment to the auxiliary variables of \(\Gamma_{\mathrm{out}}\). Formula satisfaction and the integer cost bound can both be checked in polynomial time. This explicitly respects the existential interpretation of auxiliary variables.
Because the feasible output domain is nonempty, binary search over the integers from \(0\) to \(mQ\) finds the global minimum \(c^\star\). It uses
\[ O\bigl(B+\log(m+1)\bigr) \]
NP-oracle calls. One further NP query asks whether an assignment satisfies
\[ \Gamma_{\mathrm{out}},\qquad \bigwedge_{\ell\in L}\ell,\qquad C(J)\le c^\star. \]
Every feasible judgment has cost at least \(c^\star\), so this query accepts exactly when a global minimizer contains \(L\). Thus the decision problem belongs to \(\Delta_2^{\mathrm P}\).
If the answer is yes, recover a judgment by fixing its issue values successively. At each unfixed issue, query whether the preceding conditions, the already fixed values, and \(x_i=1\) admit an extension. Choose \(1\) if they do, and \(0\) otherwise. The invariant is that the current partial assignment extends to a qualifying global minimizer. After at most \(m\) additional queries, the resulting complete judgment is the requested output.
With elementary integer arithmetic, preprocessing can be implemented in \(O((m\tau+\tau+1)B^2)\) bit operations. Every oracle query has size \(\operatorname{poly}(m,\tau,B)\). Hence the decision and search procedures take polynomial time with, respectively, \(O(B+\log(m+1))\) and \(O(B+\log(m+1)+m)\) NP-oracle calls. These are oracle running times, not ordinary polynomial-time bounds.
3. Matching hardness using dyadic rational masses
Use the following standard \(\Delta_2^{\mathrm P}\)-complete problem: given a satisfiable propositional formula \(F\) with ordered variables \(x_1,\ldots,x_m\), and a designated variable \(x_r\), decide whether the lexicographically greatest satisfying assignment sets \(x_r=1\), with \(1\) preferred to \(0\). This theorem is recalled in Section 3 of [Endriss, de Haan, Lang, and Slavkovik (2020)](https://www.lamsade.dauphine.fr/~lang/papers/EHLM20.pdf).
Construct an instance with
\[ \Gamma_{\mathrm{in}}=\top,\qquad \Gamma_{\mathrm{out}}=F,\qquad L=\{x_r\}. \]
There are no auxiliary variables. For each \(k\in\{0,\ldots,m\}\), let \(t_k\) be the type setting the first \(k\) issues to \(1\) and all remaining issues to \(0\). These \(m+1\) types are distinct and satisfy \(\Gamma_{\mathrm{in}}\).
Define
\[ p_i=\frac12+2^{-(i+1)}\qquad (1\le i\le m) \]
and give the types the masses
\[ \mu_{t_0}=1-p_1=\frac14, \]
\[ \mu_{t_k}=p_k-p_{k+1}=2^{-(k+2)} \qquad (1\le k<m), \]
\[ \mu_{t_m}=p_m=\frac12+2^{-(m+1)}. \]
Every mass is positive. Their sum telescopes to \(1\). Moreover, \(x_i\) is true precisely in types \(t_i,\ldots,t_m\), so its actual marginal support is
\[ \sum_{k=i}^m\mu_{t_k}=p_i. \]
Applying the objective identity from Section 1 gives
\[ D_\mu(b)=\sum_{i=1}^mp_i-\sum_{i=1}^m2^{-i}b_i. \]
Therefore minimizing distance is equivalent to maximizing
\[ W(b)=\sum_{i=1}^m2^{-i}b_i. \]
This objective orders assignments exactly lexicographically. To verify this, suppose assignments \(b,c\) first differ at position \(k\), with \(b_k=1\) and \(c_k=0\). Then
\[ W(b)-W(c) \ge 2^{-k}-\sum_{i=k+1}^m2^{-i} =2^{-m}>0. \]
Thus the unique distance-minimizing feasible judgment is precisely the lexicographically greatest satisfying assignment of \(F\). It contains \(x_r\) exactly when the source instance answers yes.
All promises hold: the support types satisfy \(\Gamma_{\mathrm{in}}\), the masses are positive and sum to \(1\), and \(F\) is satisfiable. There are \(\tau=m+1\) support types, each mass has \(O(m)\) bits, and the entire construction has polynomial binary length. This proves \(\Delta_2^{\mathrm P}\)-hardness, even with tautological input constraints, no auxiliary variables, and \(|L|=1\).
Together with Section 2, this establishes the claimed completeness result.
4. Relation to finite profiles
The finite-profile hardness also transfers directly. Given an explicitly listed profile of \(N\) judgments, group identical judgments into distinct types. If type \(t\) occurs \(n_t\) times, assign \(\mu_t=n_t/N\). Then, for every output judgment,
\[ D_\mu(J)=\frac1N\sum_{v=1}^NH(J,J_v). \]
This polynomial-time transformation preserves every minimizer, every tie, and acceptance of \(L\). It therefore transfers the finite-profile \(\Theta_2^{\mathrm P}\)-hardness stated in [Conati, Niskanen, and Järvisalo (2024), Proposition 2.1](https://www.cs.helsinki.fi/u/mjarvisa/papers/cnj.jair24.pdf).
The stronger hardness above uses binary rational masses to encode lexicographic priorities in polynomial space. Expanding those masses into an explicitly listed electorate can require exponentially many voters, so the finite-profile classification does not provide the same upper bound for this representation.
⟨structured verdict parsed — rendered above⟩
The argument resolves the task. It establishes \(\Delta_2^{\mathrm P}\)-completeness under polynomial-time many-to-one reductions, with the input assumptions treated explicitly as promises. I found no mathematical gaps or incorrect steps.
The binary length of \(Q\) is bounded by the sum of the denominator lengths, hence is \(O(B)\). This argument concerns binary length rather than numerical magnitude, correctly avoiding an expansion into voters. The stated preprocessing bound \(O((m\tau+\tau+1)B^2)\) is a valid loose bound using elementary integer arithmetic.
Input-type validity need not be checked by this predicate because the prover expressly treats it as a promise. That treatment agrees with the task’s assumptions.
\[
O(\log(mQ+1))=O(B+\log(m+1)).
\]
The final query includes the required literals and bounds cost by the already determined global minimum. It therefore accepts exactly when an eligible minimizer contains \(L\); it does not substitute optimization over the restricted domain.
Ties are handled correctly. If \(L\) contains contradictory literals, the final query rejects. If \(L\) is empty, it accepts by output feasibility.
\[
p_k-p_{k+1}=2^{-(k+2)}
\]
is correct. All assigned masses are positive, their sum telescopes to \(1\), and their tail sums give exactly the claimed marginals. The boundary case \(m=1\) is also correct: the intermediate range is empty, and the two masses are \(1/4\) and \(3/4\). The source problem’s designated variable ensures \(m\ge1\).
\[
\sum_{i=k+1}^{m}2^{-i}=2^{-k}-2^{-m}.
\]
Thus the claimed lower bound \(W(b)-W(c)\ge2^{-m}>0\) holds, including \(k=m\). The objective strictly orders distinct assignments according to the specified lexicographic preference. Consequently, the feasible minimizer is unique and the designated-literal test preserves the source answer.
The running times are correctly presented as polynomial oracle running times, with their dependence on \(m,\tau,B\) stated. The argument establishes NP-hardness, rather than an unconditional separation from \(\mathrm P\). No additional clarification or 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.