{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:39Z","timestamp":1759638339410,"version":"3.41.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319500614"},{"type":"electronic","value":"9783319500621"}],"license":[{"start":{"date-parts":[[2016,12,1]],"date-time":"2016-12-01T00:00:00Z","timestamp":1480550400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-50062-1_5","type":"book-chapter","created":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T10:09:42Z","timestamp":1480500582000},"page":"56-78","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Introduction to Autoreducibility and Mitoticity"],"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":"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","published-online":{"date-parts":[[2016,12,1]]},"reference":[{"key":"5_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-13331-3_30","volume-title":"Logic and Machines: Decision Problems and Complexity","author":"K Ambos-Spies","year":"1984","unstructured":"Ambos-Spies, K.: P-mitotic sets. In: B\u00f6rger, E., Hasenjaeger, G., R\u00f6dding, D. (eds.) LaM 1983. LNCS, vol. 171, pp. 1\u201323. Springer, Heidelberg (1984). doi:10.1007\/3-540-13331-3_30"},{"key":"5_CR2","unstructured":"Berman, L.: Polynomial reducibilities and complete sets. Ph.D. thesis, Cornell University, Ithaca, NY (1977)"},{"key":"5_CR3","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. Comput. Complex. 2, 1\u201317 (1992)","journal-title":"Comput. Complex."},{"issue":"5","key":"5_CR4","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 J. Comput. 29(5), 1497\u20131520 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H Buhrman","year":"1991","unstructured":"Buhrman, H., Homer, S., Torenvliet, L.: Completeness for nondeterministic complexity classes. Math. Syst. Theory 24(3), 179\u2013200 (1991)","journal-title":"Math. Syst. Theory"},{"key":"5_CR6","first-page":"41","volume":"85","author":"H Buhrman","year":"2005","unstructured":"Buhrman, H., Torenvliet, L.: A Post\u2019s program for complexity theory. Bull. EATCS 85, 41\u201351 (2005)","journal-title":"Bull. EATCS"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R., Homer, S., Gasarch, W., Moses, M.: On honest polynomial reductions, relativizations, and P=NP. In: IEEE Structure in Complexity Theory Conference, pp. 196\u2013207 (1989)","DOI":"10.1109\/SCT.1989.41825"},{"issue":"1","key":"5_CR8","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1090\/S0002-9947-1985-0797064-9","volume":"291","author":"RG Downey","year":"1985","unstructured":"Downey, R.G.: The degrees of r.e. sets without the universal splitting property. Trans. Am. Math. Soc. 291(1), 337\u2013351 (1985)","journal-title":"Trans. Am. Math. Soc."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1002\/malq.19970430303","volume":"43","author":"RG Downey","year":"1997","unstructured":"Downey, R.G.: On the universal splitting property. Math. Log. Q. 43, 311\u2013320 (1997)","journal-title":"Math. Log. Q."},{"issue":"2","key":"5_CR10","first-page":"683","volume":"302","author":"RG Downey","year":"1987","unstructured":"Downey, R.G., Remmel, J.B., Welch, L.V.: Degrees of splittings and bases of recursively enumerable subspaces. Trans. Am. Math. Soc. 302(2), 683\u2013714 (1987)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2","key":"5_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0168-0072(89)90011-0","volume":"41","author":"RG Downey","year":"1989","unstructured":"Downey, R.G., Slaman, T.A.: Completely mitotic r.e. degrees. Ann. Pure Appl. Logic 41(2), 119\u2013152 (1989)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0168-0072(93)90092-R","volume":"59","author":"RG Downey","year":"1993","unstructured":"Downey, R.G., Stob, M.: Friedberg splittings of recursively enumerable sets. Ann. Pure Appl. Logic 59(3), 175\u2013199 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"5_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(93)90234-5","volume":"65","author":"RG Downey","year":"1993","unstructured":"Downey, R.G., Stob, M.: Splitting theorems in recursion theory. Ann. Pure Appl. Logic 65(1), 1\u2013106 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1\u20133","key":"5_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0168-0072(97)00066-3","volume":"94","author":"RG Downey","year":"1998","unstructured":"Downey, R.G., Shore, R.A.: Splitting theorems and the jump operator. Ann. Pure Appl. Logic 94(1\u20133), 45\u201352 (1998)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"5_CR15","doi-asserted-by":"publisher","first-page":"88","DOI":"10.2307\/2273946","volume":"51","author":"RG Downey","year":"1986","unstructured":"Downey, R.G., Welch, L.V.: Splitting properties of r. e. sets, degrees. J. Symbolic Logic 51(1), 88\u2013109 (1986)","journal-title":"J. Symbolic Logic"},{"key":"5_CR16","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 J. Comput. 21, 733\u2013742 (1992)","journal-title":"SIAM J. Comput."},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-642-39206-1_40","volume-title":"Automata, Languages, and Programming","author":"C Gla\u00dfer","year":"2013","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. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 473\u2013484. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-39206-1_40"},{"issue":"5","key":"5_CR18","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. J. Comput. Syst. Sci. 73(5), 735\u2013754 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"1517","DOI":"10.1137\/060673886","volume":"37","author":"C Gla\u00dfer","year":"2008","unstructured":"Gla\u00dfer, C., Pavan, A., Selman, A.L., Zhang, L.: Splitting NP-complete sets. SIAM J. Comput. 37, 1517\u20131535 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR20","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1145\/23005.23009","volume":"34","author":"S Homer","year":"1987","unstructured":"Homer, S.: Minimal degrees for polynomial reducibilities. J. ACM 34(2), 480\u2013491 (1987)","journal-title":"J. ACM"},{"key":"5_CR21","unstructured":"Kurtz, S.: Private communication to Buhrman and Torenvliet [BT05] (2005)"},{"issue":"2","key":"5_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.2307\/2272056","volume":"38","author":"R Ladner","year":"1973","unstructured":"Ladner, R.: Mitotic recursively enumerable sets. J. Symbolic Logic 38(2), 199\u2013211 (1973)","journal-title":"J. Symbolic Logic"},{"issue":"2","key":"5_CR23","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/malq.19550010205","volume":"1","author":"J Myhill","year":"1955","unstructured":"Myhill, J.: Creative sets. Math. Logic Q. 1(2), 97\u2013108 (1955)","journal-title":"Math. Logic Q."},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Selman, A.: Structural properties of nonautoreducible sets. ACM Trans. Comput. Theory 8(3) (2016). Article No. 11","DOI":"10.1145\/2898440"},{"issue":"3","key":"5_CR25","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M Ogiwara","year":"1991","unstructured":"Ogiwara, M., Watanabe, O.: On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput. 20(3), 471\u2013483 (1991)","journal-title":"SIAM J. Comput."},{"key":"5_CR26","first-page":"1224","volume":"192","author":"B Trahtenbrot","year":"1970","unstructured":"Trahtenbrot, B.: On autoreducibility. Dokl. Akad. Nauk SSSR 192, 1224\u20131227 (1970). (Translation in Soviet Math. Dokl. 11: 814\u2013817 (1970))","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Yao, A.: Coherent functions and program checkers. In: Proceedings of the 22nd Annual Symposium on Theory of Computing, pp. 89\u201394 (1990)","DOI":"10.1145\/100216.100226"}],"container-title":["Lecture Notes in Computer Science","Computability and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-50062-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T23:05:11Z","timestamp":1749769511000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-50062-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,1]]},"ISBN":["9783319500614","9783319500621"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-50062-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016,12,1]]},"assertion":[{"value":"1 December 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}