A refinement of the low and high hierarchies
From MaRDI portal
Publication:4841766
DOI10.1007/BF01185399zbMath0849.68038OpenAlexW2017240293MaRDI QIDQ4841766
Ming-Jye Sheu, Timothy J. Long
Publication date: 24 July 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01185399
Related Items (5)
The extended low hierarchy is an infinite hierarchy ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ A note on P-selective sets and closeness ⋮ The structure of logarithmic advice complexity classes
Cites Work
- Unnamed Item
- A low and a high hierarchy within NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On counting problems and the polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- A second step toward the polynomial hierarchy
- A note on sparse sets and the polynomial-time hierarchy
- Sets with small generalized Kolmogorov complexity
- Self-reducible sets of small density
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Quantitative Relativizations of Complexity Classes
- Sparse Sets, Lowness and Highness
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- On Sets Truth-Table Reducible to Sparse Sets
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Lower bounds for the low hierarchy
- Complete sets and closeness to complexity classes
This page was built for publication: A refinement of the low and high hierarchies
