Wednesday, July 14, 2004

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 1n outputs 1t(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 t1 and t2 be time-constructible functions and s1 and s2 space-constructible function. We let "⊂" denote strict subset. A function f(n)=o(g(n)) if limn→∞f(n)/g(n)=0.

1. If t1(n)log t1(n)=o(t2(n)) then DTIME(t1(n))⊂DTIME(t2(n)).
2. If t1(n+1)=o(t2(n)) then NTIME(t1(n))⊂NTIME(t2(n)).
3. If s1(n)=o(s2(n)) then DSPACE(s1(n))⊂DSPACE(s2(n)).
4. If s1(n)=o(s2(n)) then NSPACE(s1(n))⊂NSPACE(s2(n)).
The DSPACE hierarchy is straightforward diagonalization. For DTIME the proof is similar but we lose log t1(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 t1(n+1). This can make a big difference for t1(n) larger than 2n2.

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 M1,… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1i01m01k:

• If k<mt1(m) then simulate Mi on input 1i01m01k+1 for t2(|w|) steps.
• If k=mt1(m) then accept if 1i01m0 rejects which we can do quickly as a function of the current input size.
This machine uses time O(t2(n)). If NTIME(t1(n))=NTIME(t2(n)) then there is an equivalent machine Mi using time O(t1(n)).

Since t1(n+1)=o(t2(n)) we have for sufficiently large m,

1i01m0 in L(M) ⇔ 1i01m01 in L(M) ⇔ … ⇔ 1i01m01mt1(m) in L(M) ⇔ 1i01m0 not in L(M)