Random oracles separate PSPACE from the polynomial-time hierarchy

DOI10.1016/0020-0190(87)90036-6MaRDI QIDQ1108794zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 complexityrandom oraclepolynomial-time hierarchyrelativized 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)

Recommendations

• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• On random oracle separations
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• Circuit size relative to pseudorandom oracles
• An oracle separating \(\oplus P\) from \(PP^{PH}\)

Cites work

• scientific article; zbMATH DE number 3950504 (Why is no real title available?)
• 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
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(29)

• On the correlation of symmetric functions
• Worst-Case to Average-Case Reductions for Subclasses of P
• Enumerative counting is hard
• Polynomial-time random oracles and separating complexity classes
• Hardness of learning problems over Burnside groups of exponent 3
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• On closure properties of bounded two-sided error complexity classes
• The power of adaptiveness and additional queries in random-self- reductions
• On the correlation of symmetric functions
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Interleaved Group Products
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Sampling lower bounds: Boolean average-case and permutations
• Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
• Circuit size relative to pseudorandom oracles
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7650112 (Why is no real title available?)
• An oracle separating \(\oplus P\) from \(PP^{PH}\)
• Cryptography with constant input locality
• Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
• Circuit depth relative to a random oracle
• Strong self-reducibility precludes strong immunity
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• The generic oracle hypothesis is false
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
• On the power of parity polynomial time
• scientific article; zbMATH DE number 4125012 (Why is no real title available?)
• Parity, circuits, and the polynomial-time hierarchy
• An information-theoretic treatment of random-self-reducibility (extended abstract)

This page was built for publication: Random oracles separate PSPACE from the polynomial-time hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108794)