{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T10:14:52Z","timestamp":1670321692687},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1997,11]]},"abstract":"\n 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\u2014a candidate who beats all other candidates in pairwise majority-rule elections. Bartholdi, Tovey, and Trick provided a lower bound\u2014NP-hardness\u2014on 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_\n 2<\/jats:sub>\n \n p<\/jats:italic>\n <\/jats:sup>\n for which it becomes the most natural complete problem known. It follows that determining the winner in \n Carroll's elections is not NP-complete unless the polynomial hierarchy collapses.\n <\/jats:p>","DOI":"10.1145\/268999.269002","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"806-825","source":"Crossref","is-referenced-by-count":79,"title":["Exact analysis of Dodgson elections"],"prefix":"10.1145","volume":"44","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[{"name":"Le Moyne College, Syracuse, NY"}]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[{"name":"Univ. of Rochester, Rochester, NY"}]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Univ. Jena, Jena, Germany"}]}],"member":"320","published-online":{"date-parts":[[1997,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00303169","article-title":"Voting schemes for which it can be difficult to tell who won the election","volume":"6","author":"BARTHOLDI J.","year":"1989","unstructured":"BARTHOLDI III , J. , TOVEY , C. , AND TRICK , M. 1989 . Voting schemes for which it can be difficult to tell who won the election . Social Choice and Welfare 6 , 157 - 165 . BARTHOLDI III, J., TOVEY, C., AND TRICK, M. 1989. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6, 157-165.","journal-title":"Social Choice and Welfare"},{"key":"e_1_2_1_2_1","volume-title":"Theory of Committees and Elections","author":"BLACK D.","unstructured":"BLACK , D. 1958. Theory of Committees and Elections . Cambridge University Press , Cambridge, Mass . BLACK, D. 1958. Theory of Committees and Elections. Cambridge University Press, Cambridge, Mass."},{"key":"e_1_2_1_3_1","volume-title":"Introduction to the Theory of Complexity","author":"BOVET D.","unstructured":"BOVET , D. , AND CRESCENZI , P. 1993. Introduction to the Theory of Complexity . Prentice-Hall , Englewood Cliffs, N.J. BOVET, D., AND CRESCENZI, P. 1993. Introduction to the Theory of Complexity. Prentice-Hall, Englewood Cliffs, N.J."},{"key":"e_1_2_1_4_1","volume-title":"Essai sur l'Application de L'Analyse gtla Probabilit# des D#cisions Rendues a la Pluraliste des Voix. Facsimile reprint of original published in Paris","author":"CONDORCET M.","year":"1972","unstructured":"CONDORCET , M. 1785. Essai sur l'Application de L'Analyse gtla Probabilit# des D#cisions Rendues a la Pluraliste des Voix. Facsimile reprint of original published in Paris , 1972 , by the Imprimerie Royale . CONDORCET, M. 1785. Essai sur l'Application de L'Analyse gtla Probabilit# des D#cisions Rendues a la Pluraliste des Voix. Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale."},{"key":"e_1_2_1_5_1","unstructured":"DODGSON C. 1876. A method of taking votes on more than two issues. Pamphlet printed by the Clarendon Press Oxford and headed \"not yet published\" (see the discussions in McLean and Urken {1995} and Black {1958} both of which reprint this paper). DODGSON C. 1876. A method of taking votes on more than two issues. Pamphlet printed by the Clarendon Press Oxford and headed \"not yet published\" (see the discussions in McLean and Urken {1995} and Black {1958} both of which reprint this paper)."},{"key":"e_1_2_1_6_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"GAREY M.","unstructured":"GAREY , M. , AND JOHNSON , D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company . GAREY, M., AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"issue":"3","key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","article-title":"The strong exponential hierarchy collapses","volume":"39","author":"HEMACHANDRA L.","year":"1989","unstructured":"HEMACHANDRA , L. 1989 . The strong exponential hierarchy collapses . J. Comput. Syst. Sci. 39 , 3 , 299 - 322 . HEMACHANDRA, L. 1989. The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39, 3, 299-322.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90282-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/261342.261344"},{"key":"e_1_2_1_11_1","first-page":"575","volume-title":"Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"HEMASPAANDRA E.","year":"1997","unstructured":"HEMASPAANDRA , E. , AND WECHSUNG , G. 1997 . The minimization problem for boolean formulas . In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press . New York , pp. 575 - 584 . HEMASPAANDRA, E., AND WECHSUNG, G. 1997. The minimization problem for boolean formulas. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press. New York, pp. 575-584."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00080-3"},{"issue":"3","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","article-title":"pNP{log nl and sparse Turing-complete sets for NP","volume":"39","author":"KADIN J.","year":"1989","unstructured":"KADIN , J. 1989 . pNP{log nl and sparse Turing-complete sets for NP . J. Comput. Syst. Sci. 39 , 3 , 282 - 298 . KADIN, J. 1989. pNP{log nl and sparse Turing-complete sets for NP. J. Comput. Syst. Sci. 39, 3, 282-298.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","article-title":"The difference and truth-table hierarchies for NP","volume":"21","author":"KGBLER J.","year":"1987","unstructured":"KGBLER , J. , SCHGNING , U. , AND WAGNER , K. 1987 . The difference and truth-table hierarchies for NP . RAIRO Theoret. Inf. Appl. 21 , 419 - 435 . KGBLER, J., SCHGNING, U., AND WAGNER, K. 1987. The difference and truth-table hierarchies for NP. RAIRO Theoret. Inf. Appl. 21, 419-435.","journal-title":"RAIRO Theoret. Inf. Appl."},{"issue":"2","key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","article-title":"A comparison of polynomial time reducibilities","volume":"1","author":"LADNER R.","year":"1975","unstructured":"LADNER , R. , LYNCH , N. , AND SELMAN , A. 1975 . A comparison of polynomial time reducibilities . Theoret. Comput. Sci. 1 , 2 , 103 - 124 . LADNER, R., LYNCH, N., AND SELMAN, A. 1975. A comparison of polynomial time reducibilities. Theoret. Comput. Sci. 1, 2, 103-124.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_16_1","volume-title":"Classics of Social Choice","author":"MCLEAN I.","unstructured":"MCLEAN , I. , AND URKEN , A. 1995. Classics of Social Choice . University of Michigan Press , Ann Arbor , Mich. MCLEAN, I., AND URKEN, A. 1995. Classics of Social Choice. University of Michigan Press, Ann Arbor, Mich."},{"key":"e_1_2_1_17_1","first-page":"125","volume-title":"Proceedings of the 13th IEEE Symposium on Switching and Automata Theory. IEEE","author":"MEYER A.","year":"1972","unstructured":"MEYER , A. , AND STOCKMEYER , L. 1972 . The equivalence problem for regular expressions with squaring requires exponential space . In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory. IEEE , New York , pp. 125 - 129 . MEYER, A., AND STOCKMEYER, L. 1972. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory. IEEE, New York, pp. 125-129."},{"key":"e_1_2_1_18_1","volume-title":"Cambridge University Press","author":"MUELLER D.","unstructured":"MUELLER , D. 1989. Public Choice H. Cambridge University Press , Cambridge , Mass . MUELLER, D. 1989. Public Choice H. Cambridge University Press, Cambridge, Mass."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1038\/scientificamerican0676-21","article-title":"The choice of voting systems","volume":"234","author":"NIEMI R.","year":"1976","unstructured":"NIEMI , R. , AND RIKER , W. 1976 . The choice of voting systems . Scient. Am. 234 , 21 - 27 . NIEMI, R., AND RIKER, W. 1976. The choice of voting systems. Scient. Am. 234, 21-27.","journal-title":"Scient. Am."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.322435"},{"key":"e_1_2_1_21_1","volume-title":"Computational Complexity","author":"PAPADIMITRIOU C.","unstructured":"PAPADIMITRIOU , C. 1994. Computational Complexity . Addison-Wesley , Cambridge, Mass . PAPADIMITRIOU, C. 1994. Computational Complexity. Addison-Wesley, Cambridge, Mass."},{"key":"e_1_2_1_22_1","first-page":"269","volume-title":"Proceedings of the 6th GI Conference on Theoretical Computer Science. Springer-Verlag Lecture Notes in Computer Science","volume":"145","author":"PAPADIMITRIOU C.","year":"1983","unstructured":"PAPADIMITRIOU , C. , AND ZACHOS , S. 1983 . Two remarks on the power of counting . In Proceedings of the 6th GI Conference on Theoretical Computer Science. Springer-Verlag Lecture Notes in Computer Science , vol. 145 . Springer-Verlag, New York , pp. 269 - 276 . PAPADIMITRIOU, C., AND ZACHOS, S. 1983. Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science. Springer-Verlag Lecture Notes in Computer Science, vol. 145. Springer-Verlag, New York, pp. 269-276."},{"key":"e_1_2_1_23_1","volume-title":"String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"SANKOFF D.","unstructured":"SANKOFF , D. , AND KRUSKAL , J. , EDS. 1983. Time Warps , String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison . Addison-Wesley , Reading, Pa . SANKOFF, D., AND KRUSKAL, J., EDS. 1983. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, Pa."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"STOCKMEYER L.","year":"1977","unstructured":"STOCKMEYER , L. 1977 . The polynomial-time hierarchy . Theoret. Comput. Sci. 3 , 1 - 22 . STOCKMEYER, L. 1977. The polynomial-time hierarchy. Theoret. Comput. Sci. 3, 1-22.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90049-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219058"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/268999.269002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T09:18:21Z","timestamp":1670318301000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/268999.269002"}},"subtitle":["Lewis Carroll's 1876 voting system is complete for parallel access to NP"],"short-title":[],"issued":{"date-parts":[[1997,11]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1997,11]]}},"alternative-id":["10.1145\/268999.269002"],"URL":"http:\/\/dx.doi.org\/10.1145\/268999.269002","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1997,11]]}}}