The Tight Deterministic Time Hierarchy

Let k be a constant ≥ 2, and let us consider only deterministic k-tape Turing machines. We assume t 2 (n) > n and t 2 is computable in time t 2 . Then there is a language which is accepted in time t 2 , but not accepted in any time t 1 with t 1 (n) = o(t 2 (n)). Furthermore, we obtain a strong hierarchy (isomorphic to the rationals Q ) for languages accepted in fixed space and variable time.

Authors

• Martin Fürer

Keywords

No keywords are indexed for this paper.