EXACT ANALYSIS OF DODGSON ELECTIONS - CARROLL,LEWIS 1876 VOTING SYSTEM IS COMPLETE FOR PARALLEL ACCESS TO NP

In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences beco mes a Condorcet winner-a candidate who beats all other candidates in p airwise majority-rule elections. Bartholdi, Tovey, and Trick provided a lower bound-NP-hardness-on the computational complexity of determini ng the election winner in Carroll's system. We provide. a stronger low er bound and an upper bound that matches our lower bound. In particula r, determining the winner in Carroll's system is complete for parallel access to NP, that is, it is complete for Theta(2)(p), for which it b ecomes the most natural complete problem known. It follows that determ ining the winner in Carroll's elections is not NP-complete unless the polynomial hierarchy collapses.