[EM] Kemeny's Rule/Condorcet's Method

[Adam Tarr]

>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