{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:16Z","timestamp":1725663616260},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_20","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:14:09Z","timestamp":1330254849000},"page":"175-184","source":"Crossref","is-referenced-by-count":2,"title":["Splittings, robustness and structure of complete sets"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Albrecht","family":"Hoene","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. On the structure of polynomial time degrees. In M. Fontet and K. Mehlhorn, editors, STACS 84, Lecture Notes in Computer Science 166, pages 198\u2013208. Springer-Verlag, 1984.","DOI":"10.1007\/3-540-12920-0_18"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. P-mitotic sets. In E. B\u00f6rger, G. Hasenj\u00e4ger, and D. Roding, editors, Logic and Machines, Lecture Notes in Computer Science 177, pages 1\u201323. Springer-Verlag, 1984.","DOI":"10.1007\/3-540-13331-3_30"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"L. Berman. On the structure of complete sets: Almost everywhere complexity and infinitely often speedup. Proc. 17th IEEE Symp. on Foundations of Computing, pages 76\u201380, 1976.","DOI":"10.1109\/SFCS.1976.22"},{"key":"20_CR5","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, 1977."},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and H. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM J. Comput., 6:305\u2013322, 1977.","journal-title":"SIAM J. Comput."},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H. Buhrman","year":"1991","unstructured":"H. Buhrman, S. Homer, and L. Torenvliet. On complete sets for nondeterministic classes. Math. Systems Theory, 24:179\u2013200, 1991.","journal-title":"Math. Systems Theory"},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0022-0000(78)90034-X","volume":"17","author":"S. Breidbart","year":"1978","unstructured":"S. Breidbart. On splitting recursive sets. J. Comput. System Sci., 17:56\u201364, 1978.","journal-title":"J. Comput. System Sci."},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"H. Buhrman, B. Spaan, and L. Torenvliet. Bounded reductions. In C. Chofrut and M. Jantzen, editors, STACS 1991, Lecture Notes in Computer Science 480, pages 410\u2013421, 1991.","DOI":"10.1007\/BFb0020816"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"K. Ganesan and S. Homer. Complete problems and strong polynomial reducibilities. In B. Monien and R. Cori, editors, STACS 89, Lecture Notes in Computer Science 349, pages 240\u2013250, 1989.","DOI":"10.1007\/BFb0028988"},{"key":"20_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(78)90018-X","volume":"7","author":"J. Hartmanis","year":"1978","unstructured":"J. Hartmanis. On the logtape isomorphism of complete sets. Theoretical Computer Science, 7:273\u2013286, 1978.","journal-title":"Theoretical Computer Science"},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"N. Jones. Space bounded reducibilities among combinatorial problems. J. Comput. System Sci., 11:68\u201385, 1975.","journal-title":"J. Comput. System Sci."},{"key":"20_CR13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, New York, 1972."},{"issue":"2","key":"20_CR14","doi-asserted-by":"crossref","first-page":"199","DOI":"10.2307\/2272056","volume":"38","author":"R. E. Ladner","year":"1973","unstructured":"R.E. Ladner. Mitotic recursively enumerable sets. J. Symbolic Logic, 38(2):199\u2013211, 1973.","journal-title":"J. Symbolic Logic"},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"R. Ladner. On the structure of polynomial time reducibility. J. Assoc. Comput. Mach., 22:155\u2013171, 1975.","journal-title":"J. Assoc. Comput. Mach."},{"key":"20_CR16","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theor. Comput. Sci., 1:103\u2013123, 1975.","journal-title":"Theor. Comput. Sci."},{"key":"20_CR17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0022-0000(75)80016-X","volume":"10","author":"J. C. Owings","year":"1975","unstructured":"J.C. Owings. Splitting a context-sensitive set. J. Computer and System Sciences, 10:83\u201387, 1975.","journal-title":"J. Computer and System Sciences"},{"issue":"77","key":"20_CR18","doi-asserted-by":"crossref","first-page":"211","DOI":"10.2307\/1970214","volume":"2","author":"G. E. Sacks","year":"1963","unstructured":"G.E. Sacks. On degrees less than 0\u2032. Ann. of Math., 2(77):211\u2013231, 1963.","journal-title":"Ann. of Math."},{"key":"20_CR19","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/BF01704904","volume":"19","author":"U. Sch\u00f6ning","year":"1986","unstructured":"U. Sch\u00f6ning. Complete sets and closeness to complexity classes. Math. Systems Theory, 19:24\u201341, 1986.","journal-title":"Math. Systems Theory"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"S. Tang, B. Fu, and T. Liu. Exponential time and subexponential time sets. In Proc. Structure in Complexity Theory sixth annual conference, pages 230\u2013237, 1991.","DOI":"10.1109\/SCT.1991.160265"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"K. Wagner. More complicated questions about maxima and minima and some closures of NP. In 13th ICALP, Lecture Notes in Computer Science 226, pages 434\u2013443, 1986.","DOI":"10.1007\/3-540-16761-7_93"},{"key":"20_CR22","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"O. Watanabe. A comparison of polynomial time completeness notions. Theoret. Comput. Sci., 54:249\u2013265, 1987.","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR23","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"C.B. Wilson. Relativized circuit complexity. J. Computer and System Sciences, 31:169\u2013181, 1985.","journal-title":"J. Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:04:09Z","timestamp":1605647049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}