{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:50:52Z","timestamp":1725663052734},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_63","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:51:32Z","timestamp":1330195892000},"page":"136-145","source":"Crossref","is-referenced-by-count":6,"title":["Containment, separation, complete sets, and immunity of complexity classes"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaacov","family":"Yesha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"L. Berman, On the structure of complete sets: Almost everywhere complexity and infinitely often speedup, Proc. 17th IEEE FOCS (1977), 76\u201380.","DOI":"10.1109\/SFCS.1976.22"},{"key":"15_CR2","unstructured":"L. Berman, Polynomial reducibility and complete sets, Ph.D. thesis, Cornell University, May 1977."},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. Book","year":"1974","unstructured":"R. Book, Tally languages and complexity classes, Information and Control 26 (1974), pp. 186\u2013193.","journal-title":"Information and Control"},{"issue":"6","key":"15_CR4","first-page":"606","volume":"4","author":"R. Book","year":"1970","unstructured":"R. Book, S. Greibach, and B. Wegbreit, Time-and tape-bound Turing acceptors and AFL's, JCSS 4,6 (Dec. 1970) pp. 606\u2013621.","journal-title":"JCSS"},{"key":"15_CR5","unstructured":"R. Rook and U. Schoning, Immunity, relativization and nondeterminism, to appear in SIAM J. Computing."},{"issue":"4","key":"15_CR6","first-page":"343","volume":"7","author":"S. Cook","year":"1973","unstructured":"S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7,4 (1973) pp. 343\u2013353.","journal-title":"JCSS"},{"key":"15_CR7","unstructured":"S. Homer, On simple and creative sets in NP. TR# 84\/002, Department of Computer Science, Boston University."},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(83)90024-8","volume":"2","author":"J. Hartmanis","year":"1983","unstructured":"J. Hartmanis, On sparse sets in NP-P, Inf. Proc. Let. 2 (1983) pp. 55\u201360.","journal-title":"Inf. Proc. Let."},{"key":"15_CR9","unstructured":"J. Hartmanis and N. Immerman, On complete sets in NP \u2229 CoNP, 12th ICALP, Napflion, Greece. 1985."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, N. Immerman, and V. Sewelson, On sparse sets in NP-P. EXPTIME vs. NEXPTIME, Proc. 15th ACM STOC (April 1983), pp. 382\u2013391.","DOI":"10.1145\/800061.808769"},{"key":"15_CR11","unstructured":"J. Hartmanis, P. Lewis, and R. Stearns, Classification of computations by time and memory requirements, Proc. IFIP Congress 65, Spartan, NY. (1965). pp. 31\u201335."},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"J. Hartmanis and Y. Yesha, Computation times of NP sets of different densities, 10th ICALP, Spain (1983). Also, Special Issue of Theor. Comp. Sci. 34 (1984) pp. 17\u201332.","journal-title":"Also, Special Issue of Theor. Comp. Sci."},{"key":"15_CR13","unstructured":"J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley (1979)."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"W. Kowalozyk, Some connections between presentability of complexity classes and the power of formal systems of reasoning, Proc. MFCS'84 pp. 364\u2013369.","DOI":"10.1007\/BFb0030318"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321892.321895","volume":"22","author":"N. Lynch","year":"1975","unstructured":"N. Lynch, On reducibility to complex or sparse sets, J. ACM, 22, (1975) pp. 341\u2013345.","journal-title":"J. ACM"},{"key":"15_CR16","unstructured":"N. Lynch, M. Fischer, and A. Meyer, Relativization of the theory of computational complexity, Trans. AMS."},{"key":"15_CR17","unstructured":"M. Li, Lower bounds in computational complexity, Ph.D. Thesis, Cornell University (1985)."},{"key":"15_CR18","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","volume":"18","author":"L. Landweber","year":"1982","unstructured":"L. Landweber, R. Lipton, and E. Robertson, On the structure of sets in NP and other complexity classes, Theor. Comp. Sci., 18(1982) pp. 95\u2013103.","journal-title":"Theor. Comp. Sci."},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"R. Ladner, N. Lynch, and A. Selman, Comparison of polynomial time reducibilities, Proc. STOC (1974) pp. 110\u2013121.","DOI":"10.1145\/800119.803891"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"S. Mahaney, Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, Proc. IEEE FOCS, 1980, pp. 54\u201360.","DOI":"10.1109\/SFCS.1980.40"},{"key":"15_CR21","unstructured":"P. Orponen and U. Schoning, On the density of polynomial complexity cores, Proc. Math. Found. Comp. Sci. \u2014 84, Lecture Notes in Computer Science, to appear."},{"key":"15_CR22","unstructured":"C. W. Rackoff and J. I. Seiferas, Limitations on separating nondeterministic complexity classes, 10, 4 SIAM Comp. (1981), pp. 742\u2013745."},{"issue":"1","key":"15_CR23","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"J. Seiferas, M. Fischer, and A. Meyer, Separating nondeterministic time classes, JACM, 25, 1, (1978) pp. 146\u2013167.","journal-title":"JACM"},{"key":"15_CR24","first-page":"523","volume-title":"On relativization and the existence of complete sets, 9th ICALP, Lecture Notes in Computer Science","author":"M. Sipser","year":"1982","unstructured":"M. Sipser, On relativization and the existence of complete sets, 9th ICALP, Lecture Notes in Computer Science, Springer Verlag, Berlin (1982) pp. 523\u2013531."},{"key":"15_CR25","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1137\/0212027","volume":"12","author":"Y. Yesha","year":"1983","unstructured":"Y. Yesha, On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM J. Comp. 12,3 (1983).","journal-title":"SIAM J. Comp."},{"key":"15_CR26","unstructured":"S. Zak, A Turing machine hierarchy, to appear in Theor. Comp. Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_63.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:52Z","timestamp":1605643852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}