Oracles versus proof techniques that do not relativize | SpringerLink
Skip to main content
Springer Nature Link
Log in

Oracles versus proof techniques that do not relativize

  • Conference paper
  • First Online:
Algorithms (SIGAL 1990)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 450))

Included in the following conference series:

Abstract

Oracle constructions have long been used to provide evidence that certain questions in complexity theory cannot be resolved using the usual techniques of simulation and diagonalization. However, the existence of nonrelativizing proof techniques seems to call this practice into question. This paper reviews the status of nonrelativizing proof techniques, and argues that many oracle constructions still yield valuable information about problems in complexity theory.

Supported in part by National Science Foundation Grants CCR-8810467 and CCR-9000045 and by a grant from the International Information Science Foundation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. D. Angluin, 1980 On relativizing auxiliary pushdown machines, Math. Systems Theory 13, 283–299.

    Google Scholar 

  2. E. Allender, R. Beigel, U. Hertrampf, and S. Homer, 1990 A note on the almost-everywhere hierarchy for nondeterministic time, Proc. 7th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 415, pp. 1–11.

    Google Scholar 

  3. E. Allender and V. Gore, On strong separations from AC 0, submitted.

    Google Scholar 

  4. E. Allender and K. W. Wagner, 1990 Counting hierarchies: polynomial time and constant depth circuits, guest authors of The Structural Complexity Column (ed. Juris Hartmanis), EATCS Bulletin 40, pp. 182–194.

    Google Scholar 

  5. E. Allender and C. Wilson, Width-bounded reducibility and binary search over complexity classes, Proc. 5th Annual IEEE Structure in Complexity Theory Conference, 1990.

    Google Scholar 

  6. L. Babai and L. Fortnow, A characterization of P by straight line programs of polynomials, with applications to interactive proofs and Toda's theorem, Technical Report 90-02, University of Chicago.

    Google Scholar 

  7. L. Babai, L. Fortnow, and C. Lund, Non-deterministic exponential time has two-prover interactive protocols, manuscript.

    Google Scholar 

  8. T. Baker, J. Gill, and R. Solovay, 1975 Relativizations of the P=?NP question, SIAM J. Comput. 4, 431–442.

    Article  Google Scholar 

  9. J. Buss, A theory of oracle machines, Proc. 2nd IEEE Structure in Complexity Theory Conference, pp. 175–181.

    Google Scholar 

  10. J. Buss, 1988 Relativized alternation and space-bounded computation, J. Comput. and System Sci. 36, 351–378.

    Google Scholar 

  11. S. Cook, The complexity of theorem proving procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158.

    Google Scholar 

  12. R. Downey, W. Gasarch, S. Homer, and M. Moses, On honest polynomial reductions, relativizations, and P=NP, Proc. 4th IEEE Structure in Complexity Theory Conference, pp. 196–207.

    Google Scholar 

  13. L. Fortnow and M. Sipser, 1988 Are there interactive proofs for co-NP languages? Information Processing Letters 28, 249–251.

    Article  Google Scholar 

  14. M. Furst, J. Saxe, M. Sipser, 1984 Parti, circuits, and the polynomial-time hierarchy, Mathematical Systems Theory 17, 13–27.

    Article  Google Scholar 

  15. L. Fortnow, J. Rompel, and M. Sipser, On the power of multi-prover interactive protocols, Proc. 3rd IEEE Structure in Complexity Theory Conference, pp. 156–161.

    Google Scholar 

  16. W. Gasarch, 1987 Oracles for deterministic versus alternating classes, SIAM J. Comput. 16, 613–627.

    Google Scholar 

  17. J. Håstad, Almost optimal lower bounds for small depth circuits, Proc. 18th ACM Symposium on Theory of Computing, pp. 6–20.

    Google Scholar 

  18. J. Hartmanis, 1985 Solvable problems with conflicting relativizations, EATCS Bulletin 27, pp. 40–49.

    Google Scholar 

  19. J. Hartmanis, 1988 New developments in structural complexity theory, Proc. 15th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 317, pp. 271–286.

    Google Scholar 

  20. J. Hartmanis, 1988 Some observations about relativizations of space bounded computations, the Structural Complexity Column, EATCS Bulletin 35, pp. 82–92.

    Google Scholar 

  21. S. Homer and A. Selman, Oracles for structural properties: the isomorphism problem and public-key cryptography, Proc. 4th IEEE Structure in Complexity Theory Conference, pp. 3–14.

    Google Scholar 

  22. R. Impagliazzo, Proofs that relativize, and proofs that do not, manuscript.

    Google Scholar 

  23. R. Impagliazzo and S. Rudich, Limits on the provable consequences of one-way permutations, Proc. 21st Annual ACM Symposium on Theory of Computing, pp. 44–61.

    Google Scholar 

  24. B. Kirsig and K.-J. Lange, 1987 Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE[log n] ≠ NSPACE[log n], Information Processing Letters 25, 13–15.

    Google Scholar 

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

    Google Scholar 

  26. R. Ladner and N. Lynch, 1976 Relativization of questions about log space computability, Math. Systems Theory 10, 19–32.

    Google Scholar 

  27. N. Lynch, 1978 Log space machines with multiple oracle tapes, Theoretical Computer Science 6, 25–39.

    Google Scholar 

  28. S. Moran, 1981 Some results on relativized deterministic and nondeterministic time hierarchies, Journal Comput. System Sci. 22, 1–8.

    Google Scholar 

  29. P. Orponen, 1983 Complexity classes of alternating machines with oracles, Proc. 10th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 154, pp. 573–584.

    Google Scholar 

  30. W. Paul, N. Pippenger, E. Szemerédi, and W. Trotter, On determinism versus non-determinism and related problems, Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, pp. 429–438.

    Google Scholar 

  31. C. Rackoff and J. Seiferas, 1981 Limitations on separating nondeterministic complexity classes, SIAM J. Comput. 10, 742–745.

    Google Scholar 

  32. Walter Ruzzo, Janos Simon, and M. Tompa, 1984 Space-bounded hierarchies and probabilistic computation, J. Comput. and System Sci. 28, 216–230.

    Google Scholar 

  33. W. Savitch, 1983 A note on relativized log space, Math. Systems Theory 16, 229–235.

    Google Scholar 

  34. A. Shamir, IP = PSPACE, manuscript.

    Google Scholar 

  35. I. Simon, On some subrecursive reducibilities, Ph.D. Dissertation, Stanford University.

    Google Scholar 

  36. M. Sipser, Borel sets and circuit complexity, Proc. 15th ACM Symposium on Theory of Computing, pp. 61–69.

    Google Scholar 

  37. S. Toda, On the computational power of PP and ⊕P, Proc. 30th IEEE Symposium on Foundations of Computer Science, pp. 514–519.

    Google Scholar 

  38. J. Torán, 1989, A combinatorial technique for separating counting complexity classes, Proc. 16th ICALP, Lecture Notes in Computer Science 372, pp. 732–744.

    Google Scholar 

  39. C. B. Wilson, 1987 Relativized NC, Math. Systems Theory 20, 13–29.

    Google Scholar 

  40. C. B. Wilson, 1988 A measure of relativized space which is faithful with respect to depth, J. Comput. and System Sciences 36, 303–312.

    Google Scholar 

  41. A. C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th IEEE Symposium on Foundations of Computer Science, pp. 1–10.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ

    Eric Allender

Authors
  1. Eric Allender
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Tetsuo Asano Toshihide Ibaraki Hiroshi Imai Takao Nishizeki

Rights and permissions

Reprints and permissions

Copyright information

© 1990 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Allender, E. (1990). Oracles versus proof techniques that do not relativize. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_54

Download citation

  • DOI: https://doi.org/10.1007/3-540-52921-7_54

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-52921-7

  • Online ISBN: 978-3-540-47177-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation