[EM] Kemeny's Rule/Condorcet's Method
Adam Tarr
atarr at purdue.edu
Thu Dec 19 18:53:47 PST 2002
>What's that you say?: "this minimization is an NP complete problem." No
>capisci.
Some problems can be done in "polynomial time". This means that if the
size of the problem (number of voters, or candidates, in our case) is N,
then the amount of steps you need to solve the problem is some polynomial
of N, say twenty plus six times N cubed. For a problem of this type
(called "P-type problems") a computer can usually crunch out an answer
pretty fast.
Other problems take an exponential amount of time, say 3^N. For large
enough N, a computer might solve a P-type problem in minutes, while an
exponential problem might take decades or more. The problems just explode
for large values of N.
"NP-type" problems are problems that can be VERIFIED in polynomial time:
that is, if you have a guess at the answer, you can check it in polynomial
time. Obviously, any P-type problem is also an NP-type problem.
"NP-complete" is one type of NP problem. Every NP-complete problem can be
converted to another NP-complete problem, so if you can solve one you can
solve any of them. The NP-complete problems have no known polynomial-time
solution, so right now they're in the exponential category. There is a
standing one million dollar prize to either find a polynomial time solution
for NP-complete problems, or prove that none exists.
>Let me ask again, is there any freeware available which will do
>Kemeny Rule tallies?
Assuming I understand Forest right, if you come up with a program that
works for decent-sized elections, that's one million dollars for you!
-Adam
----
For more information about this list (subscribe, unsubscribe, FAQ, etc),
please see http://www.eskimo.com/~robla/em
More information about the Election-Methods
mailing list