On independent random oracles (Q1185000)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	On independent random oracles	scientific article

Statements

scholarly article

0 references

On independent random oracles (English)

0 references

0 references

Theoretical Computer Science

0 references

publication date

28 June 1992

0 references

zbMATH Keywords

polynomial-time complexity classes

0 references

random oracle

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(92)90317-9

0 references

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

A Theory of Program Size Formally Identical to Information Theory

0 references

Incompleteness theorems for random reals

0 references

Computational Complexity of Probabilistic Turing Machines

0 references

0 references

A Note on Randomized Polynomial Time

0 references

0 references

Category and Measure in Complexity Classes

0 references

Pseudorandom sources for BPP

0 references

A Pseudorandom Oracle Characterization of ${\text{BPP}}$

0 references

The definition of random sequences

0 references

0 references

Process complexity and effective random tests

0 references

0 references

Polynomial-time reducibilities and ``almost all'' oracle sets

0 references

On Tally Relativizations of $BP$-Complexity Classes

0 references

Identifiers

zbMATH Open document ID

0 references

10.1016/0304-3975(92)90317-9

0 references

Mathematics Subject Classification ID

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1185000

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