{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:35Z","timestamp":1759637855481,"version":"3.32.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1985,12,1]],"date-time":"1985-12-01T00:00:00Z","timestamp":502243200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1985,12]]},"DOI":"10.1007\/bf01699469","type":"journal-article","created":{"date-parts":[[2005,5,15]],"date-time":"2005-05-15T07:15:04Z","timestamp":1116141304000},"page":"189-205","source":"Crossref","is-referenced-by-count":14,"title":["Nonlevelable sets and immune sets in the accepting density hierarchy inNP"],"prefix":"10.1007","volume":"18","author":[{"given":"Ker-I","family":"Ko","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01699469_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L., Two theorems on random polynomial time,Proc. 19th IEEE Symp. on Foundations of Computer Science (1978), 75\u201383.","DOI":"10.1109\/SFCS.1978.37"},{"key":"BF01699469_CR2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(80)90027-4","volume":"12","author":"D. Angluin","year":"1980","unstructured":"Angluin, D., On counting problems and the polynomial-time hierarchy,Theoret. Comput. Sci. 12 (1980), 161\u2013173.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01699469_CR3","unstructured":"Balcazar, J. and D. Russo, Immunity and simplicity in relativizations of probabilistic complexity classes, preprint."},{"key":"BF01699469_CR4","doi-asserted-by":"crossref","unstructured":"Balcazar, J. and U. Sch\u00f6ning, Bi-immune sets for complexity classes,Math. Systems Theory, (to appear).","DOI":"10.1007\/BF01699457"},{"key":"BF01699469_CR5","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"Bennett C. H. and J. Gill, Relative to a random oracleA, P a \u2260NP A \u2260 coNP A with probability 1,SIAM. J. Comput. 10 (1981), 96\u2013113.","journal-title":"SIAM. J. Comput."},{"key":"BF01699469_CR6","doi-asserted-by":"crossref","unstructured":"Berman, L. On the structure of complete sets: almost everywhere complexity and infinitely often speedup,Proc. 17th IEEE Symp. on Foundation of Computer Science (1976) 76\u201380.","DOI":"10.1109\/SFCS.1976.22"},{"key":"BF01699469_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L. and J. Harmanis, On isomorphisms and density ofNP and other complete sets,SIAM J. Comput. 6 (1977), 305\u2013322.","journal-title":"SIAM J. Comput."},{"key":"BF01699469_CR8","doi-asserted-by":"crossref","first-page":"579","DOI":"10.2307\/2271984","volume":"38","author":"M. Blum","year":"1973","unstructured":"Blum M. and I. Marques, On complexity properties of recursively enumerable sets,J. Symbol. Logic 38 (1973), 579\u2013593.","journal-title":"J. Symbol. Logic"},{"key":"BF01699469_CR9","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S. Cook","year":"1973","unstructured":"Cook, S., A hierarchy for nondeterministic time complexity,J. Comput. System Sci. 7 (1973) 343\u2013353.","journal-title":"J. Comput. System Sci."},{"key":"BF01699469_CR10","doi-asserted-by":"crossref","unstructured":"Even, S., A. Selman and Y. Yacobi, Hard-core theorems for complexity classes,J. Assoc. Comput. Mach. (1985), to appear.","DOI":"10.1145\/2455.214111"},{"key":"BF01699469_CR11","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M. and D. Johnson,Computers and Intractability, W. H. Freeman, San Francisco, 1979."},{"key":"BF01699469_CR12","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J., Computational complexity of probabilistic Turing machines,SIAM J. Comput. 6 (1977), 675\u2013695.","journal-title":"SIAM J. Comput."},{"key":"BF01699469_CR13","doi-asserted-by":"crossref","unstructured":"Hartmanis, J., Generalized Kolmogorov complexity and the structure of feasible computations,Proc. 24th IEEE Symp. on Foundation of Computer Science (1983) 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"BF01699469_CR14","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(83)90003-8","volume":"24","author":"S. Homer","year":"1983","unstructured":"Homer, S. and W. Maass, Oracle dependent properties of the lattice ofNP sets,Theoret. Comput. Sci. 24 (1983), 279\u2013289.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01699469_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R. and R. Lipton, Some connections between nonuniform and uniform complexity classes,Proc. 12th ACM Symp. Theory of Comput. (1980), 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"BF01699469_CR16","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C. Kintala","year":"1980","unstructured":"Kintala, C. and P. Fischer, Refining nondeterminism in relativized polynomial time bounded computations,SIAM J. Comput. 9 (1980) 46\u201353.","journal-title":"SIAM J. Comput."},{"key":"BF01699469_CR17","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K. Ko","year":"1981","unstructured":"Ko, K. and D. Moore, Completeness, approximation and density,SIAM J. Comput. 10 (1981), 787\u2013796.","journal-title":"SIAM J. Comput."},{"key":"BF01699469_CR18","doi-asserted-by":"crossref","unstructured":"Ko, K. and U. Sch\u00f6ning, On circuit-size complexity and the low hierarchy inNP, SIAM J. Comput. (1985), 41\u201351.","DOI":"10.1137\/0214003"},{"key":"BF01699469_CR19","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1983","unstructured":"Lautemann, C., BPP and the polynomial hierarchy,Inform. Proc. Letters 17 (1983), 215\u2013217.","journal-title":"Inform. Proc. Letters"},{"key":"BF01699469_CR20","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321892.321895","volume":"22","author":"N. Lynch","year":"1975","unstructured":"Lynch, N., On reducibility to complex or sparse sets,J. Assoc. Comput. Mach. 22 (1975) 341\u2013345.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01699469_CR21","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1137\/0211026","volume":"11","author":"S. Moran","year":"1982","unstructured":"Moran, S., On the accepting density hierarchy inNP, SIAM J. Comput. 11 (1982) 344\u2013349.","journal-title":"NP, SIAM J. Comput."},{"key":"BF01699469_CR22","unstructured":"Orponen, P., A classification of complexity core lattices, preprint."},{"key":"BF01699469_CR23","doi-asserted-by":"crossref","unstructured":"Orponen, P., D. Russo and U. Sch\u00f6ning, Optimal approximations and polynomially levelable sets, SIAM J. Comput., to appear.","DOI":"10.1137\/0215027"},{"key":"BF01699469_CR24","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/BFb0030328","volume":"176","author":"P. Orponen","year":"1984","unstructured":"Orponen, P. and U. Sch\u00f6ning, The structure of polynomial complexity cores,Proc. 11th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 176 (1984), 452\u2013458.","journal-title":"Proc. 11th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science"},{"key":"BF01699469_CR25","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C. H. and M. Yanakakis, The complexity of facets,Proc. 14th ACM Symp. on Theory of Computing (1982), 255\u2013260.","DOI":"10.1145\/800070.802199"},{"key":"BF01699469_CR26","unstructured":"Rabin, M., Probabilistic algorithms, inAlgorithm and Complexity, J. F. Traub, ed., Academic Press (1976) 21\u201339."},{"key":"BF01699469_CR27","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"Rackoff, C., Relativized questions involving probabilistic algorithms,J. Assoc. Comput. Mach. 29 (1982), 261\u2013268.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01699469_CR28","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"Sch\u00f6ning, U., A low and a high hierarchy withinNP, J. Comput. System Sci. 27 (1983) 14\u201328.","journal-title":"NP, J. Comput. System Sci."},{"key":"BF01699469_CR29","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0213023","volume":"13","author":"U. Sch\u00f6ning","year":"1984","unstructured":"Sch\u00f6ning, U. and R. Book, Immunity, relativizations and nondeterminism,SIAM J. Comput. 13 (1984), 329\u2013337.","journal-title":"SIAM J. Comput."},{"key":"BF01699469_CR30","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Seiferas, J., M. Fischer and A. Meyer, Separating nondeterministic time complexity classes,J. Assoc. Comput. Mach. 25 (1978) 146\u2013167.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01699469_CR31","doi-asserted-by":"crossref","unstructured":"Sipser, M., A complexity theoretic approach to randomness,Proc. 15th ACM Symp. on Theory of Computing (1983) 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"BF01699469_CR32","doi-asserted-by":"crossref","first-page":"545","DOI":"10.2307\/2271876","volume":"42","author":"R. Soare","year":"1977","unstructured":"Soare, R., Computational complexity, speedable and levelable sets,J. Symbolic Logic, 42 (1977) 545\u2013563.","journal-title":"J. Symbolic Logic"},{"key":"BF01699469_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L., The polynomial time hierarchy.Theoret. Comput. Sci. 3 (1976) 1\u201322.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01699469_CR34","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"Valiant, L. G., The complexity of computing the permanent,Theoret. Comput. Sci. 8 (1979), 189\u2013201.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01699469_CR35","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"Valiant, L. G., The complexity of reliability and enumeration problems,SIAM J. Comput. 8 (1979), 410\u2013421.","journal-title":"SIAM J. Comput."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01699469.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01699469\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01699469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T08:05:23Z","timestamp":1735718723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01699469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,12]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,12]]}},"alternative-id":["BF01699469"],"URL":"https:\/\/doi.org\/10.1007\/bf01699469","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"type":"print","value":"0025-5661"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[1985,12]]}}}