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

[Richard Fobes]

On 12/22/2011 7:26 AM, Kristofer Munsterhjelm wrote:
> 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).

Good point.

I'm not sure what the most precise wording would be, but perhaps 
something like:

Most scenarios for an NP-hard problem typically require that every 
possibility be tested in order to know the characteristics of each -- 
and every -- possibility.

> 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.

I agree that "you don't necessarily need to inspect every single 
possibility".

Of course knowing how to identify which situations do require inspecting 
every possibility (or even a large number of possibilities) can itself 
be a challenge.

Richard Fobes