Balcázar, José L.; Schöning, Uwe Bi-immune sets for complexity classes. (English) Zbl 0572.68035 Math. Syst. Theory 18, 1-10 (1985). An infinite and co-infinite set A is bi-immune for a class of sets C if neither A nor its complement have an infinite subset in C. Various characterizations of this notion are given in terms of splitting, a.e. complexity, and approximation algorithms. Also a stronger version of bi- immunity is introduced and it is shown how both notions relate to density and other properties of sets in the complexity class EXPTIME. Cited in 44 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68Q05 Models of computation (Turing machines, etc.) (MSC2010) Keywords:immune sets; almost everywhere complexity; splitting; approximation algorithms; density; EXPTIME × Cite Format Result Cite Review PDF Full Text: DOI References: [1] J. Balcázar, Simplicity, relativizations, and nondeterminism,SIAM J. Comput. (1984), to appear. [2] C. H. Bennett and J. Gill, Relative to a random oracleA, P A NP A co-NP A with probability 1,SIAM J. Comput. 10 (1981), 96–113. · Zbl 0454.68030 · doi:10.1137/0210008 [3] 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–80. [4] L. Berman and J. Hartmanis, On isomorphism and density of NP and other complete sets,SIAM J. Comput. 6 (1977), 305–322. · Zbl 0356.68059 · doi:10.1137/0206023 [5] S. Breidbart, On splitting recursive sets,J. Comput. Syst. Sci. 17 (1978), 56–64. · Zbl 0392.03028 · doi:10.1016/0022-0000(78)90034-X [6] 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–457. [7] P. Flajolet and J. M. Steyaert, Une généralisation de la notion d’ensemble immune,R.A.I.R.O.-Informatique Théorique 8 (1974), 37–48. · Zbl 0283.02034 [8] W. I. Gasarch and S. Homer, Relativizations comparing NP and exponential time, submitted for publication. · Zbl 0562.68034 [9] J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations,Proc. 24th IEEE Symp. Foundations of Computer Science (1983), 439–445. [10] S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets,Theoret. Comput. Sci. 24 (1983), 279–289. · Zbl 0543.03024 · doi:10.1016/0304-3975(83)90003-8 [11] K. Ko and D. Moore, Completeness, approximation and density,SIAM J. Comput. 10 (1981), 787–796. · Zbl 0468.68051 · doi:10.1137/0210061 [12] R. E. Ladner, N. A. Lynch and A. L. Selman, A comparison of polynomial time reducibilities,Theoret. Comput. Sci. 1 (1975), 103–123. · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X [13] N. Lynch, On reducibility to complex or sparse sets,J. Assoc. Comput. Mach. 22 (1975), 341–345. · Zbl 0311.68037 [14] A. R. Meyer and M. S. Paterson, With what frequency are apparently intractable problems difficult?, M.I.T. Technical Report TM-126, Feb. 1979. [15] E. L. Post, Recursively enumerable sets of integers and their decision problems,Bull. Amer. Math. Soc. 50 (1944), 284–316. · Zbl 0063.06328 · doi:10.1090/S0002-9904-1944-08111-1 [16] 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. [17] U. Schöning and R. V. Book, Immunity,Automata, Languages, and Programming, Lecture Notes in Computer Science, Springer-Verlag, 1983, 653–661. [18] U. Schöning and R. V. Book, Immunity, relativizations, and nondeterminism,SIAM J. Comput. 13 (1984), to appear. [19] P. Young, Some structural properties of polynomial reducibilities and sets in NP,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 392–401. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.