{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:09Z","timestamp":1787340309607,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Gla\u00dfer et al., complete sets for all of the following complexity classes are m-mitotic: $\\mathrm{NP}$, $\\mathrm{coNP}$, $\\oplus\\mathrm{P}$, $\\mathrm{PSPACE}$, and $\\mathrm{NEXP}$, as well as all levels of $\\mathrm{PH}$, $\\mathrm{MODPH}$, and the Boolean hierarchy over $\\mathrm{NP}$. In the cases of $\\mathrm{NP}$, $\\mathrm{PSPACE}$, $\\mathrm{NEXP}$, and $\\mathrm{PH}$, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. In particular, every $\\mathrm{NP}$-complete set A splits into two $\\mathrm{NP}$-complete sets $A_1$ and $A_2$. We disprove the equivalence between autoreducibility and mitoticity for all polynomial-time-bounded reducibilities between 3-tt-reducibility and Turing-reducibility: There exists a sparse set in $\\mathrm{EXP}$ that is polynomial-time 3-tt-autoreducible, but not weakly polynomial-time T-mitotic. In particular, polynomial-time T-autoreducibility does not imply polynomial-time weak T-mitoticity, which solves an open question by Buhrman and Torenvliet.<\/jats:p>","DOI":"10.1137\/060673886","type":"journal-article","created":{"date-parts":[[2008,2,4]],"date-time":"2008-02-04T11:37:29Z","timestamp":1202125049000},"page":"1517-1535","source":"Crossref","is-referenced-by-count":14,"title":["Splitting NP-Complete Sets"],"prefix":"10.1137","volume":"37","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","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":"351","published-online":{"date-parts":[[2008,2,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies,\n                      P-mitotic sets\n                      , in Logic and Machines, Lecture Notes in Comput. Sci. 177, E. B\u00f6rger, G. Hasenj\u00e4ger, and D. Roding, eds., Springer-Verlag, New York, 1984, pp. 1\u201323.","DOI":"10.1007\/3-540-13331-3_30"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01276436"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798334736"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795279724"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"H. Buhrman and L. Torenvliet,\n                      On the structure of complete sets\n                      , in Proceedings of the 9th Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, 1994, IEEE Computer Society Press, Piscataway, NJ, pp. 118\u2013133.","DOI":"10.1109\/SCT.1994.315811"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"H. Buhrman and L. Torenvliet,\n                      Separating complexity classes using structural properties\n                      , in Proceedings of the 19th IEEE Conference on Computational Complexity, Amherst, MA, 2004, IEEE Computer Society Press, Piscataway, NJ, pp. 130\u2013138.","DOI":"10.1109\/CCC.2004.1313820"},{"key":"R8","first-page":"41","volume":"85","author":"Buhrman H.","year":"2005","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"R10","unstructured":"C. Gla\u00dfer,\n                      Logspace Mitoticity\n                      , Technical Report 400, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, Germany, 2007."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"C. Gla\u00dfer, M. Ogihara, A. Pavan, A. L. Selman, and L. Zhang,\n                      Autoreducibility, mitoticity, and immunity\n                      , in Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 3618, Springer-Verlag, New York, 2005, pp. 387\u2013398.","DOI":"10.1007\/11549345_34"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.020"},{"key":"R13","first-page":"191","volume":"28","author":"Karp R.","year":"1982","journal-title":"Enseign. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0013-8584","issn-type":"print"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19670130102"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1973-0398805-7"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.2307\/2272056"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0220030"},{"key":"R19","first-page":"814","volume":"11","author":"Trakhtenbrot B.","year":"1970","journal-title":"Dokl. Akad. Nauk SSSR, 192 (1970), pp. 1224\u20131227; translation in Soviet Math. Dokl."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Yao,\n                      Coherent functions and program checkers\n                      , in Proceedings of the 22nd Annual Symposium on Theory of Computing, 1990, pp. 89\u201394.","DOI":"10.1145\/100216.100226"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060673886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:19Z","timestamp":1787336959000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060673886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060673886"],"URL":"https:\/\/doi.org\/10.1137\/060673886","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}