[EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue

[Andrew Myers]

On 3/4/12 5:44 PM, Warren Smith wrote:
> On Sun, Mar 4, 2012 at 3:44 PM, Richard Fobes
> <ElectionMethods at votefair.org>  wrote:
>> Finally, after reading the articles cited by Warren Smith (listed at the
>> bottom of this reply) plus some related articles, I can reply to his
>> insistence that Condorcet-Kemeny calculations take too long to calculate.
>>   Also, this reply addresses the same claim that appears in Wikipedia both in
>> the "Kemeny-Young method" article and in the comparison table within the
>> Wikipedia "Voting systems" article (in the "polynomial time" column that
>> Markus Schulze added).
>>
>> One source of confusion is that Warren, and perhaps others, regard the
>> Condorcet-Kemeny problem as a "decision problem" that only has a "yes" or
>> "no" answer.  This view is suggested by Warren's reference (below and in
>> other messages) to the problem as being NP-complete, which only applies to
>> decision problems.  Although it is possible to formulate a decision problem
>> based on one or more specified characteristics of the Condorcet-Kemeny
>> method, that is a different problem than the Condorcet-Kemeny problem.
> --the optimization problem is at least as hard as the decision
> problem.You are erroneously creating the impression I somehow
> was unaware of this, or that you somehow have here got some new
> insight.  Neither is true.
I might try to say all this in a more friendly way than Warren does, but 
he is 100% right about all the technical issues here. This is basic 
computer science. Nothing fancy and no judgment calls are involved.

-- Andrew

-------------- next part --------------
A non-text attachment was scrubbed...
Name: andru.vcf
Type: text/x-vcard
Size: 247 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20120304/88d8f57f/attachment-0004.vcf>