{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:43:44Z","timestamp":1794336224600,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540287025","type":"print"},{"value":"9783540318675","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549345_34","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:05:47Z","timestamp":1127815547000},"page":"387-398","source":"Crossref","is-referenced-by-count":9,"title":["Autoreducibility, Mitoticity, and Immunity"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liyu","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: 17th Annual IEEE Conference on Computational Complexity, pp. 139\u2013145 (2002)","DOI":"10.1109\/CCC.2002.1004349"},{"key":"34_CR2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Logic and Machines","author":"K. Ambos-Spies","year":"1984","unstructured":"Ambos-Spies, K.: P-mitotic sets. In: B\u00f6rger, E., Hasenj\u00e4ger, G., Roding, D. (eds.) Logic and Machines. LNCS, vol.\u00a0177, pp. 1\u201323. Springer, Heidelberg (1984)"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0304-3975(87)90053-3","volume":"51","author":"K. Ambos-Spies","year":"1987","unstructured":"Ambos-Spies, K., Fleischhack, H., Huwig, H.: Diagonalizations over polynomial time computable sets. Theoretical Computer Science\u00a051, 177\u2013204 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"34_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"Ambos-Spies, K., Neis, H., Terwijn, A.: Genericity and measure for exponential time. Theoretical Computer Science\u00a0168(1), 3\u201319 (1996)","journal-title":"Theoretical Computer Science"},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"Balcazar, J., Mayordomo, E.: A note on genericty and bi-immunity. In: Proceedings of the Tenth Annual IEEE Conference on Computational Complexity, pp. 193\u2013196 (1995)","DOI":"10.1109\/SCT.1995.514857"},{"issue":"1","key":"34_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. Balc\u00e1zar","year":"1985","unstructured":"Balc\u00e1zar, J., Sch\u00f6ning, U.: Bi-immune sets for complexity classes. Mathematical Systems Theory\u00a018(1), 1\u201318 (1985)","journal-title":"Mathematical Systems Theory"},{"key":"34_CR7","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":"34_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90084-S","volume":"103","author":"R. Beigel","year":"1992","unstructured":"Beigel, R., Gill, J.: Counting classes: Thresholds, parity, mods, and fewness. Theoretical Computer Science\u00a0103, 3\u201323 (1992)","journal-title":"Theoretical Computer Science"},{"key":"34_CR9","unstructured":"Berman, L.: Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, Ithaca, NY (1977)"},{"issue":"5","key":"34_CR10","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.: Using autoreducibility to separate complexity classes. SIAM Journal on Computing\u00a029(5), 1497\u20131520 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1137\/S0097539795279724","volume":"27","author":"H. Buhrman","year":"1998","unstructured":"Buhrman, H., Hoene, A., Torenvliet, L.: Splittings, robustness, and structure of complete sets. SIAM Journal on Computing\u00a027, 637\u2013653 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Torenvliet, L.: On the structure of complete sets. In: Proceedings 9th Structure in Complexity Theory, pp. 118\u2013133 (1994)","DOI":"10.1109\/SCT.1994.315811"},{"key":"34_CR13","first-page":"45","volume-title":"Proceedings of Logic Colloquium 1996","author":"H. Buhrman","year":"1998","unstructured":"Buhrman, H., Torenvliet, L.: Complete sets and structure in subrecursive classes. In: Proceedings of Logic Colloquium 1996, pp. 45\u201378. Springer, Heidelberg (1998)"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Torenvliet, L.: Separating complexity classes using structural properties. In: Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 130\u2013138 (2004)","DOI":"10.1109\/CCC.2004.1313820"},{"key":"34_CR15","first-page":"41","volume":"85","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Torenvliet, L.: A Post\u2019s program for complexity theory. Bulleting of the EATCS\u00a085, 41\u201351 (2005)","journal-title":"Bulleting of the EATCS"},{"key":"34_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 Journal on Computing\u00a021, 733\u2013742 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Pavan, A., Selman, A., Sengupta, S.: Properties of NP-complete sets. In: Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pp. 184\u2013197 (2004)","DOI":"10.1109\/CCC.2004.1313839"},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"Hertrampf, U., Lautemann, C., Schwentick, T., Vollmer, H., Wagner, K.W.: On the power of polynomial time bit-reductions. In: Proceedings 8th Structure in Complexity Theory, pp. 200\u2013207 (1993)","DOI":"10.1109\/SCT.1993.336526"},{"key":"34_CR19","volume-title":"Texts in Computer Science","author":"S. Homer","year":"2001","unstructured":"Homer, S., Selman, A.: Computability and Complexity Theory. In: Texts in Computer Science, Springer, New York (2001)"},{"key":"34_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D.W. Juedes","year":"1995","unstructured":"Juedes, D.W., Lutz, J.H.: The complexity and distribution of hard problems. SIAM Joutnal on Computing\u00a024, 279\u2013295 (1995)","journal-title":"SIAM Joutnal on Computing"},{"issue":"2","key":"34_CR21","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. Journal of Symbolic Logic\u00a038(2), 199\u2013211 (1973)","journal-title":"Journal of Symbolic Logic"},{"issue":"3","key":"34_CR22","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 Journal of Computing\u00a020(3), 471\u2013483 (1991)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"34_CR23","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539701387039","volume":"31","author":"A. Pavan","year":"2002","unstructured":"Pavan, A., Selman, A.: Separation of NP-completeness notions. SIAM Journal on Computing\u00a031(3), 906\u2013918 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"Sch\u00f6ning, U.: Probabilistic complexity classes and lowness. Journal of Computer and System Sciences\u00a039, 84\u2013100 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1977)","journal-title":"Theoretical Computer Science"},{"key":"#cr-split#-34_CR26.1","unstructured":"Trahtenbrot, B.: On autoreducibility. Dokl. Akad. Nauk SSSR, 192 (1970);"},{"key":"#cr-split#-34_CR26.2","unstructured":"Translation in Soviet Math. Dokl. \u00a011, 814\u2013817 (1970)"},{"key":"34_CR27","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1109\/SCT.1995.514864","volume-title":"Proceedings of the 10th Annual Conference on Structure in Complexity Theory","author":"N. Tran","year":"1995","unstructured":"Tran, N.: On P-immunity of nondeterministic complete sets. In: Proceedings of the 10th Annual Conference on Structure in Complexity Theory, pp. 262\u2013263. IEEE Computer Society Press, Los Alamitos (1995)"},{"key":"34_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-540-31834-7_5","volume-title":"Machines, Computations, and Universality","author":"K.W. Wagner","year":"2004","unstructured":"Wagner, K.W.: Leaf language classes. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol.\u00a03354, pp. 60\u201381. Springer, Heidelberg (2004)"},{"key":"34_CR29","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theoretical Computer Science\u00a03, 23\u201333 (1977)","journal-title":"Theoretical Computer Science"},{"key":"34_CR30","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","Mathematical Foundations of Computer Science 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549345_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T10:44:18Z","timestamp":1735987458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11549345_34","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11549345","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}