Alternating Hierarchies for Time-Space Tradeoffs
| dc.creator | Pollett, Chris | |
| dc.creator | Miles, Eric | |
| dc.date | 2008-01-08 | |
| dc.date.accessioned | 2026-07-07T08:53:20Z | |
| dc.date.available | 2026-07-07T08:53:20Z | |
| dc.description | 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. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/0801.1307 | |
| dc.identifier | http://arxiv.org/abs/0801.1307 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/145585 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.1.3 | |
| dc.title | Alternating Hierarchies for Time-Space Tradeoffs | |
| dc.type | text |