The generic oracle hypothesis is false (Q1209320)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	The generic oracle hypothesis is false	scientific article

Statements

scholarly article

0 references

The generic oracle hypothesis is false (English)

0 references

James A. Foster

0 references

Information Processing Letters

0 references

publication date

16 May 1993

0 references

zbMATH Keywords

generic oracle hypothesis

0 references

genericity

0 references

MaRDI profile type

MaRDI publication profile

0 references

Random oracles separate PSPACE from the polynomial-time hierarchy

0 references

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

0 references

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

0 references

With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

0 references

Are there interactive protocols for co-NP languages?

0 references

Structural complexity theory: Recent surprises

0 references

Some applications of forcing to hierarchy problems in arithmetic

0 references

0 references

On the random oracle hypothesis

0 references

Category and Measure in Complexity Classes

0 references

An upward measure separation theorem

0 references

Identifiers

zbMATH Open document ID

0 references

10.1016/0020-0190(93)90216-V

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1209320

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1209320&oldid=34103645"