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.
---- Election-Methods mailing list - see http://electorama.com/em for list info
