Alternating Hierarchies for Time-Space Tradeoffs

Details Alternating Hierarchies for Time-Space Tradeoffs Alternating Hierarchies for Time-Space Tradeoffs

2008-01-08

arxiv.org/abs/0801.1307v1

Computer Science

Computational Complexity

14 pages

Scientific paper

Nepomnjascii's Theorem states that for all 0 <= \epsilon < 1 and k > 0 the class of languages recognized in nondeterministic time n^k and space n^\epsilon, NTISP[n^k, n^\epsilon ], 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^\epsilon ]. 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.

Affiliated with

Also associated with

No associations

Rating

Alternating Hierarchies for Time-Space Tradeoffs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Alternating Hierarchies for Time-Space Tradeoffs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alternating Hierarchies for Time-Space Tradeoffs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-421793