×

Random oracles separate PSPACE from the polynomial-time hierarchy. (English) Zbl 0654.68052

By confirming a conjecture of M. Furst, J. B. Saxe and M. Sipser [Math. Syst. Theory 17, 13-27 (1984; Zbl 0534.94008)] on the size of constant-depth parity circuits, A. C. Yao [Separating the polynomial time hierarchy by oracles, Proc. 26th FOCS, 1-10 (1985)] has completed the proof that PSPACE is separated from the polynomial-time hierarchy by some oracles. J. Cai [With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, Proc. 18th STOC, 21-29 (1986); cf. Lect. Notes Comput. Sci. 223, 104 (1986) and J. Comput. Syst. Sci. 38, No.1, 68-85 (1989)] modified Yao’s complex argument to prove that this separation occurs relative to almost every oracle. We prove that this result actually follows immediately from Yao’s theorem, using a simple construction of M. Ajtai and M. Ben- Or [A theorem on probabilistic constant depth computation, Proc. 16th ACM STOC, 471-474 (1984)] to eliminate randomization in bounded-depth Boolean circuits.

MSC:

68Q25 Analysis of algorithms and problem complexity
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)

Citations:

Zbl 0534.94008
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., \(Σ^1_1\) formulas on finite structures, Ann. Pure & Appl. Logic, 24, 1-48 (1983) · Zbl 0519.03021
[2] Ajtai, M.; Ben-Or, M., A theorem on probabilistic constant depth computations, Proc. 16th ACM STOC, 471-474 (1984), Washington, D.C.
[3] Baker, T.; Gill, J.; Solovay, R., Relativations of the \(P = NP \)? question, SIAM J. Comput., 4, 431-442 (1975) · Zbl 0323.68033
[4] Bennett, C. H.; Gill, J., Relative to a random oracle \(A, P^A\) ≠ \( NP^A \) ≠ \( coNP^A\) with probability 1, SIAM J. Comput., 10, 96-113 (1981) · Zbl 0454.68030
[5] Cai, J. Y., With probability one a random oracle separates PSPACE from the polynomial hierarchy, Proc. 18th STOC, 21-29 (1986)
[6] Furst, M.; Saxe, J.; Sipser, M., Parity, circuits, and the polynomial time hierarchy, Proc. 22nd FOCS, 260-270 (1981)
[7] Kurtz, S. A., Randomness and Genericity in the Degrees of Unsolvability, (Ph.D. Thesis (1981), Univ. of Illinois at Urbana- Champaign)
[8] Kurtz, S. A., On the random oracle hypothesis, Proc. 14th STOC, 224-230 (1982)
[9] Poizat, B., \(Q = NQ \)?, J. Symbolic Logic, 51, 22-32 (1986) · Zbl 0592.03027
[10] Sipser, M., Borel sets and circuit complexity, Proc. 15th STOC, 61-69 (1983)
[11] Yao, A. C., Separating the polynomial-time hierarchy by oracles, Proc. 26th FOCS, 1-10 (1985)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.