The generic oracle hypothesis is false
From MaRDI portal
Publication:1209320
DOI10.1016/0020-0190(93)90216-VzbMath0795.68075WikidataQ57834864 ScholiaQ57834864MaRDI QIDQ1209320
Publication date: 16 May 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- An upward measure separation theorem
- Random oracles separate PSPACE from the polynomial-time hierarchy
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Are there interactive protocols for co-NP languages?
- On the random oracle hypothesis
- Category and Measure in Complexity Classes
- 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
- Structural complexity theory: Recent surprises
- Some applications of forcing to hierarchy problems in arithmetic
This page was built for publication: The generic oracle hypothesis is false