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

^{n}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

_{1}and t_{2}be time-constructible functions and s_{1}and s_{2}space-constructible function. We let "⊂" denote strict subset. A function f(n)=o(g(n)) if lim_{n→∞}f(n)/g(n)=0.- If t
_{1}(n)log t_{1}(n)=o(t_{2}(n)) then DTIME(t_{1}(n))⊂DTIME(t_{2}(n)). - If t
_{1}(n+1)=o(t_{2}(n)) then NTIME(t_{1}(n))⊂NTIME(t_{2}(n)). - If s
_{1}(n)=o(s_{2}(n)) then DSPACE(s_{1}(n))⊂DSPACE(s_{2}(n)). - If s
_{1}(n)=o(s_{2}(n)) then NSPACE(s_{1}(n))⊂NSPACE(s_{2}(n)).

_{1}(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

_{1}(n+1). This can make a big difference for t_{1}(n) larger than 2^{n2}.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

_{1},… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1^{i}01^{m}01^{k}:-
If
k<m
^{t1(m)}then simulate M_{i}on input 1^{i}01^{m}01^{k+1}for t_{2}(|w|) steps. -
If
k=m
^{t1(m)}then accept if 1^{i}01^{m}0 rejects which we can do quickly as a function of the current input size.

_{2}(n)). If NTIME(t_{1}(n))=NTIME(t_{2}(n)) then there is an equivalent machine M_{i}using time O(t_{1}(n)).Since t

_{1}(n+1)=o(t_{2}(n)) we have for sufficiently large m,1 a contradiction.^{i}01^{m}0 in L(M) ⇔ 1^{i}01^{m}01 in L(M) ⇔ … ⇔ 1^{i}01^{m}01^{mt1(m)}in L(M) ⇔ 1^{i}01^{m}0 not in L(M)

--

Posted by Lance to My Computational Complexity Web Log at 7/14/2004 08:40:49 AM- If t