{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:28:20Z","timestamp":1778783300526,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T00:00:00Z","timestamp":1464825600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00037-016-0137-8","type":"journal-article","created":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T12:51:33Z","timestamp":1464871893000},"page":"421-467","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the connection between interval size functions and path counting"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1496-9299","authenticated-orcid":false,"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","published-online":{"date-parts":[[2016,6,2]]},"reference":[{"issue":"1","key":"137_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"Carme \u00c0lvarez","year":"1993","unstructured":"\u00c0lvarez Carme, Birgit Jenner (1993) A very hard log-space counting class. Theoretical Computer Science 107(1): 3\u201330","journal-title":"Theoretical Computer Science"},{"key":"137_CR2","doi-asserted-by":"publisher","unstructured":"Evangelos Bampas, Andreas-Nikolas G\u00f6bel, Aris Pagourtzis & Aris Tentes (2009). On the connection between interval size functions and path counting. In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, volume 5532 of Lecture Notes in Computer Science, 108\u2013117.","DOI":"10.1007\/978-3-642-02017-9_14"},{"issue":"3","key":"137_CR3","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"Martin E. Dyer","year":"2003","unstructured":"Dyer Martin E., Leslie Ann Goldberg, Greenhill Catherine S., Mark Jerrum (2003) The relative complexity of approximate counting problems. Algorithmica 38(3): 471\u2013500","journal-title":"Algorithmica"},{"issue":"5","key":"137_CR4","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1137\/S0097539705447013","volume":"36","author":"Lane A. Hemaspaandra","year":"2007","unstructured":"Hemaspaandra Lane A., Homan Christopher M., Sven Kosub, Wagner Klaus W. (2007) The complexity of computing the size of an interval. SIAM Journal on Computing 36(5): 1264\u20131300","journal-title":"SIAM Journal on Computing"},{"key":"137_CR5","doi-asserted-by":"publisher","unstructured":"Lane A. Hemaspaandra & Mitsunori Ogihara (2002). The Complexity Theory Companion. Springer-Verlag Berlin Heidelberg.","DOI":"10.1007\/978-3-662-04880-1"},{"issue":"2","key":"137_CR6","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1142\/S0129054100000181","volume":"11","author":"Harald Hempel","year":"2000","unstructured":"Hempel Harald, Wechsung Gerd (2000) The operators min and max on the polynomial hierarchy. International Journal of Foundations of Computer Science 11(2): 315\u2013342","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"4","key":"137_CR7","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"Mark Jerrum","year":"2004","unstructured":"Jerrum Mark, Sinclair Alistair, Vigoda Eric (2004) A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM 51(4): 671\u2013697","journal-title":"Journal of the ACM"},{"issue":"3","key":"137_CR8","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"Richard M. Karp","year":"1989","unstructured":"Karp Richard M., Luby Michael, Madras Neal (1989) Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms 10(3): 429\u2013448","journal-title":"Journal of Algorithms"},{"key":"137_CR9","unstructured":"Aggelos Kiayias, Aris Pagourtzis, Kiron Sharma & Stathis Zachos (2001). Acceptor-definable counting classes. In Proceedings of the 8th Panhellenic Conference on Informatics, Revised Selected Papers, volume 2563 of Lecture Notes in Computer Science, 453\u2013463."},{"key":"137_CR10","doi-asserted-by":"publisher","unstructured":"Jingcheng Liu, Pinyan Lu & Chihao Zhang (2014). FPTAS for counting weighted edge covers. In Proceedings of the 22nd Annual European Symposium on Algorithms, volume 8737 of Lecture Notes in Computer Science, 654\u2013665.","DOI":"10.1007\/978-3-662-44777-2_54"},{"key":"137_CR11","unstructured":"Aris Pagourtzis (2001). On the complexity of hard counting problems with easy decision version. In Proceedings of the 3rd Panhellenic Logic Symposium."},{"key":"137_CR12","doi-asserted-by":"publisher","unstructured":"Aris Pagourtzis & Stathis Zachos (2006). The complexity of counting functions with easy decision version. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, volume 4162 of Lecture Notes in Computer Science, 741\u2013752.","DOI":"10.1007\/11821069_64"},{"issue":"3","key":"137_CR13","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1006\/jcss.1995.1039","volume":"50","author":"Sanjeev Saluja","year":"1995","unstructured":"Saluja Sanjeev, Subrahmanyam K. V., Thakur Madhukar N. (1995) Descriptive complexity of #P functions. Journal of Computer and System Sciences 50(3): 493\u2013505","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"137_CR14","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"Seinosuke Toda","year":"1991","unstructured":"Toda Seinosuke (1991) PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing 20(5): 865\u2013877","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"137_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"Seinosuke Toda","year":"1992","unstructured":"Toda Seinosuke, Osamu Watanabe (1992) Polynomial time 1-Turing reductions from #PH to #P. Theoretical Computer Science 100(1): 205\u2013221","journal-title":"Theoretical Computer Science"},{"key":"137_CR16","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant (1979a). The complexity of computing the permanent. Theoretical Computer Science 8, 189\u2013201.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"137_CR17","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant (1979b). The complexity of enumeration and reliability problems. SIAM Journal on Computing 8(3), 410\u2013421.","DOI":"10.1137\/0208032"},{"key":"137_CR18","doi-asserted-by":"publisher","unstructured":"Dror Weitz (2006). Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 140\u2013149.","DOI":"10.1145\/1132516.1132538"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0137-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0137-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0137-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0137-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,2]],"date-time":"2017-05-02T13:26:56Z","timestamp":1493731616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0137-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,2]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["137"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0137-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,2]]}}}