Relativizations of the P=? NP and other problems: Some developments in structural complexity theory

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

   Article  Google Scholar 

2. J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I, Springer-Verlag, 1988.

   Google Scholar 

3. J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity II, Springer-Verlag, 1990.

   Google Scholar 

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

   Article  Google Scholar 

5. L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets, SIAM J. Computing 6 (1977), 305–322.

   Article  Google Scholar 

6. R. Book. Some Observations on separating complexity classes, SIAM J. Computing 20 (1991), 246–258.

   Article  Google Scholar 

7. R. Book, T. Long, and A. Selman. Quantitative relativizations of complexity classes, SIAM J. Computing 13 (1984), 461–487.

   Article  Google Scholar 

8. R. Book, J. Lutz, and K. Wagner. On complexity classes and algorithmically random languages, STACS 92, Lecture Notes in Computer Sci., 577, Springer-Verlag (1992), 319–328.

   Google Scholar 

9. J.-Y. Cai. With proability one, a random oracle separates PSPACE from the polynomial-time hierarchy, J. Comput. Systems Sci. 38 (1989), 68–85.

   Article  Google Scholar 

10. A. Cobham. The intrinsic computational difficulty of functions, Prod. 1964 International Congress for Logic, Methodology and Philosophy of Science, North Holland (1964), 24–30.

    Google Scholar 

11. S. Cook. The complexity of theorem-proving procedures, Proc. 3rd ACM Symp. Theory of Computing (1971), 151–158.

    Google Scholar 

12. M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman & Co., 1979.

    Google Scholar 

13. R. Karp. Reducibility among combinatorial problems, in R. Miller and J. Thatcher (eds.), Complexity of Computer Computation, Plenum Press (1972), 85–104.

    Google Scholar 

14. R. Karp and R. Lipton. Turing machines that take advice, L'Enseignement Mathématique 28 2nd series (1982), 191–209.

    Google Scholar 

15. S. Kurtz. On the random oracle hypothesis, Info. and Control 57 (1983), 40–47.

    Article  Google Scholar 

16. L. Levin. Universal sequential search problems, Probl. Pered. Inform. IX (1973), 115–116. English translation in Probl. Information Transmission 9 (1973), 265–266.

    Google Scholar 

17. M. Li and P. Vitanyi. Kolmogorov complexity and its applications, in J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, vol. A, Elsevier Sci. Publishers (1990), 187–254.

    Google Scholar 

18. S. Mahaney. Sparse complete sets for NP: solution of a conjecture by Berman and Hartmanis, J. Comput. and Systems Sci. 25 (1982), 130–143.

    Article  Google Scholar 

19. P. Martin-Löf. On the definition of random sequences, Info. and Control 9 (1966), 602–619.

    Google Scholar 

20. P. Martin-Löf. Complexity oscillations in infinite binary sequences, Zeitschrift für Wahrscheinlichkeitstheory und Verwandte Gebiete 19 (1971), 225–230.

    Article  Google Scholar 

21. M. Ogiwara and A. Lozano. On one query self-reducible sets, Proc. 6th IEEE Conference on Structure in Complexity Theory (1991), 139–151.

    Google Scholar 

22. M. Ogiwara and O. Watanabe. On polynomial bounded truth-table reducibility of NP sets to sparse sets, SIAM J. Computing 20 (1991), 471–483.

    Article  Google Scholar 

23. H. Rogers. Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.

    Google Scholar 

24. B. Trakhtenbrot. A survey of Russian approaches to Perebor (brute-force search) algorithms, Annals History of Computing 6 (1984), 384–399.

    Google Scholar 

25. O. Watanabe, A comparison of polynomial-time completeness notions, Theoret. Comput. Sci. 54 (1987), 249–265.

    Article  Google Scholar 

26. A. Yao. Separating the polynomial-time hierarchy by oracles, Proc. 26th IEEE Symp. Foundations of Comput. Sci. (1985), 1–10.

    Google Scholar 

Download references