[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On closure properties of bounded two-sided error complexity classes

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

We show that if a complexity classC is closed downward under polynomial-time majority truth-table reductions (≤ pmtt ), then practically every other “polynomial” closure property it enjoys is inherited by the corresponding bounded two-sided error class BP[C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practically every closure property of NP. Our main lemma shows that, for any relativizable classD which meets two fairly transparent technical conditions, we haveC BP[C] \( \subseteq \)BP[D C]. Among our applications, we simplify the proof by Toda [Tol], [To2] that the polynomial hierarchy PH is contained in BP[⊕P]. We also show that relative to a random oracleR, PHR is properly contained in ⊕PR.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Adleman and K. Manders. Reducibility, randomness, and intractability.Proceedings of the 9th Annual ACM Symposium on the Theory of Computing, pages 151–163, 1977.

  2. E. Allender and K. Wagner. Counting hierarchies: polynomial time and constant depth circuits.EATCS Bulletin, 40:182–194, February 1990.

    Google Scholar 

  3. L. Babai. Trading group theory for randomness.Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, pages 421–429, 1985.

  4. L. Babai. Random oracles separate PSPACE from the polynomial-time hierarchy.Information Processing Letters, 26:51–53, 1987.

    Google Scholar 

  5. C. Bennett and J. Gill. Relative to a random oracle,A, P A ≠ NPA ≠ coNPA with probability 1.SIAM Journal on Computing, 10:96–113, 1981.

    Google Scholar 

  6. L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes.Journal of Computer and System Sciences, 36:254–276, 1988.

    Google Scholar 

  7. J. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy.Journal of Computer and System Sciences, 38:68–85, 1989.

    Google Scholar 

  8. P. Chew and M. Machtey. A note on structure and looking-back applied to the relative complexity of computable functions.Journal of Computer and System Sciences, 22:53–59, 1981.

    Google Scholar 

  9. P. Hinman and S. Zachos. Probabilistic machines, oracles, and quantifiers.Proceedings, Oberwohlfach Recursion-Theory Week, pages 159–192. Lecture Notes in Mathematics, volume 1141. Springer-Verlag, Berlin, 1984.

    Google Scholar 

  10. A. Klapper. Generalized lowness and highness and probabilistic complexity classes.Mathematical Systems Theory, 22:37–45, 1990.

    Google Scholar 

  11. K. Ko. Some observations on the probabilistic algorithms and NP-hard problems.Information Processing Letters, 14:39–43, 1982.

    Google Scholar 

  12. C. Lautemann. BPP and the polynomial hierarchy.Information Processing Letters, 17:215–217, 1983.

    Google Scholar 

  13. T. Long. Strong nondeterministic polynomial reducibilities.Theoretical Computer Science, 21:1–25, 1982.

    Google Scholar 

  14. N. Nisan and A. Wigderson. Hardness vs. randomness.Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 2–11, 1988.

  15. C. H. Papadimitriou and S. Zachos. Two remarks on the power of counting.Proceedings of the 6th GI Conference on Theoretical Computer Science, pages 269–276. Lecture Notes in Computer Science, volume 145. Springer-Verlag, Berlin, 1983.

    Google Scholar 

  16. M. Santha. Relativized Arthur-Merlin vs. Merlin-Arthur games.Proceedings, 7th Conference on Foundations of Software Theory and Theoretical Computer Science, pages 437–442. Lecture Notes in Computer Science, volume 287. Springer-Verlag, Berlin, 1987.

    Google Scholar 

  17. U. Schöning.Complexity and Structure. Lecture Notes in Computer Science, volume 211. Springer-Verlag, Berlin, 1985.

    Google Scholar 

  18. U. Scheming. Graph isomorphism is in the low hierarchy.Journal of Computer and System Sciences, 37:312–323, 1988.

    Google Scholar 

  19. U. Schöning. Probabilistic complexity classes and lowness.Journal of Computer and System Sciences, 39:84–100, 1989.

    Google Scholar 

  20. U. Schöning. The power of counting. In A. Selman, editor,Complexity Theory Retrospective, pages 204–223. Springer-Verlag, New York, 1990.

    Google Scholar 

  21. A. Selman. Reductions on NP and p-selective sets.Theoretical Computer Science, 19:287–304, 1982.

    Google Scholar 

  22. J. Tarui. Randomized polynomials, threshold circuits, and the polynomial hierarchy.Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science, pages 238–250. Lecture Notes in Computer Science, volume 480. Springer-Verlag, Berlin, 1991.

    Google Scholar 

  23. J. Tarui. Probabilistic polynomials, AC0 functions, and the polynomial-time hierarchy.Theoretical Computer Science, 113:167–183, 1993.

    Google Scholar 

  24. S. Toda. On the computational power of PP and ⊕P.Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 514–519, 1989.

  25. S. Toda. PP is as hard as the polynomial-time hierarchy.SLAM Journal on Computing, 20:865–877, 1991.

    Google Scholar 

  26. L. Valiant and V Vazirani. NP is as easy as detecting unique solutions.Theoretical Computer Science, 47:85–93, 1986.

    Google Scholar 

  27. S. Zachos. Robustness of probabilistic computational complexity classes under definitional perturbations.Information and Computation, 54:143–154, 1982.

    Google Scholar 

  28. S. Zachos. Probabilistic quantifiers and games.Journal of Computer and System Sciences, 36:433–451, 1988.

    Google Scholar 

  29. S. Zachos and H. Heller. A decisive characterization of BPP.Information and Computation, 69:125–135, 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. State University of New York, 14260, Buffalo, NY, USA

    K. W. Regan

  2. Syracuse University, 13244, Syracuse, NY, USA

    J. S. Royer

Authors
  1. K. W. Regan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. S. Royer
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The first author was supported in part by NSF Grant CCR-9011248 and the second author was supported in part by NSF Grant CCR-89011154.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Regan, K.W., Royer, J.S. On closure properties of bounded two-sided error complexity classes. Math. Systems Theory 28, 229–243 (1995). https://doi.org/10.1007/BF01303057

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01303057

Keywords

Search

Navigation