On independent random oracles

DOI10.1016/0304-3975(92)90317-9zbMath0745.68049OpenAlexW2031489119MaRDI QIDQ1185000

Jack H. Lutz

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90317-9

zbMATH Keywords

random oraclepolynomial-time complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Feasible reductions to Kolmogorov-Loveland stochastic sequences

Cites Work

• Incompleteness theorems for random reals
• Process complexity and effective random tests
• Polynomial-time reducibilities and ``almost all oracle sets
• Pseudorandom sources for BPP
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• Category and Measure in Complexity Classes
• A Note on Randomized Polynomial Time
• On Tally Relativizations of $BP$-Complexity Classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• A Theory of Program Size Formally Identical to Information Theory
• Computational Complexity of Probabilistic Turing Machines
• The definition of random sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item