The generic oracle hypothesis is false
type: Item
instance of: scholarly article
title: The generic oracle hypothesis is false
zbMATH Open document ID: 0795.68075
DOI: 10.1016/0020-0190(93)90216-V
author: James A. Foster
published in: Information Processing Letters
publication date: 1993-05-16T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 167735
zbMATH Keywords: generic oracle hypothesis
zbMATH Keywords: genericity
Wikidata QID: Q57834864
MaRDI profile type: Publication
cites work: Random oracles separate PSPACE from the polynomial-time hierarchy
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
cites work: Are there interactive protocols for co-NP languages?
cites work: Structural complexity theory: Recent surprises
cites work: Some applications of forcing to hierarchy problems in arithmetic
cites work: Q3905267
cites work: On the random oracle hypothesis
cites work: Category and Measure in Complexity Classes
cites work: An upward measure separation theorem
description: scientific article; zbMATH DE number 167735