Alternating Hierarchies for Time-Space Tradeoffs

Nepomnjaščǐı’s Theorem states that for all 0 ≤ < 1 and k> 0 the class of languages recognized in nondeterministic time nk and space n, NTISP[nk, n], is contained in the linear time hierarchy. By considering restrictions on the size of the universal quantifiers in the linear time hierarchy, this paper refines Nepomnjaščǐı’s result to give a sub-hierarchy, Eu-LinH, of the linear time hierarchy that is contained in NP and which contains NTISP[nk, n]. Hence, Eu-LinH contains NL and SC. This paper investigates basic structural properties of Eu-LinH. Then the relationships between Eu-LinH and the classes NL, SC, and NP are considered to see if they can shed light on the NL = NP or SC = NP questions. Finally, a new hierarchy, ξ-LinH, is defined to reduce the space requirements needed for the upper bound on Eu-LinH