Time and Space Hierarchies

What the world needs are the time and space hierarchies clearly spelled out in one place.

A function t is time-constructible if there is a Turing machine M such that on input 1ⁿ outputs 1^t(n) in time O(t(n)). Space constructible functions are defined similarly. All the natural functions are time and space constructible.

DTIME(t(n)) are the set of problems computable by a multi-tape Turing machine in deterministic time O(t(n)) on inputs of length n. NTIME (nondeterministic time), DSPACE and NSPACE are defined similarly.

Let t₁ and t₂ be time-constructible functions and s₁ and s₂ space-constructible function. We let "⊂" denote strict subset. A function f(n)=o(g(n)) if lim_n→∞f(n)/g(n)=0.

1. If t₁(n)log t₁(n)=o(t₂(n)) then DTIME(t₁(n))⊂DTIME(t₂(n)).
2. If t₁(n+1)=o(t₂(n)) then NTIME(t₁(n))⊂NTIME(t₂(n)).
3. If s₁(n)=o(s₂(n)) then DSPACE(s₁(n))⊂DSPACE(s₂(n)).
4. If s₁(n)=o(s₂(n)) then NSPACE(s₁(n))⊂NSPACE(s₂(n)).

The DSPACE hierarchy is straightforward diagonalization. For DTIME the proof is similar but we lose log t₁(n) in the simulation of a k-tape machine by a 2-tape machine.

Straightforward diagonalization does not work directly for nondeterministic computation because one need to negate the answer. For NSPACE we easily get around this problem by using Immerman-Szelepcsényi.

The NTIME hierarchy has the most interesting proof that leads to requiring the "+1" in t₁(n+1). This can make a big difference for t₁(n) larger than 2ⁿ².

An NTIME hierarchy was first proved by Cook and in the strongest form by Seiferas, Fischer and Meyer. We sketch a simple proof due to Zàk.

Let M₁,… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1ⁱ01^m01^k:

• If k<m^t₁(m) then simulate M_i on input 1ⁱ01^m01^k+1 for t₂(|w|) steps.
• If k=m^t₁(m) then accept if 1ⁱ01^m0 rejects which we can do quickly as a function of the current input size.

This machine uses time O(t₂(n)). If NTIME(t₁(n))=NTIME(t₂(n)) then there is an equivalent machine M_i using time O(t₁(n)).

Since t₁(n+1)=o(t₂(n)) we have for sufficiently large m,

1ⁱ01^m0 in L(M) ⇔ 1ⁱ01^m01 in L(M) ⇔ … ⇔ 1ⁱ01^m01^mt₁(m) in L(M) ⇔ 1ⁱ01^m0 not in L(M) a contradiction.