The Sky is Falling: The Strong Exponential Hierarchy Collapses
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
This paper investigates the complexity of the high levels of the exponential hierarchy [HY84,HIS85]: Are they hard, and if so why are they hard? We show that