[EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue
andru at cs.cornell.edu
Sun Mar 4 17:17:24 PST 2012
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 247 bytes
Desc: not available
More information about the Election-Methods