{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T10:31:41Z","timestamp":1725532301350},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020162"},{"type":"electronic","value":"9783642020179"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02017-9_14","type":"book-chapter","created":{"date-parts":[[2009,5,11]],"date-time":"2009-05-11T11:38:06Z","timestamp":1242041886000},"page":"108-117","source":"Crossref","is-referenced-by-count":1,"title":["On the Connection between Interval Size Functions and Path Counting"],"prefix":"10.1007","author":[{"given":"Evangelos","family":"Bampas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas-Nikolas","family":"G\u00f6bel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aris","family":"Tentes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"14_CR1","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1137\/S0097539705447013","volume":"36","author":"L.A. Hemaspaandra","year":"2007","unstructured":"Hemaspaandra, L.A., Homan, C.M., Kosub, S., Wagner, K.W.: The complexity of computing the size of an interval. SIAM J. Comput.\u00a036(5), 1264\u20131300 (2007)","journal-title":"SIAM J. Comput."},{"key":"#cr-split#-14_CR2.1","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":"#cr-split#-14_CR2.2","doi-asserted-by":"crossref","unstructured":"Extended and revised version: Acceptor-definable complexity classes. LNCS 2563, pp.\u00a0453\u2013463. Springer, Heidelberg (2003)","DOI":"10.1007\/3-540-38076-0_29"},{"key":"14_CR3","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. Theor. Comput. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"14_CR4","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 J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"14_CR5","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 J. Comput.\u00a020(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR6","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. Theor. Comput. Sci.\u00a0100(1), 205\u2013221 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR7","unstructured":"Kiayias, A., Pagourtzis, A., Zachos, S.: Cook reductions blur structural differences between functional complexity classes. In: Panhellenic Logic Symposium, pp. 132\u2013137 (1999)"},{"issue":"3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"M.E. Dyer","year":"2003","unstructured":"Dyer, M.E., Goldberg, L.A., Greenhill, C.S., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica\u00a038(3), 471\u2013500 (2003)","journal-title":"Algorithmica"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"\u00c0lvarez, C., Jenner, B.: A very hard log space counting class. In: Structure in Complexity Theory Conference, pp. 154\u2013168 (1990)","DOI":"10.1109\/SCT.1990.113964"},{"issue":"3","key":"14_CR10","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. J. Comput. Syst. Sci.\u00a050(3), 493\u2013505 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR11","unstructured":"Pagourtzis, A.: On the complexity of hard counting problems with easy decision version. In: Proceedings of 3rd Panhellenic Logic Symposium, Anogia, Crete, July 17-21 (2001)"},{"key":"14_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)"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1142\/S0129054100000181","volume":"11","author":"H. Hempel","year":"2000","unstructured":"Hempel, H., Wechsung, G.: The operators min and max on the polynomial hierarchy. Int. J. Found. Comput. Sci.\u00a011(2), 315\u2013342 (2000)","journal-title":"Int. J. Found. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02017-9_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T06:17:22Z","timestamp":1619763442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02017-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020162","9783642020179"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02017-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}