{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T13:40:03Z","timestamp":1736084403363,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":10,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540537090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020816","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:07:52Z","timestamp":1131862072000},"page":"410-421","source":"Crossref","is-referenced-by-count":5,"title":["Bounded reductions"],"prefix":"10.1007","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":"34_CR1","doi-asserted-by":"crossref","unstructured":"Berman L. On the structure of complete sets. Proc. 17th IEEE conference on Foundations of Computer Science (1976) pp76\u201380.","DOI":"10.1109\/SFCS.1976.22"},{"key":"34_CR2","unstructured":"Buhrman H., S. Homer & L. Torenvliet. Honest reductions, completeness and nondeterministic complexity classes. Report CT-89-08, University of Amsterdam, Dept. of Computer Science."},{"key":"34_CR3","unstructured":"Buhrman H., E. Spaan & L. Torenvliet. On Adaptive Resource Bounded Computations. Report CT-89-08, University of Amsterdam, Dept. of Computer Science."},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Cook, S. A. The complexity of theorem-proving procedures. Proc. 3d ACM Symp. on Theory of Computing, Assoc. for Computing Machinery, New York (1971) pp151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"34_CR5","unstructured":"Homer, S. Personal communication."},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Karp, R.M. Reducibility among combinatorial problems. Complexity of Computer Computations, R.E. Miller & J.W. Thatcher eds. Plenum N.Y. pp85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R.E. Ladner","year":"1976","unstructured":"Ladner R.E. & N.A. Lynch. Relativization of Questions About Log Space Computability. Mathematical Systems Theory 10 (1976) pp19\u201332.","journal-title":"Mathematical Systems Theory"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E., N. Lynch & A.L. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science 1 (1975) 103\u2013123.","journal-title":"Theoretical Computer Science"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Soare, R.I. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag (1987) pp60\u201361.","DOI":"10.1007\/978-3-662-02460-7_5"},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"Watanabe, O. A comparison of polynomial time completeness notions. Theoretical Computer Science 54 (1987) pp249\u2013265.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020816.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T13:00:13Z","timestamp":1736082013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0020816","relation":{},"subject":[]}}