|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP | | Edith Hemaspaandra
; Lane A. Hemaspaandra
; Joerg Rothe
; | | Date: |
25 Jul 1999 | | Journal: | Journal of the ACM vol. 44, no. 6, pp. 806--825, 1997 | | Subject: | Computational Complexity ACM-class: F.1.3; F.2.2; J.4 | cs.CC | | Abstract: | 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 $ hetatwo$, 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. | | Source: | arXiv, cs.CC/9907036 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER