Alternating Hierarchies for Time-Space Tradeoffs

2008/01/08 by Chris Pollett, Eric Miles, Pollett, Chris +1 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0801.1307

openalex publication_date 2008/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Nepomnjascii's Theorem states that for all 0 <= ε< 1 and k > 0 the class of languages recognized in nondeterministic time n^k and space n^ε, NTISP[n^k, 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 Nepomnjascii's result to give a sub- hierarchy, Eu-LinH, of the linear time hierarchy that is contained in NP and which contains NTISP[n^k, 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, zeta -LinH, is defined to reduce the space requirements needed for the upper bound on Eu-LinH.

Cited by

• Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness

Related

• A Predicative Harmonization of the Time and Provable Hierarchies
• A note on time hierarchies for reasonable semantic classes without advice
• Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case
• Proper Hierarchies in Polylogarithmic Time and Absence of Complete\n Problems
• A correspondence between the time and space complexity