Preliminary versionA preliminary version of these results was presented in: Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. In Pierpaolo Degano and Robert Gorrieri and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, 24th International Colloquium, volume 1256 of Lecture Notes in Computer Science, pages 214-224, Bologna, Italy, 7-11 July 1997. Springer-Verlag.
Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; J.4 [Social and Behavioral Sciences]
General Terms: Theory
Additional Key Words and Phrases: Completeness, election sysstems, Lewis Carroll, majority rule
Selected references
- Lane A. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299-322, December 1989.
- Lane A. Hemachandra and Gerd Wechsung. Kolmogorov characterizations of complexity classes. Theoretical Computer Science, 83(2):313-322, 28 June 1991. Note.
- Edith Hemaspaandra and Gerd Wechsung. The minimization problem for Boolean formulas. In 38th Annual Symposium on Foundations of Computer Science, pages 575-584, Miami Beach, Florida, 20-22 October 1997. IEEE.
- Birgit Jenner and Jacobo Torán. Computing functions with parallel queries to NP. Theoretical Computer Science, 141(1-2):175-193, 17 April 1995.
- Jim Kadin. P^{NP[O(log n)]} and sparse Turing-complete sets for NP. Journal of Computer and System Sciences, 39(3):282-298, December 1989.
- R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103-123, December 1975.
- A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, pages 125-129, The University of Maryland, 25-27 October 1972. IEEE.
- Christos H. Papadimitriou. On the complexity of unique solutions. Journal of the ACM, 31(2):392-400, April 1984.
- Larry J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, October 1976.
- Eric G. Wagner. A categorical treatment of pre- and post-conditions. Theoretical Computer Science, 53(1):3-24, March 1987.
- Klaus W. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833-846, October 1990.