Answer: \(\mathrm{NP}\)-hard ranking computation; the requested randomized polynomial expected-time algorithm exists if and only if \(\mathrm{NP}=\mathrm{RP}\). The minimum expected query count is always \(0\).
Corollary 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor k ≥2 arms, Q ∈Q(k) with Kemeny ranking τ, fixed approximation guarantee 0 < ρ ≤k(k−1) 2 and probability δ, Algorithm 1 is a (δ, ρ)-PAC algorithm. That is, after t < 1 2x2y samples of each pair of arms, Algo- rithm 1 returns ranking ˆτ such that with probability (1 −δ), we have KS(Q, ˆτ) −KS(Q, τ) ≤ρ. Here x := k·(k−1) ρ and y := −ln δ k(k−1) > 1. Sampling Without Replacement Suppose that, while sampling voters uniformly at random, none of the voters v ∈N can be asked twice about their preferences over a pair of arms.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\) alternatives, a society distribution \(\mu\) over complete rankings, independent sampling access to \(\mu\), and \(\rho, \delta > 0\), design an adaptive pair-query policy and output ranking \(\sigma\) minimizing queries subject to \(\Pr[\mathrm{KS}_\mu(\sigma) - \min_\pi \mathrm{KS}_\mu(\pi) \le \rho] \ge 1-\delta\).
Let \(m=k\geq2\) be the number of alternatives. A society \(\mu\) is given explicitly by its support: \(\tau\) distinct strict complete rankings, each with positive binary-rational mass, summing to \(1\). Here \(\tau\) is the support size, not \(m!\); let \(L\) be the total input bit length.
Define \(q_{ij}=\Pr_{R\sim\mu}[i\succ_R j]\) and \(\operatorname{KS}_{\mu}(\sigma)=\sum_{i\succ_\sigma j}q_{ji}\), without normalization by the number of pairs. Output rankings are strict; any tied optimum is acceptable.
The input also contains binary rationals \(0<\rho\leq\binom m2\) and \(0<\delta<1\), with \(\log(m(m-1)/\delta)>1\). A unit-cost pair query chooses distinct alternatives and reveals only their comparison in a fresh independent draw from \(\mu\); it reveals neither the sampled ranking nor its identity.
A randomized adaptive policy may read the explicit support, choose queries using previous responses, and stop with a ranking \(\sigma\). It must satisfy \(\Pr[\operatorname{KS}_{\mu}(\sigma)-\min_{\pi}\operatorname{KS}_{\mu}(\pi)\leq\rho]\geq1-\delta\), where probability includes sampling and internal randomness. Its objective is to minimize its expected total number of queries on the supplied instance, among all policies satisfying this guarantee.
Does this additive PAC query-minimization problem admit a randomized algorithm with polynomial expected running time in \(m,\tau,L,1/\rho,\log(1/\delta)\), or is it NP-hard?
For finite electorates, uniform sampling with replacement gives the additive PAC guarantee using \(O(m^4\rho^{-2}\log(m/\delta)+m^2)\) total pair queries and exact Kemeny optimization. [Source](https://arxiv.org/html/2312.11663)
The same verified guarantee covers arbitrary pairwise-probability matrices, hence distributional societies; it establishes neither minimum query cost nor polynomial total running time. [Source](https://arxiv.org/html/2312.11663)
The required ranking computation is \(\mathrm{NP}\)-hard, although the minimum expected query count is always \(0\). More precisely, a randomized algorithm with the requested polynomial expected running time exists if and only if \(\mathrm{NP}=\mathrm{RP}\).
Thus the hardness concerns producing the ranking. Computing only the optimal query-cost value is trivial.
Write the explicitly supplied society as \(\mu=\{(R_\ell,p_\ell):1\leq\ell\leq\tau\}\). Let \(d(\sigma,R)\) denote the number of unordered pairs on which the strict rankings \(\sigma\) and \(R\) disagree. Expanding the definition gives
\(\displaystyle \operatorname{KS}_{\mu}(\sigma)=\sum_{\ell=1}^{\tau}p_\ell d(\sigma,R_\ell).\)
Consequently, a deterministic policy can enumerate all strict rankings, evaluate their scores exactly using rational arithmetic, and output an optimum without making any query. It satisfies the PAC guarantee with probability \(1\).
Since query counts are nonnegative, the minimum expected query count is therefore \(0\), attained on every instance.
Moreover, any policy attaining this minimum makes no queries almost surely: if its query count is \(Q\), then \(\Pr[Q\geq1]\leq\mathbb E[Q]=0\).
We now address the intended computational question: producing a valid output while attaining this minimum.
We use the \(\mathrm{NP}\)-complete Feedback Arc Set problem: given a directed graph \(G=(V,E)\) and an integer \(t\), determine whether at most \(t\) arcs can be deleted to make the graph acyclic. Its completeness is established in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Loops can be removed while subtracting their number from the deletion budget. The remaining trivial cases can be decided directly. Thus we may assume a loopless graph with \(m=|V|\geq2\) and \(e=|E|\geq1\).
For a strict ranking \(\sigma\) of \(V\), define
\(\displaystyle b_G(\sigma)=|\{(u,v)\in E:v\succ_\sigma u\}|.\)
Then the minimum feedback arc set size equals \(\min_\sigma b_G(\sigma)\). Indeed:
These two inequalities prove the equality.
Put \(B=\binom m2\). For each arc \((u,v)\), list the remaining vertices as \(w_1,\ldots,w_{m-2}\), and construct the two strict rankings
\(\displaystyle R_{uv}:u\succ v\succ w_1\succ\cdots\succ w_{m-2},\)
\(\displaystyle S_{uv}:w_{m-2}\succ\cdots\succ w_1\succ u\succ v.\)
When \(m=2\), the list of remaining vertices is empty.
Both rankings place \(u\) above \(v\). On every other unordered pair, their comparisons are opposite: pairs within the list are reversed, and each listed vertex moves from below both \(u,v\) to above both.
Therefore, for every strict ranking \(\sigma\),
\(\displaystyle d(\sigma,R_{uv})+d(\sigma,S_{uv})=B-1+2\mathbf1[v\succ_\sigma u].\)
Also, for any ranking \(R\) and its complete reversal \(R^{\mathrm{rev}}\),
\(\displaystyle d(\sigma,R)+d(\sigma,R^{\mathrm{rev}})=B,\)
because exactly one of the two rankings disagrees with \(\sigma\) on each unordered pair.
Let \(P\) be the smallest power of two satisfying \(P\geq2e\). Thus
\(\displaystyle 2e\leq P<4e.\)
Take the two rankings above for every arc. Add \((P-2e)/2\) reversal pairs of any fixed ranking, obtaining exactly \(P\) ranking occurrences. Give each occurrence mass \(1/P\).
Merge identical rankings, assigning each distinct ranking its total mass. This produces precisely the required support representation: distinct strict rankings, positive dyadic masses, and total mass \(1\). Its support size satisfies \(\tau\leq P\).
Summing the preceding identities yields
\(\displaystyle P\operatorname{KS}_{\mu}(\sigma)=e(B-1)+2b_G(\sigma)+\frac{P-2e}{2}B=\frac{PB}{2}-e+2b_G(\sigma).\)
Hence
\(\displaystyle \operatorname{KS}_{\mu}(\sigma)=\frac B2-\frac eP+\frac2P b_G(\sigma).\)
In particular, minimizing the society’s Kemeny score is exactly equivalent to minimizing the graph’s backward-arc count.
The construction is polynomial: \(P<4e\), each ranking has polynomial encoding length, and duplicate rankings can be merged in polynomial time. Every mass has denominator \(P\), with \(O(\log P)\) bits.
Choose the legal input parameters
\(\displaystyle \rho=\frac1P,\qquad\delta=\frac14.\)
We have \(0<\rho\leq B\), and \(\log(m(m-1)/\delta)\geq\log8>1\).
Let \(b_*=\min_\pi b_G(\pi)\). The score identity gives
\(\displaystyle \operatorname{KS}_{\mu}(\sigma)-\min_\pi\operatorname{KS}_{\mu}(\pi)=\frac2P\bigl(b_G(\sigma)-b_*\bigr).\)
The quantity \(b_G(\sigma)-b_*\) is a nonnegative integer. Therefore, whenever the additive error is at most \(\rho=1/P\), it must be \(0\). Every successful PAC output is an exact optimum.
Crucially, \(1/\rho=P<4e\). Thus a running-time bound polynomial in \(1/\rho\) remains polynomial in the source-instance size.
For a deterministic algorithm, the reduction immediately proves hardness: an accurate output decides Feedback Arc Set by testing whether \(b_G(\sigma)\leq t\). Equivalently, the exact score-threshold problem is \(\mathrm{NP}\)-complete. Membership in \(\mathrm{NP}\) follows because a ranking is a polynomial-size certificate whose rational score is exactly evaluable in polynomial time.
Suppose an algorithm attains the minimum expected query count and has the requested polynomial expected running time on every instance.
On the reduced instances, it makes no queries almost surely, by Section 1. Its PAC guarantee and Section 3 imply
\(\displaystyle \Pr[b_G(\sigma)=b_*]\geq\frac34.\)
Let \(p(n)\geq1\) be a polynomial upper bound on its expected running time on reductions of source inputs of length \(n\). Such a polynomial exists because every requested runtime parameter is polynomially bounded in \(n\).
Construct a bounded-time randomized Feedback Arc Set decider:
For a NO instance, every ranking has \(b_G(\sigma)>t\), so acceptance is impossible.
For a YES instance, an optimum ranking passes the test. Markov’s inequality gives timeout probability at most \(1/8\). Therefore acceptance probability is at least
\(\displaystyle \frac34-\frac18=\frac58>\frac12.\)
This is an \(\mathrm{RP}\) algorithm for an \(\mathrm{NP}\)-complete problem. Polynomial reductions imply \(\mathrm{NP}\subseteq\mathrm{RP}\). Conversely, \(\mathrm{RP}\subseteq\mathrm{NP}\): an accepting random seed is a polynomial-size, deterministically verifiable certificate. Hence
\(\displaystyle \mathrm{NP}=\mathrm{RP}.\)
Thus the proposed randomized polynomial expected-time algorithm cannot exist unless this equality holds.
Assume \(\mathrm{NP}=\mathrm{RP}\). We show that this assumption suffices for all supplied societies, not only those constructed above.
Choose a common denominator \(D\) for the input masses and write \(p_\ell=a_\ell/D\). Taking the product of their denominators ensures that \(D\) has polynomial bit length. Then
\(\displaystyle W(\sigma)=D\operatorname{KS}_{\mu}(\sigma)=\sum_{\ell=1}^{\tau}a_\ell d(\sigma,R_\ell)\)
is an integer satisfying \(0\leq W(\sigma)\leq DB\).
The following predicate belongs to \(\mathrm{NP}\): “There exists a strict ranking extending a specified prefix and satisfying \(W(\sigma)\leq h\).” A complete ranking is its certificate; both prefix compatibility and the score inequality can be checked exactly in polynomial time.
Exact answers to this predicate suffice to obtain an optimum:
These procedures use at most \(M=O(\log(DB+1)+m^2)\) predicate calls.
Under \(\mathrm{NP}=\mathrm{RP}\), each call has a polynomial-time randomized decision algorithm. Independent repetition reduces its error probability to at most \(\delta/M\), using \(O(\log(M/\delta))\) repetitions. This bound holds conditionally for each adaptive call, so a union bound gives probability at least \(1-\delta\) that every answer is correct.
On that event, the procedure outputs an exact Kemeny optimum. If an erroneous answer prevents the procedure from continuing, it outputs any fixed ranking. Its running time remains polynomial in \(m,\tau,L,\log(1/\delta)\).
The procedure makes zero pair queries and satisfies the requested PAC guarantee. It therefore attains the minimum query cost.
The optimal expected query count is identically \(0\), but producing the required ranking contains an \(\mathrm{NP}\)-hard optimization problem even with dyadic masses and polynomially bounded \(1/\rho\). The requested randomized polynomial expected-time algorithm exists exactly when \(\mathrm{NP}=\mathrm{RP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated task. The minimum expected query count is \(0\) on every supplied instance, while producing a ranking satisfying the guarantee is NP-hard. The claimed equivalence with \(\mathrm{NP}=\mathrm{RP}\) is supported by both directions of the argument.
I found no major or minor mathematical issues requiring repair.
The prover correctly uses the explicit support representation. For every strict ranking \(\sigma\),
\[ \operatorname{KS}_{\mu}(\sigma) =\sum_{\ell=1}^{\tau}p_\ell d(\sigma,R_\ell). \]
Each unordered pair contributes its probability of disagreement with \(\sigma\), exactly as specified in USER_TASK. There is no unintended normalization.
Enumerating all rankings and evaluating these rational scores terminates and produces an exact optimum without queries. This policy is admissible because the optimization over policies imposes no computational bound. Consequently, the optimal expected query count is exactly \(0\).
The almost-sure conclusion is also correct: a nonnegative integer query count \(Q\) with \(\mathbb E[Q]=0\) satisfies \(\Pr[Q\geq1]=0\).
Thus the prover’s subsequent computational question—whether a polynomial-time policy can attain this query minimum while satisfying the PAC guarantee—is precisely relevant to the task.
The cited theorem is the NP-completeness of directed Feedback Arc Set: given a directed graph and a deletion budget, decide whether deleting at most that many arcs makes the graph acyclic. This is the appropriate source problem and is included in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Removing loops and subtracting their number from the budget preserves the decision problem; resulting trivial cases can be handled directly. Restricting the construction to \(m\geq2\) and \(e\geq1\) therefore does not discard the hard cases.
The equality between minimum feedback arc set size and minimum backward-arc count is fully justified:
Both directions are valid, including graphs containing oppositely directed arcs between a pair of vertices.
For each arc \((u,v)\), the two constructed rankings agree on \(u\succ v\) and disagree on every other unordered pair. Therefore their combined distance from \(\sigma\) is
\[ B-1+2\mathbf1[v\succ_\sigma u]. \]
The constant \(B-1\) correctly counts all pairs other than \(\{u,v\}\). The remaining pair contributes either \(0\) or \(2\).
The case \(m=2\) is covered: both gadget rankings coincide, and the displayed identity still holds.
The reversal identity
\[ d(\sigma,R)+d(\sigma,R^{\mathrm{rev}})=B \]
is correct because exactly one of the two opposite comparisons disagrees with \(\sigma\) on each pair.
The padding count is integral. Since \(e\geq1\), the chosen power of two \(P\) is even; hence \((P-2e)/2\) is a nonnegative integer. When \(P=2e\), no padding is needed.
The construction has exactly \(P\) occurrences, each with mass \(1/P\). Merging duplicates preserves every score and produces distinct support rankings with positive dyadic masses summing to \(1\). No lower bound on the number of distinct rankings is required.
The bound
\[ 2e\leq P<4e \]
is correct, so both the number of occurrences and the support size are polynomially bounded. Ranking encodings, mass encodings, and duplicate merging all require polynomial resources.
The score calculation checks out:
\[ \begin{aligned} P\operatorname{KS}_{\mu}(\sigma) &=e(B-1)+2b_G(\sigma)+\frac{P-2e}{2}B\\ &=\frac{PB}{2}-e+2b_G(\sigma). \end{aligned} \]
Thus
\[ \operatorname{KS}_{\mu}(\sigma) =\frac B2-\frac eP+\frac2P b_G(\sigma). \]
The constant term does not depend on \(\sigma\), and the coefficient of \(b_G(\sigma)\) is positive. Exact Kemeny optimization therefore corresponds exactly to minimum backward-arc optimization.
The parameters \(\rho=1/P\) and \(\delta=1/4\) satisfy the stated input restrictions. In particular, \(B\geq1\), \(P\geq2\), and the logarithmic condition holds.
The excess score is
\[ \frac2P\bigl(b_G(\sigma)-b_*\bigr). \]
The parenthesized quantity is a nonnegative integer. Any nonoptimal ranking therefore has excess score at least \(2/P\), which exceeds \(\rho\). Every successful PAC output must be an exact optimum.
Crucially, \(1/\rho=P<4e\). The reduction does not hide exponential complexity in the allowed dependence on inverse accuracy.
Testing the resulting ranking against the original budget correctly decides Feedback Arc Set whenever the output is successful. The associated rational score-threshold problem has polynomially verifiable ranking certificates, supporting the stated NP-completeness claim.
The prover correctly converts expected polynomial running time into bounded polynomial running time.
All parameters of the constructed society are polynomially bounded in the source input length, so a polynomial expected-time bound \(p(n)\) exists. Truncating execution after \(8p(n)\) steps gives timeout probability at most \(1/8\) by Markov’s inequality.
For a YES instance, exact optimality occurs with probability at least \(3/4\), so successful acceptance before timeout has probability at least
\[ \frac34-\frac18=\frac58. \]
No independence between optimality and timeout is needed for this subtraction.
For a NO instance, no valid ranking passes the budget test. Rejecting invalid outputs and timeouts preserves one-sided error. The resulting decider is therefore an RP algorithm.
Using NP-completeness and closure under polynomial reductions gives \(\mathrm{NP}\subseteq\mathrm{RP}\). The reverse inclusion follows from polynomial-length accepting random-bit sequences for bounded-time RP machines. The conclusion \(\mathrm{NP}=\mathrm{RP}\) is justified.
Taking the product of input denominators yields a common denominator \(D\) with polynomial bit length. The integer objective
\[ W(\sigma)=\sum_{\ell=1}^{\tau}a_\ell d(\sigma,R_\ell) \]
satisfies \(0\leq W(\sigma)\leq DB\).
The prefix-constrained threshold predicate is in NP: its certificate is a complete strict ranking, and both prefix compatibility and the integer score inequality are verifiable in polynomial time.
With correct predicate answers, binary search determines the minimum integer score, and the stated prefix procedure constructs a ranking attaining it. The number of calls is bounded by
\[ O\bigl(\log(DB+1)+m^2\bigr), \]
which is polynomial in the input length.
Under \(\mathrm{NP}=\mathrm{RP}\), independent repetition provides the stated per-call error bound. Fresh randomness makes that bound valid conditional on each adaptive call’s history. The union bound therefore establishes probability at least \(1-\delta\) that every answer is correct.
On that event, the output is an exact optimum. The fallback ensures a strict ranking is still produced if erroneous answers prevent continuation. Running time remains polynomial, and the procedure makes zero queries on every execution.
This establishes the claimed sufficiency and attains the optimal query cost.
The output distinguishes the trivial optimal query-cost value from the hard ranking computation and proves the claimed randomized complexity characterization. No additional clarification is necessary to verify the argument.
⟨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.