Computational Complexity

Wednesday, July 14, 2004

 
Time and Space Hierarchies

Posted by Lance

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.

8:40 AM #

1.  Anonymous says:  
   
   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
   

   3:42 PM, July 14, 2004

2.  Anonymous says:  
   
   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].
   

   8:54 PM, July 14, 2004

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

   4:23 PM, July 20, 2004