{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:29Z","timestamp":1767339989670},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_64","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"741-752","source":"Crossref","is-referenced-by-count":18,"title":["The Complexity of Counting Functions with Easy Decision Version"],"prefix":"10.1007","author":[{"given":"Aris","family":"Pagourtzis","sequence":"first","affiliation":[]},{"given":"Stathis","family":"Zachos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"64_CR1","doi-asserted-by":"crossref","unstructured":"\u00c0lvarez, C., Jenner, B.: A very hard log space counting class. In: Proceedings of Structure in Complexity Theory Conference, pp. 154\u2013168 (1990)","DOI":"10.1109\/SCT.1990.113964"},{"issue":"3","key":"64_CR2","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"},{"issue":"3","key":"64_CR3","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"M. Dyer","year":"2003","unstructured":"Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: On the relative complexity of approximate counting problems. Algorithmica\u00a038(3), 471\u2013500 (2003)","journal-title":"Algorithmica"},{"key":"#cr-split#-64_CR4.1","unstructured":"Hemaspaandra, L.A., Homan, C.M., Kosub, S., Wagner, K.W.: The complexity of computing the size of an interval. Technical Report cs.cc\/0502058, ACM Computing Research Repository (2005);"},{"key":"#cr-split#-64_CR4.2","doi-asserted-by":"crossref","unstructured":"Preliminary version: Hemaspaandra, L.A., Kosub, S., Wagner, K.W.: The complexity of computing the size of an interval. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 1040\u20131051. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-48224-5_84"},{"key":"64_CR5","unstructured":"Jerrum, M., Sinclair, A.: The Markov chain Monte-Carlo method: an approach to approximate counting and integration. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, pp. 482\u2013520, PWS (1996)"},{"key":"64_CR6","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"R.M. Karp","year":"1989","unstructured":"Karp, R.M., Luby, M., Madras, N.: Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms\u00a010, 429\u2013448 (1989)","journal-title":"Journal of Algorithms"},{"key":"64_CR7","unstructured":"Kiayias, A., Pagourtzis, A., Sharma, K., Zachos, S.: The complexity of determining the order of solutions. In: Proceedings of the First Southern Symposium on Computing, Hattiesburg, Mississippi, December 4-5 (1998)"},{"key":"64_CR8","unstructured":"Kiayias, A., Pagourtzis, A., Zachos, S.: Cook Reductions Blur Structural Differences Between Functional Complexity Classes. In: Proceedings of the 2nd Panhellenic Logic Symposium, Delphi, July 13\u201317, pp. 132\u2013137 (1999)"},{"issue":"2","key":"64_CR9","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"On Self-Reducibility and Weak P-Selectivity","year":"1983","unstructured":"On Self-Reducibility and Weak P-Selectivity. Journal of Computer and System Sciences\u00a026(2), 209\u2013221 (1983)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"64_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":"4","key":"64_CR11","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"},{"key":"64_CR12","unstructured":"Pagourtzis, A.: On the complexity of hard counting problems with easy decision version. In: Proceedings of the 3rd Panhellenic Logic Symposium, Anogia, Crete, July 17\u201321 (2001)"},{"issue":"3","key":"64_CR13","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1006\/jcss.1995.1039","volume":"50","author":"S. Saluja","year":"1995","unstructured":"Saluja, S., Subrahmanyam, K.V., Thakur, M.N.: Descriptive Complexity of #P Functions. Journal of Computer and System Sciences\u00a050(3), 493\u2013505 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"64_CR14","unstructured":"Simon, J.: On some Central Problems of Computational Complexity. PhD thesis, Cornell University, Ithaca, NY (1975)"},{"issue":"5","key":"64_CR15","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing\u00a020(5), 865\u2013877 (1991)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"64_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"},{"key":"64_CR17","unstructured":"Toran, J.: Structural Properties of the Counting Hierarchies. PhD thesis, Facultat d\u2019Informatica de Barcelona (1988)"},{"issue":"2","key":"64_CR18","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":"64_CR19","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"},{"key":"64_CR20","series-title":"LNCS","first-page":"24","volume-title":"STACS 94","author":"H. Vollmer","year":"1994","unstructured":"Vollmer, H.: On different reducibility notions for function classes. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 24\u201326. Springer, Heidelberg (1994)"},{"issue":"2","key":"64_CR21","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(86)90141-6","volume":"47","author":"K.W. Wagner","year":"1986","unstructured":"Wagner, K.W.: Some observations on the connection between counting and recursion. Theoretical Computer Science\u00a047(2), 131\u2013147 (1986)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T02:43:36Z","timestamp":1707187416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11821069_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}