The generic oracle hypothesis is false

DOI10.1016/0020-0190(93)90216-VzbMath0795.68075WikidataQ57834864 ScholiaQ57834864MaRDI QIDQ1209320

James A. Foster

Publication date: 16 May 1993

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

zbMATH Keywords

genericitygeneric oracle hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Strong self-reducibility precludes strong immunity

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