Controlled relativizations of P and NP

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

   Google Scholar 

2. 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 

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

   Google Scholar 

4. Book, R., Long, T. and Selman, A., Qualitative relativizations of complexity classes, in preparation.

   Google Scholar 

5. Book, R., Long, T. and Selman, A., Quantitative relativizations of complexity classes, submitted for publication.

   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. Breidbart, S., Splitting recursive sets. J. Comput. Syst. Sci., 17(1978), 56–64.

   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. Ladner, R., Lynch, N. and Selman, A., A comparison of polynomial-time reducibilities. Theoret. Comput. Sci., 1(1975), 103–123.

    Google Scholar 

11. Long, T., Relativizing nondeterministic time, unpublished manuscript, 1981.

    Google Scholar 

12. Long, T., Strong nondeterministic polynomial-time reducibilities. Theoret. Comput. Sci., 21(1982), 1–25.

    Google Scholar 

13. Schöning, U., Relativization and infinite subsets of NP sets, unpublished manuscript, 1982.

    Google Scholar 

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

    Google Scholar 

Download references