Structural complexity theory: Recent surprises

1. L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Technical Report 90-03, Department of Computer Science, University of Chicago, March 1990.

   Google Scholar 

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

   Article  Google Scholar 

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

   Article  Google Scholar 

4. L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets. SIAM Journal on Computing, 6:305–322, June 1977.

   Article  Google Scholar 

5. J. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. In ACM Symposium on Theory of Computing, pages 21–29, 1986.

   Google Scholar 

6. J. Cai. Probability one separation of the Boolean Hierarchy. In 4th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag Lecture Notes in Computer Science # 247, pages 148–158, 1987.

   Google Scholar 

7. A. Condon. Computational models of games. Technical Report 87-04-04, Department of Computer Science, University of Washington, 1987.

   Google Scholar 

8. L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28(5):249–251, August 1988.

   Article  Google Scholar 

9. J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675–695, December 1977.

   Article  Google Scholar 

10. O. Goldreich, S. Micali, and A. Widgerson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 174–187, 1986.

    Google Scholar 

11. S. Goldwasser. Interactive proof systems. In Computational Complexity Theory, Proceedings of Symposia in Applied Mathematics, Volume 38, pages 108–128. American Mathematical Society, 1989.

    Google Scholar 

12. S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In ACM Symposium on Theory of Computing, pages 59–68, 1986.

    Google Scholar 

13. J. Hartmanis. Solvable problems with conflicting relativizations. Bulletin of the European Association for Theoretical Computer Science, 27:40–49, Oct 1985.

    Google Scholar 

14. J. E. Hopcroft. Turing machines. Scientific American, pages 86–98, May 1984.

    Google Scholar 

15. J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263–1282, December 1988.

    Article  Google Scholar 

16. R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In ACM Symposium on Theory of Computing, pages 302–309, 1980.

    Google Scholar 

17. S. A. Kurtz, S. R. Mahaney, and J. S. Royer. The isomorphism conjecture fails relative to a random oracle. In ACM Symposium on Theory of Computing, pages 157–166, 1989.

    Google Scholar 

18. K. Ko. Relativized polynomial time hierarchies having exactly k levels. In ACM Symposium on Theory of Computing, pages 245–253, 1988.

    Google Scholar 

19. S. A. Kurtz. On the random oracle hypothesis. In ACM Symposium on Theory of Computing, pages 224–230, 1982.

    Google Scholar 

20. C. Lund, L. Fortnow, H. Karloff, and N. Nisan. The polynomial-time hierarchy has interactive proofs. Unpublished manuscript, 1989.

    Google Scholar 

21. S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25(2):130–143, 1982.

    Article  Google Scholar 

22. C. H. Papadimitriou. Games against nature. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 446–450, 1983.

    Google Scholar 

23. A. Shamir. IP = PSPACE. Unpublished manuscript, 1989.

    Google Scholar 

24. A. C. Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 1–10, 1985.

    Google Scholar 

Download references