Random oracles separate PSPACE from the polynomial-time hierarchy

DOI10.1016/0020-0190(87)90036-6zbMath0654.68052OpenAlexW2111824166WikidataQ61687899 ScholiaQ61687899MaRDI QIDQ1108794

László Babai

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90036-6

zbMATH Keywords

computational complexitypolynomial-time hierarchyrandom oraclerelativized complexity classbounded-depth Boolean circuitsconstant-depth parity circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

The power of adaptiveness and additional queries in random-self- reductions ⋮ An information-theoretic treatment of random-self-reducibility ⋮ When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ On closure properties of bounded two-sided error complexity classes ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Borel complexity and Ramsey largeness of sets of oracles separating complexity classes ⋮ Unnamed Item ⋮ On the correlation of symmetric functions ⋮ Interleaved Group Products ⋮ Strong self-reducibility precludes strong immunity ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ On the power of parity polynomial time ⋮ Circuit size relative to pseudorandom oracles ⋮ The generic oracle hypothesis is false ⋮ Unnamed Item ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ On the correlation of symmetric functions ⋮ Enumerative counting is hard ⋮ Cryptography with constant input locality ⋮ Hardness of learning problems over Burnside groups of exponent 3

Cites Work

• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question