00000cab a22000003a 4500 UP-99796217608727537 Buklod 20231007234724.0 m |o d | ta 090226s xx d | ||r ||||| || (iLib)UPD-00077096451 DENGII eng Hemaspaandra, Edith Exact analysis of Dodgson elections Lewis Carroll's 1876 voting system is complete for parallel access to NP. pp. 806-825 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, that is, it is complete for Theta_2p 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. Theory of computation. Computation by abstract devices. Analysis of algorithms and problem complexity. Computer applications. Theory. Journal of the ACM 44, 6 (1997). FO UPD DENG-II Article