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)
a contradiction.

3 comments:

  1. Dear Lance,

    I always see these results in the first few sections of any complexity text. I am curious about other resuts that use the Hierarchy Theorems. For example, the DTIME hierarchy shows that P is a proper subset of EXP. What else can be said with these theorems? They seem quite applicable, and it would be nice to know about other results stem from them. Also, maybe you could do a post on the Polynomial Hierarchy since I have yet to find a lucid explanation of what that is all about. Thanks!

    Steve Orzel
    phloam@myrealbox.com

    ReplyDelete
  2. I'm curious about the log t1(n) term in the DTIME hierarchy. Is this a tight bound, or is it open as to whether this term can be reduced or eliminated? Sipser mentions in passing that this is an open question, but he used a 1-tape TM model in his exposition. I understand that if the number of tapes are fixed for some k >= 2, that the log t1(n) term can be eliminated altogether [Furer 1982].

    ReplyDelete
  3. Actually, the name should by (in Tex) \v{Z}\'{a}k (hacek over Z is missing). The Czech language is strange:-)

    ReplyDelete