A refinement of the low and high hierarchies

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

zbMATH Keywords

sparse setspolynomial-time hierarchyextended low hierarchies

Mathematics Subject Classification ID

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

Related Items

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