Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP

DOI10.1007/3-540-63165-8_179zbMath1401.68097OpenAlexW1595189656MaRDI QIDQ4571954

Hemaspaandra, Lane A., Edith Hemaspaandra, Jörg Rothe

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_179

Mathematics Subject Classification ID

Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Computing functions with parallel queries to NP
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• More complicated questions about maxima and minima, and some closures of NP
• Voting schemes for which it can be difficult to tell who won the election
• A comparison of polynomial time reducibilities
• Bounded Query Classes
• On the complexity of unique solutions
• The difference and truth-table hierarchies for NP
• Exact analysis of Dodgson elections

This page was built for publication: Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP