Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy

ABSTRACT

The probabilistic polynomial-time hierarchy (BPH) is the hierarchy generated by applying the BP-operator to the Meyer-Stockmeyer polynomial-time hierarchy (PH), where the BP-operator is the natural generalization of the probabilistic complexity class BPP. The similarity and difference between the two hierarchies BPH and PH is investigated. Oracles A and B are constructed such that both PH(A) and PH(B) are infinite while BPH(A) is not equal to PH(A) at any level and BPH(B) is identical to PH(B) at every level. Similar separating and collapsing results in the case that PH(A) is finite having exactly k levels are also considered.

REFERENCES

• 1: AIELLO, W., GOLDWASSER, S., AND HASTAD, J. On the power of interaction. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 368-379.
• 2: L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
• 3: Laszlo Babai, Random oracles separate PSPACE from the polynomial-time hierarchy, Information Processing Letters, v.26 n.1, p.51-53, 15 Sept. 1987 [doi>10.1016/0020-0190(87)90036-6]
• 4: BAKER, T., AND SELMAN, A. A second step toward the polynomial hierarchy. Theoret, Comput. Sci. 8 (1979), 177-187.
• 5: Jose L. Balcázar , Ronald V. Book , Uwe Schöning, The polynomial-time hierarchy and sparse oracles, Journal of the ACM (JACM), v.33 n.3, p.603-617, July 1986 [doi>10.1145/5925.5937]
• 6: BALCAZAR, J., AND RUSSO, D. Immunity and simplicity in relativizations of probabilistic complexity classes. RAIRO Theoret. Inf. Appl. 22 (1988), 227-244.
• 7: BENNETT, C., AND GILL, J. Relative to a random oracle, pA # NpA # coNPa with probability 1. SIAM J. Comput. 10 ( 1981 ), 96-113.
• 8: R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
• 9: J Y Cai, With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.21-29, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12133]
• 10: Lance Fortnow , Michael Sipser, Are there interactive protocols for CO-NP languages?, Information Processing Letters, v.28 n.5, p.249-251, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90199-8]
• 11: FURST, M., SAXE, J., AND SIPSER, M. Parity, circuits and the polynomial-time hierarchy. Math. Syst. Theory 17 (1984), 13-27.
• 12: GILL, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675-695.
• 13: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 14: S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
• 15: HASTAD, J.T. Computational limitations for small-depth circuits. Ph.D. dissertation. MIT Press, Cambridge, Mass., 1987.
• 16: Ker-I Ko, Relativized polynomial time hierarchies having exactly K levels, SIAM Journal on Computing, v.18 n.2, p.392-408, April 1989 [doi>10.1137/0218027]
• 17: LAUTEMANN, C. BPP and the polynomial hierarchy. Inf. Proc. Lett. 14 (1983), 215-217.
• 18: Timothy J. Long , Alan L. Selman, Relativizing complexity classes with sparse oracles, Journal of the ACM (JACM), v.33 n.3, p.618-627, July 1986 [doi>10.1145/5925.5938]
• 19: Charles Rackoff, Relativized Questions Involving Probabilistic Algorithms, Journal of the ACM (JACM), v.29 n.1, p.261-268, Jan. 1982 [doi>10.1145/322290.322306]
• 20: M. Santha, Relativized Arthur-Merlin versus Merlin-Arthur games, Information and Computation, v.80 n.1, p.44-49, January 1, 1989 [doi>10.1016/0890-5401(89)90022-9]
• 21: Uwe Schöning, Complexity and structure, Springer-Verlag New York, Inc., New York, NY, 1986
• 22: U. Schoning, Probalisitic complexity classes and lowness, Journal of Computer and System Sciences, v.39 n.1, p.84-100, Aug. 1989 [doi>10.1016/0022-0000(89)90020-2]
• 23: Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
• 24: STOCKMEVER, L. The polynomial time hierarchy. Theoret. Comput. Sci. 3 (1977), 1-22.
• 25: WRATHALL, C. Complete sets and the polynomial time hierarchy. Theoret. Comput. Sci 3 (1977), 23-33.
• 26: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States
• 27: S Zachos, Probabilistic quantifiers, adversaries, and complexity classes: an overview, Proc. of the conference on Structure in complexity theory, p.383-400, June 1986, Berkeley, California, United States
• 28: Stathis Zachos , Hans Heller, A decisive characterization of BPP, Information and Control, v.69 n.1-3, p.125-135, April/May/June 1986 [doi>10.1016/S0019-9958(86)80044-4]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Machine-independent complexity**

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies

General Terms:
Algorithms, Theory