Relativized worlds with an infinite hierarchy
From MaRDI portal
Publication:1606916
DOI10.1016/S0020-0190(99)00034-4zbMath1002.68060WikidataQ61688303 ScholiaQ61688303MaRDI QIDQ1606916
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (5)
Hausdorff dimension and oracle constructions ⋮ Relative to a random oracle, P/poly is not measurable in EXP ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Error-bounded probabilistic computations between MA and AM ⋮ One complexity theorist's view of quantum computing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Gap-definable counting classes
- The random oracle hypothesis is false
- Hardness vs randomness
- On collapsing the polynomial-time hierarchy
- An oracle builder's toolkit
- Relative to a random oracle, NP is not small
- Parity, circuits, and the polynomial-time hierarchy
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Structural analysis of the complexity of inverse functions
- Algebraic methods for interactive proof systems
- Threshold Computation and Cryptographic Security
- The isomorphism conjecture fails relative to a random oracle
- The complexity of generating and checking proofs of membership
- UP and the low and high hierarchies: A relativized separation
This page was built for publication: Relativized worlds with an infinite hierarchy
