{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:58Z","timestamp":1760202538352},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_84","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"1040-1051","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Computing the Size of an Interval"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Kosub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"84_CR1","volume-title":"International Series in Computer Science","author":"D. P. Bovet","year":"1994","unstructured":"D. P. Bovet and P. Crescenzi. Introduction to the Theory of Complexity. International Series in Computer Science. Prentice Hall, New York, 1994."},{"key":"84_CR2","first-page":"96","volume":"64","author":"A. E. F. Clementi","year":"1998","unstructured":"A. E. F. Clementi, J. D. P. Rolim, and L. Trevisan. Recent advances towards proving P=BPP. Bulletin of the EATCS, 64:96\u2013103, 1998.","journal-title":"Bulletin of the EATCS"},{"key":"84_CR3","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem-proving procedures. In Proceedings 3rd ACM Symposium on Theory of Computing, pages 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"84_CR4","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48:116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"84_CR5","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic complexity classes. SIAM Journal on Computing, 6:675\u2013695, 1977.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"84_CR6","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/0220034","volume":"20","author":"A. V. Goldberg","year":"1991","unstructured":"A. V. Goldberg and M. Sipser. Compression and ranking. SIAM Journal on Computing, 20(3):524\u2013536, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"84_CR7","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1137\/0220033","volume":"20","author":"J. Goldsmith","year":"1991","unstructured":"J. Goldsmith, L. A. Hemachandra, D. Joseph, and P. Young. Near-testable sets. SIAM Journal on Computing, 20(3):506\u2013523, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"84_CR8","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and A. L. Selman. Complexity measures for public-key crypto-systems. SIAM Journal on Computing, 17(2):309\u2013335, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"84_CR9","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1142\/S0129054100000181","volume":"11","author":"H. Hempel","year":"2000","unstructured":"H. Hempel and G. Wechsung. The operators min and max on the polynomial hierarchy. International Journal of Foundations of Computer Science, 11(2):315\u2013342, 2000.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"84_CR10","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/BF01192696","volume":"29","author":"U. Hertrampf","year":"1996","unstructured":"U. Hertrampf, H. Vollmer, and K. W. Wagner. On balanced versus unbalanced computation trees. Mathematical Systems Theory, 29:411\u2013421, 1996.","journal-title":"Mathematical Systems Theory"},{"key":"84_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K. Ko","year":"1983","unstructured":"K. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences, 26:209\u2013221, 1983.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5-6","key":"84_CR12","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0020-0190(99)00142-8","volume":"72","author":"S. Kosub","year":"1999","unstructured":"S. Kosub. A note on unambiguous function classes. Information Processing Letters, 72(5-6):197\u2013203, 1999.","journal-title":"Information Processing Letters"},{"issue":"6","key":"84_CR13","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0218073","volume":"18","author":"R. E. Ladner","year":"1989","unstructured":"R. E. Ladner. Polynomial space counting problems. SIAM Journal on Computing, 18(6):1087\u20131097, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"84_CR14","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"L. Levin. Universal sorting problems. Problems of Information Transmission, 9:265\u2013266, 1973.","journal-title":"Problems of Information Transmission"},{"key":"84_CR15","series-title":"Technical Report MIT\/LCS\/TM-126","volume-title":"With what frequency are apparently intractable problems difficult","author":"A. R. Meyer","year":"1979","unstructured":"A. R. Meyer and M. Paterson. With what frequency are apparently intractable problems difficult? Technical Report MIT\/LCS\/TM-126, Laboratory for Computer Science, MIT, Cambridge, MA, 1979."},{"key":"84_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1109\/SWAT.1972.29","volume-title":"Proceedings 13th Symposium on Switching and Automata Theory","author":"A. R. Meyer","year":"1972","unstructured":"A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential time. In Proceedings 13th Symposium on Switching and Automata Theory, pages 125\u2013129. IEEE Computer Society Press, Los Alamitos, 1972."},{"key":"84_CR17","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"G. L. Miller","year":"1976","unstructured":"G. L. Miller. Riemann\u2019s hypothesis and tests for primality. Journal of Computer and System Sciences, 13:300\u2013317, 1976.","journal-title":"Journal of Computer and System Sciences"},{"key":"84_CR18","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"M. Ogiwara and L. A. Hemachandra. A complexity theory of feasible closure properties. Journal of Computer and System Sciences, 46:295\u2013325, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"84_CR19","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, 1994."},{"key":"84_CR20","unstructured":"J. Simon. On Some Central Problems in Computational Complexity. PhD thesis, Cornell University, Ithaca, 1975."},{"key":"84_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"84_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. G. Valiant","year":"1976","unstructured":"L. G. Valiant. Relative complexity of checking and evaluation. Information Processing Letters, 5:20\u201323, 1976.","journal-title":"Information Processing Letters"},{"issue":"3","key":"84_CR23","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):411\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"84_CR24","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1006\/inco.1995.1109","volume":"120","author":"H. Vollmer","year":"1995","unstructured":"H. Vollmer and K. W. Wagner. Complexity classes of optimization functions. Information and Computation, 120:198\u2013219, 1995.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_84","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T18:27:24Z","timestamp":1551032844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_84","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}