The generic oracle hypothesis is false

DOI10.1016/0020-0190(93)90216-VzbMATH Open0795.68075WikidataQ57834864 ScholiaQ57834864MaRDI QIDQ1209320FDOQ1209320

Authors: James A. Foster 

Publication date: 16 May 1993

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

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

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)

Cites Work

• Title not available (Why is that?)
• Some applications of forcing to hierarchy problems in arithmetic
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Category and Measure in Complexity Classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Are there interactive protocols for co-NP languages?
• On the random oracle hypothesis
• Structural complexity theory: Recent surprises
• An upward measure separation theorem
• Random oracles separate PSPACE from the polynomial-time hierarchy

Cited In (5)

• Forcing complexity: Minimum sizes of forcing conditions.
• The random oracle hypothesis is false
• An oracle builder's toolkit
• Strong self-reducibility precludes strong immunity
• Title not available (Why is that?)

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)