A refinement of the low and high hierarchies

DOI10.1007/BF01185399zbMath0849.68038MaRDI QIDQ4841766

Ming-Jye Sheu, Timothy J. Long

Publication date: 24 July 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

sparse sets; polynomial-time hierarchy; extended low hierarchies

Mathematics Subject Classification ID

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

Related Items

Fault-tolerance and complexity (Extended abstract), Upper bounds for the complexity of sparse and tally descriptions, 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