{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T14:04:13Z","timestamp":1770818653352,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1993,9,1]],"date-time":"1993-09-01T00:00:00Z","timestamp":746841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1993,9]]},"DOI":"10.1007\/bf01271369","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:32:36Z","timestamp":1111638756000},"page":"231-244","source":"Crossref","is-referenced-by-count":7,"title":["The relative power of logspace and polynomial time reductions"],"prefix":"10.1007","volume":"3","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Edith","family":"Spaan","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","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"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3,Structural Complexity II. Springer-Verlag, 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"L. Berman, On the structure of complete sets: Almost everywhere complexity and infinitely often speedup.Proc. 17th IEEE Symposium on Foundations of Computing (1976), 76?80.","DOI":"10.1109\/SFCS.1976.22"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman andH. Hartmanis, On isomorphisms and density of NP and other complete sets.SIAM J. Comput. 6 (1977), 305?322.","journal-title":"SIAM J. Comput."},{"key":"CR5","first-page":"757","volume-title":"Handbook of theoretical computer science","author":"R.B. Boppana","year":"1990","unstructured":"R.B. Boppana andM. Sipser, The complexity of finite functions. InHandbook of theoretical computer science, ed.J. van Leeuwen, vol. A Algorithms and Complexity, 757?804. Elsevier, Amsterdam. New York. Oxford. Tokyo, 1990."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H. Buhrman","year":"1991","unstructured":"H. Buhrman, S. Homer, andL. Torenvliet, On complete sets for nondeterministic classes.Math. Systems Theory 24 (1991), 179?200.","journal-title":"Math. Systems Theory"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"S. Cook, The complexity of theorem-proving procedures. InProc. 3rd ACM Symposium Theory of Computing, Shaker Heights, Ohio, 1971, 151?158.","DOI":"10.1145\/800157.805047"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(78)90018-X","volume":"7","author":"J. Hartmanis","year":"1978","unstructured":"J. Hartmanis, On the logtape isomorphism of complete sets.Theoretical Computer Science 7 (1978), 273?286.","journal-title":"Theoretical Computer Science"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"N. Jones, Space bounded reducibilities among combinatorial problems.J. Comput. System Sci. 11 (1975), 68?85.","journal-title":"J. Comput. System Sci."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"R. Karp, Reducibility among combinatorial problems. InComplexity of Computer Computations, ed.R. Miller andJ. Thatcher, 85?103. Plenum Press, New York, 1972."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R.E. Ladner","year":"1976","unstructured":"R.E. Ladner andN. Lynch, Relativization of questions about logspace computability.Math. Systems Theory 10 (1976), 19?32.","journal-title":"Math. Systems Theory"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, andA. Selman, A comparison of polynomial time reducibilities.Theoret. Comput. Sci. 1 (1975), 103?123.","journal-title":"Theoret. Comput. Sci."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E. Post","year":"1944","unstructured":"E. Post, Recursively enumerable sets of integers and their decision problems.Bull. Amer. Math. Soc. 50 (1944), 284?316.","journal-title":"Bull. Amer. Math. Soc."},{"issue":"2","key":"CR14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"W.J. Savitch, Relationships between nondeterministic and deterministic tape complexities.J. Comput. System Sci. 4(2) (1970), 177?192.","journal-title":"J. Comput. System Sci."},{"key":"CR15","unstructured":"P.M. Spira, On time-hardware complexity tradeoffs for boolean functions. InProc. 4th Hawai Symp. on System Sciences, North Hollywood, 1971, Western Periodicals Company, 525?527."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"O. Watanabe, A comparison of polynomial time completeness notions.Theoret. Comput. Sci. 54 (1987), 249?265.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01271369.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01271369\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01271369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:55:35Z","timestamp":1586177735000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01271369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,9]]}},"alternative-id":["BF01271369"],"URL":"https:\/\/doi.org\/10.1007\/bf01271369","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}