{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:10:18Z","timestamp":1787386218346,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We investigate the structure of EXP-complete and hard sets under various kinds of reductions. In particular, we are interested in the way in which information that makes the set complete is stored in the set. We study for various types of reductions the question of whether the set difference A-S for a hard set A and a sparse set S is still hard. We also address the question of which complete sets A can be split into sets A\n                    <jats:sub>1<\/jats:sub>\n                    and A\n                    <jats:sub>2<\/jats:sub>\n                    such that $A\\equiv^P_r A_1\\equiv^P_r A_2$ for reduction type r, i.e., which complete sets are mitotic. We obtain both positive and negative answers to these questions depending on the reduction type and the structure of the sparse set.\n                  <\/jats:p>","DOI":"10.1137\/s0097539795279724","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"637-653","source":"Crossref","is-referenced-by-count":17,"title":["Splittings, Robustness, and Structure of Complete Sets"],"prefix":"10.1137","volume":"27","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albrecht","family":"Hoene","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Klaus Ambos\u2010Spies, On the structure of polynomial time degrees, Lecture Notes in Comput. Sci., Vol. 166, Springer, Berlin, 1984, 198\u201320886h:68053","DOI":"10.1007\/3-540-12920-0_18"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79235-9"},{"key":"R3","unstructured":"L. Berman,\n                      Polynomial Reducibilities and Complete Sets\n                      , PhD thesis, Cornell University, 1977."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90034-X"},{"key":"R5","unstructured":"H. Buhrman,\n                      Resource Bounded Reductions\n                      , PhD thesis, University of Amsterdam, June 1993."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"H. Buhrman, L. Fortnow, and L. Torenvliet,\n                      Using autoreducibility in separating complexity classes\n                      , in Proc. 36d IEEE Symposium on Foundations of Computer Science, Milwaukee, Wis, 1995, pp. 520\u2013527.","DOI":"10.1109\/SFCS.1995.492582"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090397"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271369"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"H. Buhrman and L. Torenvliet,\n                      On the structure of complete sets\n                      , in Proc. Structure in Complexity Theory 9th annual conference, Amsterdam, Holland, 1994, IEEE computer society press, pp. 118\u2013133.","DOI":"10.1109\/SCT.1994.315811"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90146-Z"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Peter van Helden, Leen Torenvliet, P\u2010selective self\u2010reducibles sets: a new characterization of P, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 44\u20135196c:68056","DOI":"10.1109\/SCT.1993.336542"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0221044"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0220595-7"},{"key":"R14","unstructured":"J. Kelly,\n                      General Topology\n                      , D. van Nostrand Company Inc., New York, 1955."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.2307\/2272056"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80016-X"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.2307\/1970214"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01704904"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744288"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90125-D"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090391"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90132-0"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90040-6"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795279724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:32Z","timestamp":1787336012000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795279724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795279724"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795279724","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}