The strong exponential hierarchy collapses

摘要

Composed of the levels E (i.e., ∪c DTIME[2cn]), NE, PNE, NPNE, etc., the strong exponential hierarchy is an exponential-time analogue of the polynomial-time hierarchy. This paper shows that the strong exponential hierarchy collapses to PNE, its Δ2 level. E ≠ pNE = NPNE ∪ NPNPNE ∪ … The proof stresses the use of partial census information and the exploitation of nondeterminism. Extending these techniques, we derive new quantitative relativization results: if the weak exponential hierarchy's ΔJ + 1 and Σj + 1 levels, respectively EΣjp and NEΣjp, do separate, this is due to the large number of queries NE makes to its Σjp database. Our techniques provide a successful method of proving the collapse of certain complexity classes.