Circuit size relative to pseudorandom oracles
From MaRDI portal
Publication:1208410
DOI10.1016/0304-3975(93)90256-SzbMath0764.68043OpenAlexW2083770479MaRDI QIDQ1208410
William J. Schmidt, Jack H. Lutz
Publication date: 16 May 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90256-s
Related Items
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Relative to a random oracle, P/poly is not measurable in EXP, Circuit depth relative to a random oracle, On the contribution of backward jumps to instruction sequence expressiveness, On pseudorandomness and resource-bounded measure
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relativized circuit complexity
- Complexity and structure
- On the notion of infinite pseudorandom sequences
- Random oracles separate PSPACE from the polynomial-time hierarchy
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Almost everywhere high nonuniform complexity
- Sets with small generalized Kolmogorov complexity
- Pseudorandom sources for BPP
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
- Some Observations on Separating Complexity Classes
- On the random oracle hypothesis
- Characterizing polynomial complexity classes by reducibilities
- Category and Measure in Complexity Classes
- Randomness conservation inequalities; information and independence in mathematical theories
- Algorithms and Randomness
- 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
- Alternation
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- The isomorphism conjecture fails relative to a random oracle
- P-Printable Sets
- On the Length of Programs for Computing Finite Binary Sequences
- The definition of random sequences
- A formal theory of inductive inference. Part II
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
