UP and the low and high hierarchies: A relativized separation
From MaRDI portal
Publication:4895813
DOI10.1007/BF01184809zbMath0858.68040MaRDI QIDQ4895813
Timothy J. Long, Ming-Jye Sheu
Publication date: 16 October 1996
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items
Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Relativized worlds with an infinite hierarchy ⋮ A note on unambiguous function classes
Cites Work
- Unnamed Item
- A low and a high hierarchy within NP
- Turing machines with few accepting computations and low sets for PP
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Gap-definable counting classes
- Separating the low and high hierarchies by oracles
- One-way functions and the nonisomorphism of NP-complete sets
- Parity, circuits, and the polynomial-time hierarchy
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Complexity Measures for Public-Key Cryptosystems
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The Extended Low Hierarchy is an Infinite Hierarchy
- Relativized Polynomial Time Hierarchies Having Exactly K Levels