{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:30:37Z","timestamp":1758274237408},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_28","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"348-360","source":"Crossref","is-referenced-by-count":9,"title":["\u0398in2sup-Completeness: A Classical Approach for New Results"],"prefix":"10.1007","author":[{"given":"Holger","family":"Spakowski","sequence":"first","affiliation":[]},{"given":"J\u00f6rg","family":"Vogel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J. Bartholdi III","year":"1989","unstructured":"J. Bartholdi III, C.A. Tovey, M.A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6 (1989), 157\u2013165","journal-title":"Social Choice and Welfare"},{"key":"28_CR2","unstructured":"M. Condorcet. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. Paris, 1785"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"S.A. Cook. The complexity of theorem-proving procedures. Proceedings of the 3rd IEEE Symp. on the Foundations of Computer Science 1971, 524\u2013535","DOI":"10.1145\/800157.805047"},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/0133030","volume":"33","author":"P.C. Fishburn","year":"1977","unstructured":"P.C. Fishburn. Condorcet social choice functions. SIAM J Appl Math, 33 (1977), 469\u2013489","journal-title":"SIAM J Appl Math"},{"key":"28_CR5","unstructured":"M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Company,1979"},{"issue":"6","key":"28_CR6","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E. Hemaspaandra","year":"1997","unstructured":"E. Hemaspaandra, L. Hemaspaandra, J. Rothe. Exact Analysis of Dodgson Elections: Lewis Carroll\u2019s 1876 Voting System is Complete for Parallel Access to NP. JACM, 44(6) (1997), 806\u2013825","journal-title":"JACM"},{"key":"28_CR7","unstructured":"E. Hemaspaandra. The complexity of Kemeny elections. In preparation."},{"key":"28_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-44612-5_5","volume-title":"Computational Politics: Electoral Systems","author":"E. Hemaspaandra","year":"2000","unstructured":"E. Hemaspaandra, L. Hemaspaandra. Computational Politics: Electoral Systems. Proceedings of MFCS 2000, LNCS 1893, 64\u201383"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"R.M. Karp. Reducibility among combinatorial problems, in R.E. Miller and J.W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 85\u2013103","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36 (1988), 490\u2013509","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR11","unstructured":"M. Machtey, P. Young. An Introduction to General Theory of Algorithms. North-Holland, New York, 1978"},{"key":"28_CR12","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994"},{"key":"28_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1007\/3-540-48321-7_44","volume-title":"The Operators minCh and maxCh on the Polynomial Hierarchy","author":"H. Spakowski","year":"1999","unstructured":"H. Spakowski, J. Vogel. The Operators minCh and maxCh on the Polynomial Hierarchy. Proceedings of FCT 99, LNCS 1684, 524\u2013535"},{"key":"28_CR14","unstructured":"H. Spakowski, J. Vogel. The complexity of voting schemes-a method for proving completeness for parallel access to NP. Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany, TR Math\/Inf\/00\/16."},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K.W. Wagner","year":"1987","unstructured":"K.W. Wagner. More complicated questions about maxima an minima, and some closures of NP. Theoretical Computer Science, 51(1987), 53\u201380","journal-title":"Theoretical Computer Science"},{"key":"28_CR16","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K.W. Wagner","year":"1990","unstructured":"K.W. Wagner. Bounded query classes. SIAM Journal on Computing, 19(1990), 833\u2013846","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:17:19Z","timestamp":1556770639000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}