{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:09:44Z","timestamp":1778292584700,"version":"3.51.4"},"reference-count":19,"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\/bf01699457","type":"journal-article","created":{"date-parts":[[2005,5,15]],"date-time":"2005-05-15T07:15:04Z","timestamp":1116141304000},"page":"1-10","source":"Crossref","is-referenced-by-count":96,"title":["Bi-immune sets for complexity classes"],"prefix":"10.1007","volume":"18","author":[{"given":"Jos\u00e9 L.","family":"Balc\u00e1zar","sequence":"first","affiliation":[]},{"given":"Uwe","family":"Sch\u00f6ning","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01699457_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, Simplicity, relativizations, and nondeterminism,SIAM J. Comput. (1984), to appear.","DOI":"10.1137\/0214012"},{"key":"BF01699457_CR2","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 oracleA, P A \u2260 NP A \u2260 co-NP A with probability 1,SIAM J. Comput. 10 (1981), 96\u2013113.","journal-title":"SIAM J. Comput."},{"key":"BF01699457_CR3","doi-asserted-by":"crossref","unstructured":"L. Berman, On the structure of complete sets: almost everywhere complexity and infinitely often speedup,Proc. 17th IEEE Symp. Foundations of Computer Science, 1976, 76\u201380.","DOI":"10.1109\/SFCS.1976.22"},{"key":"BF01699457_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis, On isomorphism and density of NP and other complete sets,SIAM J. Comput. 6 (1977), 305\u2013322.","journal-title":"SIAM J. Comput."},{"key":"BF01699457_CR5","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. Syst. Sci. 17 (1978), 56\u201364.","journal-title":"J. Comput. Syst. Sci."},{"key":"BF01699457_CR6","doi-asserted-by":"crossref","unstructured":"P. Flajolet and J. M. Steyaert, On sets having only hard subsets,Automata, Languages, and Programming, Lecture Notes in Computer Science 14, Springer-Verlag, 1974, 446\u2013457.","DOI":"10.1007\/978-3-662-21545-6_34"},{"key":"BF01699457_CR7","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1051\/ita\/197408R100371","volume":"8","author":"P. Flajolet","year":"1974","unstructured":"P. Flajolet and J. M. Steyaert, Une g\u00e9n\u00e9ralisation de la notion d'ensemble immune,R.A.I.R.O.-Informatique Th\u00e9orique 8 (1974), 37\u201348.","journal-title":"R.A.I.R.O.-Informatique Th\u00e9orique"},{"key":"BF01699457_CR8","unstructured":"W. I. Gasarch and S. Homer, Relativizations comparing NP and exponential time, submitted for publication."},{"key":"BF01699457_CR9","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations,Proc. 24th IEEE Symp. Foundations of Computer Science (1983), 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"BF01699457_CR10","doi-asserted-by":"crossref","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":"BF01699457_CR11","doi-asserted-by":"crossref","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":"BF01699457_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, N. A. Lynch and A. L. Selman, A comparison of polynomial time reducibilities,Theoret. Comput. Sci. 1 (1975), 103\u2013123.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01699457_CR13","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. Assoc. Comput. Mach. 22 (1975), 341\u2013345.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01699457_CR14","unstructured":"A. R. Meyer and M. S. Paterson, With what frequency are apparently intractable problems difficult?, M.I.T. Technical Report TM-126, Feb. 1979."},{"key":"BF01699457_CR15","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 integers and their decision problems,Bull. Amer. Math. Soc. 50 (1944), 284\u2013316.","journal-title":"Bull. Amer. Math. Soc."},{"key":"BF01699457_CR16","unstructured":"M. O. Rabin, Degree of difficulty of computing a function and a partial ordering of recursive sets, Tech. Report 2, The Hebrew University, Jerusalem, 1960."},{"key":"BF01699457_CR17","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning and R. V. Book, Immunity,Automata, Languages, and Programming, Lecture Notes in Computer Science, Springer-Verlag, 1983, 653\u2013661.","DOI":"10.1007\/BFb0036945"},{"key":"BF01699457_CR18","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning and R. V. Book, Immunity, relativizations, and nondeterminism,SIAM J. Comput. 13 (1984), to appear.","DOI":"10.1137\/0213023"},{"key":"BF01699457_CR19","doi-asserted-by":"crossref","unstructured":"P. Young, Some structural properties of polynomial reducibilities and sets in NP,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 392\u2013401.","DOI":"10.1145\/800061.808770"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01699457.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01699457\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01699457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T10:17:58Z","timestamp":1586254678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01699457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,12]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,12]]}},"alternative-id":["BF01699457"],"URL":"https:\/\/doi.org\/10.1007\/bf01699457","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,12]]}}}