[EM] Fast Condorcet-Kemeny calculations -- in polynomial time

[Kristofer Munsterhjelm]

On 12/22/2011 08:27 AM, Richard Fobes wrote:

> NP-hard problems require that every possibility be tested in order to
> know the characteristics of each -- and every -- possibility.

Just as a nitpick: that's not entirely true. Consider integer 
programming. Integer programming is NP-hard, but in practice, there are 
algorithms that do significantly better than brute force. These usually 
work by excluding ranges of answers where one can reason that whatever 
the optimum outcome is, it must be better than what lies in that region 
(or that going in the direction given cannot possibly give a feasible 
answer).

NP-hard problems are properly speaking also decision problems. Thus, if 
the problem says "find the social ordering for which the sum of the 
magnitudes of pairwise contests going in the other direction is less 
than x", then you don't need to find the very best. All you have to do 
is find an ordering with the sum less than x. Of course, you can then 
use a binary search to find the minimal x for which it's possible to 
solve the problem, but my point is that you don't necessarily need to 
inspect every single possibility.