Computer Science – Computational Complexity
Scientific paper
1999-07-25
Journal of the ACM vol. 44, no. 6, pp. 806--825, 1997
Computer Science
Computational Complexity
22 pages
Scientific paper
In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner---a candidate who beats all other candidates in pairwise majority-rule elections. Bartholdi, Tovey, and Trick provided a lower bound---NP-hardness---on the computational complexity of determining the election winner in Carroll's system. We provide a stronger lower bound and an upper bound that matches our lower bound. In particular, determining the winner in Carroll's system is complete for parallel access to NP, i.e., it is complete for $\thetatwo$, for which it becomes the most natural complete problem known. It follows that determining the winner in Carroll's elections is not NP-complete unless the polynomial hierarchy collapses.
Hemaspaandra Edith
Hemaspaandra Lane A.
Rothe Joerg
No associations
LandOfFree
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-619294