Random oracles separate PSPACE from the polynomial-time hierarchy
type: Item
instance of: scholarly article
title: Random oracles separate PSPACE from the polynomial-time hierarchy
zbMATH Open document ID: 0654.68052
DOI: 10.1016/0020-0190(87)90036-6
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4068282
zbMATH Keywords: computational complexity
zbMATH Keywords: relativized complexity class
zbMATH Keywords: random oracle
zbMATH Keywords: constant-depth parity circuits
zbMATH Keywords: polynomial-time hierarchy
zbMATH Keywords: bounded-depth Boolean circuits
Wikidata QID: Q61687899
author: László Babai
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90036-6
OpenAlex ID: W2111824166
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Q3720579
DBLP publication ID: journals/ipl/Babai87
description: scientific article; zbMATH DE number 4068282