{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T21:10:25Z","timestamp":1736284225202,"version":"3.32.0"},"publisher-location":"Boston","reference-count":26,"publisher":"Kluwer Academic Publishers","isbn-type":[{"type":"print","value":"1402081405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/1-4020-8141-3_9","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T15:15:11Z","timestamp":1140534911000},"page":"81-96","source":"Crossref","is-referenced-by-count":0,"title":["Resource Bounded Immunity and Simplicity"],"prefix":"10.1007","author":[{"given":"Toshio","family":"Suzuki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyuki","family":"Yamakami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1137\/0214012","volume":"14","author":"J. L. Balc\u00e1zar","year":"1985","unstructured":"J. L. Balc\u00e1zar, Simplicity, relativizations, and nondeterminism, SIAM J. Comput. 14 (1985) 148\u2013157.","journal-title":"SIAM J. Comput."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. L. Balc\u00e1zar","year":"1985","unstructured":"J. L. Balc\u00e1zar and U. Sch\u00f6ning, Bi-immune sets for complexity classes, Math. Systems Theory 18 (1985) 1\u201310.","journal-title":"Math. Systems Theory"},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"C. H. Bennett and J. Gill, Relative to a random oracle A, P A \u2260 NP A \u2260 co-NP A with probability 1, SIAMJ. Comput. 10 (1981) 96\u2013113.","journal-title":"SIAMJ. Comput."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0304-3975(92)90232-5","volume":"102","author":"D. Bruschi","year":"1992","unstructured":"D. Bruschi, Strong separations of the polynomial hierarchy with oracles: constructive separations by immune and simple sets, Theoret. Comput. Sci. 102 (1992) 215\u2013252.","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"P. Flajolet and J. M. Steyaert, On sets having only hard subsets, in Proc. 2nd Intern. Colloq. on Automata, Languages, and Programming, LNCS, Springer, Vol.14, pp.446\u2013457, 1974.","DOI":"10.1007\/3-540-06841-4_81"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, M. Li, and Y. Yesha, Containment, separation, complete sets, and immunity of complexity classes, in: Proc. 13th Intern. Colloq. on Automata, Languages, and Programming, LNCS, Springer, Vol.226, pp. 136\u2013145, 1986.","DOI":"10.1007\/3-540-16761-7_63"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90144-1","volume":"47","author":"S. Homer","year":"1986","unstructured":"S. Homer, On simple and creative sets in NP, Theoret. Comput. Sci., 47 (1986) 169\u2013180.","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0304-3975(83)90003-8","volume":"24","author":"S. Homer","year":"1983","unstructured":"S. Homer and W. Maass, Oracle-dependent properties of the lattice of NP sets, Theoret. Comput. Sci., 24 (1983) 279\u2013289.","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(85)90140-9","volume":"39","author":"D. Joseph","year":"1985","unstructured":"D. Joseph and P. Young, Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, Theoret. Comput. Sci. 39 (1985) 225\u2013237.","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF01699469","volume":"18","author":"K. Ko","year":"1985","unstructured":"K. Ko, Nonlevelable sets and immune sets in the accepting density hierarchy in NP, Math. Systems Theory 18 (1985) 189\u2013205.","journal-title":"Math. Systems Theory"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K. Ko","year":"1981","unstructured":"K. Ko and D. Moore, Completeness, approximation and density, SIAM J. Comput. 10 (1981) 787\u2013796.","journal-title":"SIAM J. Comput."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"A. Meyer and L. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential time, in Proc. 13th IEEE Symp. on Switching and Automata theory, pp.125\u2013129, 1973.","DOI":"10.1109\/SWAT.1972.29"},{"key":"9_CR13","doi-asserted-by":"publisher","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, Journal of ACM, 22 (1975) 341\u2013345.","journal-title":"Journal of ACM"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(86)90140-4","volume":"47","author":"P. Orponen","year":"1986","unstructured":"P. Orponen, A classification of complexity core lattices, Theoret. Comput. Sci., 47 (1986) 121\u2013130.","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/174644.174648","volume":"41","author":"P. Orponen","year":"1994","unstructured":"P. Orponen, K. Ko, U. Sch\u00f6ning, and O. Watanabe, Instance complexity, Journal of ACM, 41 (1994) 96\u2013121.","journal-title":"Journal of ACM"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/0215027","volume":"15","author":"P. Orponen","year":"1986","unstructured":"P. Orponen, D. Russo, and U. Sch\u00f6ning, Optimal approximations and polynomially levelable sets, SIAM J. Comput., 15 (1986) 399\u2013408.","journal-title":"SIAM J. Comput."},{"key":"9_CR17","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E. L. Post","year":"1944","unstructured":"E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Am. Math. Soc. 50 (1944) 284\u2013316.","journal-title":"Bull. Am. Math. Soc."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"D. A. Russo, Optimal approximations of complete sets, in Proc. 1st Annual Conference on Structure in Complexity Theory, LNCS, Springer, Vol.223, pp.311\u2013324, 1986.","DOI":"10.1007\/3-540-16486-3_107"},{"key":"9_CR19","unstructured":"M. Schaefer and S. Fenner, Simplicity and strong reductions, manuscript, 2000."},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman, P-selective sets, tally languages and the behavior of polynomial time reducibilities on NP, Math. Systems Theory, 13 (1979) 55\u201365.","journal-title":"Math. Systems Theory"},{"key":"9_CR21","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02088009","volume":"21","author":"L. Torenvliet","year":"1988","unstructured":"L. Torenvliet, A second step toward the strong polynomial-time hierarchy, Math. Systems Theory 21 (1988) 99\u2013123.","journal-title":"Math. Systems Theory"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90020-5","volume":"80","author":"L. Torenvliet","year":"1989","unstructured":"L. Torenvliet and P. van Emde Boas, Simplicity, immunity, relativization and nondeterminism, Inform. and Comput. 80 (1989) 1\u201317.","journal-title":"Inform. and Comput."},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1002\/malq.19570031202","volume":"3","author":"V. A. Uspenskii","year":"1957","unstructured":"V. A. Uspenskii, Some remarks on r.e. sets, Zeit. Math. Log. Grund. Math. 3 (1957) 157\u2013170.","journal-title":"Zeit. Math. Log. Grund. Math."},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"N. K. Vereshchagin, Relationships between NP-sets, CoNP-sets and P-sets relative to random oracles, in Proc. 8th IEEE Conf. on Structure in Complexity Theory, pp.132\u2013138, 1993.","DOI":"10.1109\/SCT.1993.336533"},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01374524","volume":"25","author":"T. Yamakami","year":"1992","unstructured":"T. Yamakami, Structural properties for feasibly computable classes of type two, Math. Systems Theory 25 (1992) 177\u2013201.","journal-title":"Math. Systems Theory"},{"key":"9_CR26","unstructured":"T. Yamakami, Simplicity, unpublished manuscript, University of Toronto, 1995."}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T20:45:26Z","timestamp":1736282726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["1402081405"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_9","relation":{},"subject":[]}}