Efficient verification of Kemeny-optimal rankings The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\ldots n$ that minimizes $\sum_i d(r, q_i)$. Where $d(r, q)$ is defined as a count of the number of pairs on which $r$ and $q$ agree, scaled so that complete agreement is 1 (i.e. scaled by $k(k-1)/2$ where $k = |q|$).

Finding a Kemeny-optimal solution is known to be NP-hard in n (not surprising, it's an optimisation problem on a search space of size $n!$). What I'm wondering is if it's in fact NP-complete - if there's an (efficient?) polynomial time algorithm for verifying if a given ranking is in fact Kemeny optimal. I've seen a paper or two claiming it is, but I've not been able to find any papers which prove it. (Possibly because I live and work outside the academic firewall). Any references / ideas?
The following decision problem is NP-complete:
Kemeny Score
Input: An election ($n$ partial or full rankings of $m$ candidates) and a positive integer $k$.
Question:: Is there a ranking with $\sum_i d(r, q_i) \leq k$?

This decision problem is often seen as "natural decision problem" behind Kemeny voting. It is trivially in NP since computing the Kendall-Tau distance is in P. For NP-hardness see for example [Bartholdi, Tovey and Tick, Social Choice and Welfare 1989] or [Dwork, Kumar, Naor, and Sivakumar, WWW 2001].

However, the problem you describe above looks more like an optimization problem. To answer your question I refer to the Kemeny Winner problem which is $P_{||}^{NP}$-complete (see [Hemaspaandra, Spakowski, Vogel, TCS 2005]). Thus, already deciding whether a candidate is an (optimal) winner in Kemeny's system is presumable not in NP.