On random oracle separations

DOI10.1016/0020-0190(91)90054-LzbMath0735.68029OpenAlexW1998388147WikidataQ126812549 ScholiaQ126812549MaRDI QIDQ1182108

Ronald V. Book

Publication date: 27 June 1992

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

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90054-l

zbMATH Keywords

random oraclesrelativizations of complexity classesuniform witness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• On the random oracle hypothesis
• Characterizing polynomial complexity classes by reducibilities
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Structural complexity theory: Recent surprises

This page was built for publication: On random oracle separations