{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:07Z","timestamp":1725664027004},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582014"},{"type":"electronic","value":"9783540485667"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58201-0_74","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:32:59Z","timestamp":1330270379000},"page":"263-273","source":"Crossref","is-referenced-by-count":5,"title":["On the cutting edge of relativization: The resource bounded injury method"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"22_CR1","unstructured":"S. Arora, R. Impagliazzo, and U. Vazirani. On the role of the Cook-Levin theorem in complexity theory. manuscript, 1193."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"issue":"1","key":"22_CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill. Relative to a random oracle A, P A \u2260NP A \u2260 Co-NPA with probability 1. SIAM J. Comput., 10(1):96\u2013113, February 1981.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"22_CR4","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"90","author":"S. R. Buss","year":"1991","unstructured":"S.R. Buss and L. Hay. On truth-table reducibility to SAT. Information and Computation, 90(2):86\u2013102, February 1991.","journal-title":"Information and Computation"},{"key":"22_CR5","first-page":"282","volume-title":"Lecture Notes in Computer Science vol. 45","author":"M. I. Dekhtyar","year":"1977","unstructured":"M.I. Dekhtyar. On the relation of deterministic and nondeterministic complexity classes. In Proceedings Mathematical Foundations of Computer Science, Lecture Notes in Computer Science vol. 45, pages 282\u2013287, Berlin, 1977. Springer-Verlag."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, and S.A. Kurtz. The isomorphism conjecture holds relative to an oracle. In Proc. 33rd IEEE Symposium Foundations of Computer Science, pages 30\u201339, 1992.","DOI":"10.1109\/SFCS.1992.267821"},{"key":"22_CR7","unstructured":"B. Fu, H. Li, and Y. Zhong. Some properties of exponential time complexity classes. In Proc. Structure in Complexity Theory seventh annual conference, pages 50\u201357. IEEE computer society press, 1992."},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1073\/pnas.43.2.236","volume":"43","author":"R. M. Friedberg","year":"1957","unstructured":"R.M. Friedberg. Two recursively enumerable sets of incomparable degrees of unsolvability. In Proc. Nat. Acad. Sci., volume 43, pages 236\u2013238, 1957.","journal-title":"Proc. Nat. Acad. Sci."},{"issue":"4","key":"22_CR9","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1137\/0213045","volume":"13","author":"H. Heller","year":"1984","unstructured":"Hans Heller. On relativized polynomial and exponential computations. SIAM J. Comput, 13(4):717\u2013725, november 1984.","journal-title":"SIAM J. Comput"},{"issue":"3","key":"22_CR10","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0019-9958(86)80012-2","volume":"71","author":"H. Heller","year":"1986","unstructured":"Hans Heller. On relativized exponential and probabilistic complexity classes. Information and Control., 71(3):231\u2013243, December 1986.","journal-title":"Information and Control."},{"issue":"3","key":"22_CR11","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2\/3","key":"22_CR12","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis, N. Immerman, and V. Sewelson. Sparse sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, 65(2\/3):158\u2013181, May\/June 1985.","journal-title":"Information and Control"},{"key":"22_CR13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285\u2013306, 1965.","journal-title":"Trans. Amer. Math. Soc."},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and G. Tardos. Decision versus search problems in superpolynomial time. In Proc. 30th IEEE Symposium on Foundations of Computer Science, pages 222\u2013227, 1989.","DOI":"10.1109\/SFCS.1989.63482"},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0890-5401(89)90029-1","volume":"81","author":"K. Ko","year":"1989","unstructured":"K. Ko. Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Information and Computation, 81:62\u201387, 1989.","journal-title":"Information and Computation"},{"issue":"1","key":"22_CR16","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(83)80023-0","volume":"57","author":"Stuart A. A. Kurtz","year":"1983","unstructured":"Stuart A. Kurtz. On the random oracle hypothesis. Information and Control, 57(1):40\u201347, April 1983.","journal-title":"Information and Control"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"S. Mocas. Using bounded query classes to separate classes in the exponential time hierarchy. To appear in proceedings of the 9th structure in complexity theory conference, 1994.","DOI":"10.1109\/SCT.1994.315818"},{"key":"22_CR18","first-page":"194","volume":"108","author":"A. A. Muchnik","year":"1956","unstructured":"A.A. Muchnik. On the unsolvability of the problem of reducibility in the theory of algorithms. Dokl. Acad. Nauk SSSR, 108:194\u2013197, 1956.","journal-title":"Dokl. Acad. Nauk SSSR"},{"key":"22_CR19","series-title":"TR83-575","volume-title":"PhD thesis","author":"V. Sewelson","year":"1983","unstructured":"V. Sewelson. A study of the Structure of NP. PhD thesis, Cornell University, Ithaca. New York 14853, August 1983. TR83-575."},{"issue":"1","key":"22_CR20","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. I. Seiferas","year":"1978","unstructured":"J.I. Seiferas, M.J. Fischer, and A.R. Meyer. Separating nondeterministic time complexity classes. J. ACM, 25(1):146\u2013167, January 1978.","journal-title":"J. ACM"},{"key":"22_CR21","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"4","author":"A. Shamir","year":"1992","unstructured":"A. Shamir. IP=PSPACE. Journal of the ACM, 4:869\u2013877, October 1992.","journal-title":"Journal of the ACM"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Robert I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag, 1987.","DOI":"10.1007\/978-3-662-02460-7"},{"key":"22_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1976.","journal-title":"Theoretical Computer Science"},{"key":"22_CR24","first-page":"331","volume-title":"Lecture Notes in Computer Science vol. 223","author":"L. Torenvliet","year":"1986","unstructured":"L. Torenvliet and P. Van Emde Boas. Diagonalisation methods in a polynomial setting. In Proc. Structure in Complexity Theory, Lecture Notes in Computer Science vol. 223, pages 331\u2013334, Berlin, 1986. Springer-Verlag."},{"key":"22_CR25","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S. Z\u00e1k","year":"1983","unstructured":"S. Z\u00e1k. A Turing machine hierarchy. Theoretical Computer Science, 26:327\u2013333, 1983.","journal-title":"Theoretical Computer Science"}],"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-58201-0_74.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:29Z","timestamp":1605647909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58201-0_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582014","9783540485667"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-58201-0_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}