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

DOI10.1016/0304-3975(95)00078-XMaRDI QIDQ1365687zbMATH OpenFDO

Authors Sarah E. Mocas

Publication date 7 September 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(95)00078-X

zbMATH Keywords

exponential-time hierarchy

Mathematics Subject Classification ID

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

Recommendations

• Defying upward and downward separation
• scientific article; zbMATH DE number 4080914
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets

Cites work

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

Cited in

(10)

• Separating classes in the exponential-time hierarchy from classes in PH
• Sparse selfreducible sets and nonuniform lower bounds
• scientific article; zbMATH DE number 4130016 (Why is no real title available?)
• scientific article; zbMATH DE number 1018738 (Why is no real title available?)
• scientific article; zbMATH DE number 1543364 (Why is no real title available?)
• Fine separation of average time complexity classes
• 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
• Bounded Henkin quantifiers and the exponential time hierarchy

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1365687)