The generic oracle hypothesis is false

DOI10.1016/0020-0190(93)90216-VMaRDI QIDQ1209320zbMATH OpenWikidataFDO

Authors 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)

Recommendations

• The random oracle hypothesis is false
• Computable Dowd-type generic oracles
• Relativized generic classes P and NP
• An oracle builder's toolkit
• Generic separations

Cites work

• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• An upward measure separation theorem
• Are there interactive protocols for co-NP languages?
• Category and Measure in Complexity Classes
• On the random oracle hypothesis
• Random oracles separate PSPACE from the polynomial-time hierarchy
• 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
• Some applications of forcing to hierarchy problems in arithmetic
• Structural complexity theory: Recent surprises
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Cited in

(5)

• Strong self-reducibility precludes strong immunity
• An oracle builder's toolkit
• Forcing complexity: Minimum sizes of forcing conditions.
• scientific article; zbMATH DE number 4025422 (Why is no real title available?)
• The random oracle hypothesis is false

This page was built for publication: The generic oracle hypothesis is false

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