{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:25Z","timestamp":1759638565788},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_40","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"473-484","source":"Crossref","is-referenced-by-count":7,"title":["Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dung T.","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Reitwie\u00dfner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maximilian","family":"Witek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"40_CR1","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0022-0000(90)90025-G","volume":"41","author":"J.L. Balc\u00e1zar","year":"1990","unstructured":"Balc\u00e1zar, J.L.: Self-reducibility. Journal of Computer and System Sciences\u00a041(3), 367\u2013388 (1990)","journal-title":"Journal of Computer and System Sciences"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01276436","volume":"2","author":"R. Beigel","year":"1992","unstructured":"Beigel, R., Feigenbaum, J.: On being incoherent without being very hard. Computational Complexity\u00a02, 1\u201317 (1992)","journal-title":"Computational Complexity"},{"key":"40_CR3","unstructured":"Berman, L.: Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, Ithaca, NY (1977)"},{"key":"40_CR4","unstructured":"Buhrman, H.: Resource Bounded Reductions. PhD thesis, University of Amsterdam (1993)"},{"issue":"5","key":"40_CR5","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1137\/S0097539798334736","volume":"29","author":"H. Buhrman","year":"2000","unstructured":"Buhrman, H., Fortnow, L., van Melkebeek, D., Torenvliet, L.: Separating complexity classes using autoreducibility. SIAM Journal on Computing\u00a029(5), 1497\u20131520 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0221044","volume":"21","author":"K. Ganesan","year":"1992","unstructured":"Ganesan, K., Homer, S.: Complete problems and strong polynomial reducibilities. SIAM Journal on Computing\u00a021, 733\u2013742 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"40_CR7","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1016\/j.jcss.2006.10.020","volume":"73","author":"C. Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Ogihara, M., Pavan, A., Selman, A.L., Zhang, L.: Autoreducibility, mitoticity, and immunity. Journal of Computer and System Sciences\u00a073(5), 735\u2013754 (2007)","journal-title":"Journal of Computer and System Sciences"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Pavan, A., Selman, A.L., Zhang, L.: Splitting NP-complete sets. SIAM Journal on Computing (2008)","DOI":"10.1137\/060673886"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Nguyen, D.T., Reitwie\u00dfner, C., Selman, A.L., Witek, M.: Autoreducibility of complete sets for log-space and polynomial-time reductions. Technical Report TR13-047, Electronic Colloquium on Computational Complexity (2013)","DOI":"10.1007\/978-3-642-39206-1_40"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0304-3975(93)90126-E","volume":"115","author":"S. Homer","year":"1993","unstructured":"Homer, S., Kurtz, S.A., Royer, J.S.: On 1-truth-table-hard languages. Theoretical Computer Science\u00a0115(2), 383\u2013389 (1993)","journal-title":"Theoretical Computer Science"},{"key":"40_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R.E. Ladner","year":"1976","unstructured":"Ladner, R.E., Lynch, N.A.: Relativization of questions about log space computability. Mathematical Systems Theory\u00a010, 19\u201332 (1976)","journal-title":"Mathematical Systems Theory"},{"key":"40_CR12","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., Lynch, N.A., Selman, A.L.: A comparison of polynomial time reducibilities. Theoretical Computer Science\u00a01, 103\u2013123 (1975)","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\/978-3-642-39206-1_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:36:09Z","timestamp":1557898569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}