Separating classes in the exponential-time hierarchy from classes in PH

DOI10.1016/0304-3975(95)00078-XzbMath0877.68057MaRDI QIDQ1365687

Sarah E. Mocas

Publication date: 7 September 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

exponential-time hierarchy

Mathematics Subject Classification ID

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

Related Items (5)

Separating classes in the exponential-time hierarchy from classes in PH ⋮ Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ Sparse selfreducible sets and nonuniform lower bounds

Cites Work

• Unnamed Item
• The strong exponential hierarchy collapses
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Separating classes in the exponential-time hierarchy from classes in PH
• A hierarchy for nondeterministic time complexity
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Nondeterministic Space is Closed under Complementation
• Alternation
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On the cutting edge of relativization: The resource bounded injury method
• On the Computational Complexity of Algorithms
• Quasi-realtime languages

This page was built for publication: Separating classes in the exponential-time hierarchy from classes in PH