Random oracles separate PSPACE from the polynomial-time hierarchy (Q1108794): Difference between revisions

By confirming a conjecture of \textit{M. Furst}, \textit{J. B. Saxe} and \textit{M. Sipser} [Math. Syst. Theory 17, 13-27 (1984; Zbl 0534.94008)] on the size of constant-depth parity circuits, \textit{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. \textit{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 \textit{M. Ajtai} and \textit{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.