With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

DOI10.1016/0022-0000(89)90033-0zbMath0668.68052OpenAlexW4300757861MaRDI QIDQ1118405

Jin-Yi Cai

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6555

zbMATH Keywords

PSPACErandom oraclepolynomial time hiararchy

Mathematics Subject Classification ID

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

Related Items (22)

The correlation between parity and quadratic polynomials mod \(3\) ⋮ Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity ⋮ On collapsing the polynomial-time hierarchy ⋮ An information-theoretic treatment of random-self-reducibility ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Relativized collapsing between BPP and PH under stringent oracle access ⋮ An observation on probability versus randomness with applications to complexity classes ⋮ On closure properties of bounded two-sided error complexity classes ⋮ On complexity classes and algorithmically random languages ⋮ Borel complexity and Ramsey largeness of sets of oracles separating complexity classes ⋮ On the correlation of symmetric functions ⋮ Lower bounds for constant-depth circuits in the presence of help bits ⋮ Strong self-reducibility precludes strong immunity ⋮ On random oracle separations ⋮ On the power of parity polynomial time ⋮ Circuit size relative to pseudorandom oracles ⋮ The generic oracle hypothesis is false ⋮ Unnamed Item ⋮ An oracle separating \(\oplus P\) from \(PP^{PH}\) ⋮ On the robustness of ALMOST-$\mathcal {R}$ ⋮ On the correlation of symmetric functions

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Alternation
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Unnamed Item
• Unnamed Item

This page was built for publication: With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy