Immunity

1. Baker, T., Gill, J. and Solovay, R., Relativizations of the P=? NP question. SIAM J. Computing, 4(1975), 431–442.

   Google Scholar 

2. Balcázar, J., Simplicity for relativized complexity classes, submitted for publication.

   Google Scholar 

3. Bennett, C. and Gill, J., Relative to a random oracle A, p^A≠ NP^A ≠ co-NP^A with probability 1. SIAM J. Computing, 10(1981), 96–113.

   Google Scholar 

4. Book, R., Bounded query machines: on NP and PSPACE. Theoret. Comput. Sci., 15(1981), 27–39.

   Google Scholar 

5. Book, R., Long, T. and Selman, A., Controlled relativizations of P and NP. Theoret. Comput. Sci., Lecture Notes in Computer Science, 145(1983), 85–90.

   Google Scholar 

6. Book, R., Wilson, C. and Xu Mei-rui, Relativizing time, space, and time space. SIAM J. Computing, 11(1982), 571–581.

   Google Scholar 

7. Book, R. and Wrathall, C., Bounded query machines: on NP and NPQUERY. Theoret. Comput. Sci., 15(1981), 41–50.

   Google Scholar 

8. Flajolet, P. and Steyaert, J., On sets having only hard subsets. 2nd International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 14(1974), 446–457. Also, Une généralization de la notion d'ensemble immune, R.A.I.R.O. Informatique Théorique, 8(1974), 37–48.

   Google Scholar 

9. Homer, S. and Maass, W., Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci., to appear.

   Google Scholar 

10. Hopcroft, J. and Ullman, J., Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

    Google Scholar 

11. Kintala, C.M.R., Computations with a Restricted Number of Nondeter-ministic Steps. Ph.D. dissertation, Pennsylvania State University, 1977.

    Google Scholar 

12. Kintala, C.M.R. and Fischer, P., Refining nondeterminism in relativized polynomial time-bounded computations. SIAM J. Computing, 9(1980), 46–53.

    Google Scholar 

13. Ko, K and Moore, D., Completeness, approximation, and density. SIAM J. Computing, 10(1981), 787–796.

    Google Scholar 

14. Long, T., Relativizing nondeterministic time. Unpublished manuscript, 1981.

    Google Scholar 

15. Schöning, U., A low and a high hierarchy within NP. J. Comput. Syst. Sci., (1983), to appear.

    Google Scholar 

16. Schöning, U., Relativization and infinite subsets of NP sets. Unpublished manuscript, 1982.

    Google Scholar 

17. Schöning, U., Bi-immune sets for complexity classes, in preparation.

    Google Scholar 

18. Selman, A., Xu Mei-rui and Book, R., Positive relativizations of complexity classes. SIAM J. Computing, 12(1983), to appear.

    Google Scholar 

19. Xu Mei-rui, Doner, J. and Book, R., Refining nondeterminism in relativized complexity classes. J. Assoc. Comput. Mach., 30(1983), to appear.

    Google Scholar 

Download references