Random oracles separate PSPACE from the polynomial-time hierarchy
From MaRDI portal
Publication:1108794
DOI10.1016/0020-0190(87)90036-6zbMath0654.68052OpenAlexW2111824166WikidataQ61687899 ScholiaQ61687899MaRDI QIDQ1108794
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
computational complexitypolynomial-time hierarchyrandom oraclerelativized complexity classbounded-depth Boolean circuitsconstant-depth parity circuits
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
