zbMATH — the first resource for mathematics

More on BPP and the polynomial-time hierarchy. (English) Zbl 0875.68425
Summary: We simplify known proofs that BPP lies within the Polynomial-time Hierarchy. Furthermore, our simple proof shows that BPP is contained in a complexity class that presumably lies even lower in this Hierarchy than was previously known. Our technique also simplifies the proof that one-sided-error IP equals two-sided-error IP.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[1] Alon, N.; Spencer, J., The probabilistic method, (1992), Wiley New York
[2] Babai, L.; Moran, S., Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes, J. comput. system sci., 36, 254-276, (1988) · Zbl 0652.03029
[3] Furer, M.; Goldreich, O.; Mansour, Y.; Sipser, M.; Zachos, S., On completeness and soundness in interactive proof systems, Adv. comput. res., 5, 429-442, (1989)
[4] Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proofs, SIAM J. comput., 18, 186-208, (1989) · Zbl 0677.68062
[5] Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, Adv. comput. res., 5, 73-90, (1989)
[6] Lautemann, C., BPP and the polynomial hierarchy, Inform. process. lett., 17, 215-217, (1983) · Zbl 0515.68042
[7] Russell, A.; Sundaram, R., Symmetric alternation captures BPP, Tech. rept. MIT-LCS-TM-541, (1995) · Zbl 0912.68054
[8] Sipser, M., A complexity theoretic approach to randomness, (), 330-335
[9] Stockmeyer, L.J., The polynomial time hierarchy, Theoret. comput. sci., 3, 1-22, (1976) · Zbl 0353.02024
[10] Shamir, A., Ip = pspace, (), 11-15
[11] Wrathall, C., Complete sets and the polynomial-time hierarchy, Theoret. comput. sci., 3, 23-33, (1976) · Zbl 0366.02031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.