{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:10Z","timestamp":1725516790898},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_16","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"149-159","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Counting the Optimal Solutions"],"prefix":"10.1007","author":[{"given":"Miki","family":"Hermann","sequence":"first","affiliation":[]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"16_CR1","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0022-0000(05)80004-2","volume":"48","author":"M. Cadoli","year":"1994","unstructured":"Cadoli, M., Lenzerini, M.: The Complexity of Propositional Closed World Reasoning and Circumscription. Journal of Computer and System Sciences\u00a048(2), 255\u2013310 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"16_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of Generalized Satisfiability Counting Problems. Information and Computation\u00a0125(1), 1\u201312 (1996)","journal-title":"Information and Computation"},{"issue":"3","key":"16_CR3","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1016\/j.tcs.2005.03.012","volume":"340","author":"A. Durand","year":"2005","unstructured":"Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive Reductions and Complete Problems for Counting Complexity Classes. Theoretical Computer Science\u00a0340(3), 496\u2013513 (2005)","journal-title":"Theoretical Computer Science"},{"key":"16_CR4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/978-1-4612-1872-2_4","volume-title":"Complexity Theory Retrospective\u00a0II","author":"L. Fortnow","year":"1997","unstructured":"Fortnow, L.: Counting complexity. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective\u00a0II, pp. 81\u2013107. Springer, Heidelberg (1997)"},{"issue":"1","key":"16_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1811129.1811131","volume":"6","author":"Z. Galil","year":"1974","unstructured":"Galil, Z.: On Some Direct Encodings of Nondeterministic Turing Machines Operating in Polynomial Time into P-complete Problems. SIGACT News\u00a06(1), 19\u201324 (1974)","journal-title":"SIGACT News"},{"issue":"6","key":"16_CR6","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/BF01204168","volume":"28","author":"W.I. Gasarch","year":"1995","unstructured":"Gasarch, W.I., Krentel, M.W., Rappoport, K.J.: OptP as the Normal Behavior of NP-complete Problems. Mathematical Systems Theory\u00a028(6), 487\u2013514 (1995)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L.A. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L.A., Vollmer, H.: The Satanic Notations: Counting Classes beyond #P and other Definitional Adventures. SIGACT News, Complexity Theory Column\u00a08\u00a026(1), 2\u201313 (1995)","journal-title":"SIGACT News, Complexity Theory Column\u00a08"},{"issue":"1-2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(94)00080-3","volume":"141","author":"B. Jenner","year":"1995","unstructured":"Jenner, B., Tor\u00e1n, J.: Computing Functions with Parallel Queries to NP. Theoretical Computer Science\u00a0141(1-2), 175\u2013193 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"16_CR9","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF00276023","volume":"26","author":"J. K\u00f6bler","year":"1989","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: On Counting and Approximation. Acta Informatica\u00a026(4), 363\u2013379 (1989)","journal-title":"Acta Informatica"},{"issue":"3","key":"16_CR10","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M.W. Krentel","year":"1988","unstructured":"Krentel, M.W.: The Complexity of Optimization Problems. Journal of Computer and System Sciences\u00a036(3), 490\u2013509 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"16_CR11","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(92)90073-O","volume":"97","author":"M.W. Krentel","year":"1992","unstructured":"Krentel, M.W.: Generalizations of OptP to the Polynomial Hierarchy. Theoretical Computer Science\u00a097(2), 183\u2013198 (1992)","journal-title":"Theoretical Computer Science"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1007\/11821069_64","volume-title":"Mathematical Foundations of Computer Science 2006","author":"A. Pagourtzis","year":"2006","unstructured":"Pagourtzis, A., Zachos, S.: The Complexity of Counting Functions with Easy Decision Version. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 741\u2013752. Springer, Heidelberg (2006)"},{"key":"16_CR13","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1137\/0212037","volume":"12","author":"A. Selman","year":"1983","unstructured":"Selman, A., Mei-Rui, X., Book, R.: Positive Relativizations of Complexity Classes. SIAM Journal on Computing\u00a012(3), 565\u2013579 (1983)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"Toda, S., Ogiwara, M.: Counting Classes are at least as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing\u00a021(2), 316\u2013328 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"16_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"Toda, S., Watanabe, O.: Polynomial-Time 1-Turing Reductions from #PH to #P. Theoretical Computer Science\u00a0100(1), 205\u2013221 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"16_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The Complexity of Computing the Permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"16_CR18","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"16_CR19","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"Wagner, K.: Bounded Query Classes. SIAM Journal on Computing\u00a019(5), 833\u2013846 (1990)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"Wrathall, C.: Complete Sets and the Polynomial-Time Hierarchy. Theoretical Computer Science\u00a03(1), 23\u201333 (1976)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T06:07:42Z","timestamp":1709186862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}