Space & Time hierarchy

Space & Time hierarchy theorems

Complexity of an algorithm measures how much of a certain resource the algorithm uses, such as time, space, or number of random bits.

Does more space increase the power of a TM? For instance, for every decidable language, can we construct a TM with a constant size tape that decides this language? The answer is no, because a constant size tape TM can be written as a finite state machine, and we know there are languages that can be recognized by a TM that an FSM cannot.

How much power is granted to a machine by additional resources? Perhaps we get a hierarchy of languages, where each level of the hierarchy is the set of languages that are recognizable by a TM with a certain amount of space.

First, we define formally the notion of the space requirement of computing a function.

Definition. A function f: \mathbb{N} \rightarrow \mathbb{N} is said to be space-constructible if there exists a TM M that on input 1^n outputs f(n) and uses O(f(n)) space. We assume that f(n) \ge \log n.

Theorem (Space Hierarchy). For any space-constructible function f(n), there exists a language L_f such that L_f can be decided by a TM using O(f(n)) space and there does not exist a TM that decides L_f using o(f(n)) space.

Recall the difference between “little-o” and “big-O” for bounding a function. f=O(g) means that f grows at most the rate of g, up to constants; f=o(g) means that f grows strictly slower than g asymptotically. More precisely,

f(n) = O(g(n)) means \exists n_0, c>0 : \forall n \ge n_0, g(n) \le c \cdot f(n)

f(n) = o(g(n)) means \forall c>0, \exists n_0 : \forall n \ge n_0, f(n) \le c\cdot g(n)

For example, the Space Hierarchy theorem implies that a language is recognizable by a TM using n^2 space, but no TM exists that recognizes the language and uses n^{1.99} space.

SPACE(s(n)) = languages accepted by TM’s that use at most s(n) space.

TIME(t(n)) = languages accepted by TM’s that run for at most t(n) steps.

Theorem SPACE(s(n)) \subseteq TIME(C^{s(n)}).

Proof: 

Consider the current “configuration” of a TM, specified by (q, head position, tape contents). Therefore, with space s(n), we can bound the number of configurations as:

\begin{aligned}  \text{\# possible configurations} &\le |Q| \cdot s(n) \cdot |\Gamma|^{s(n)} \\  &= c_1 \cdot s(n) \cdot c_2^{s(n)} \\  &\le c_2^{s(n) + \log n} \\  &\le c^{s(n)}\end{aligned}

Thus we can simulate the NTM using a DTM in c^{s(n)} time by visiting every allowable configuration and checking if it is an accept state.

 

We can now prove the Space Hierarchy theorem.

Proof: (of Space Hierarchy theorem)

Define L_f as the set of TM’s M and strings 1^n such that M has a tape alphabet of constant size and does not accept (\langle M\rangle,1^n) and using space \le f(n) and time \le 2^{f(n)}. The proof then follows from the following two claims.

Claim 1: There exists a TM D that decides L_f using space O(f(n)).

Proof: We construct the following TM D on input (\langle M\rangle, 1^n) (if the input is not in this form, reject):

  1. Mark f(n) space on the tape.
  2. Simulate M on (\langle M\rangle,1^n)
  3. If M tries to use more space, reject.
  4. If time used is \ge 2^{f(n)}, reject.
  5. Else
    1. If M accepts, reject.
    2. If M rejects, accept.

Claim 2: No TM using o(f(n)) space can decide L_f.

Proof: Suppose there exists such a TM M. Consider whether M\in L_f? If M\in L_f, when M run on (\langle M\rangle, 1^n), M is supposed to accept it using o(f(n)) space since M decide L_f, which is contradict to the fact that M\in L_f. And if M\notin L_f the case will be similar. Thus no such TM could exist.

Note that such a contradiction doesn’t happens on D since D uses either >f(n) space or >2^{f(n)} time when simulating itself.

 

The following theorem gives a similar result as the Space Hierarchy Theorem for time, but with a \log factor.

Definition: We say that a function f: \mathbb{N} \rightarrow \mathbb{N}, where f(n) \ge n \log n, is time-constructible if the function that maps 1^n to the binary representation of f(n) is computable in time O(f(n)).

Theorem (Time Hierarchy Theorem): For any time-constructible function f(n), there exists a language L such that L can be decided by a TM using O(f(n)) time and cannot be decided by any TM using o(\frac{f(n)}{log(f(n))}) time.

Proof (of Time Hierarchy Theorem): Consider the following TM B that, in time O(f(n)), decides a language L which we will show is not decidable in o(\frac{f(n)}{\log f(n)}) time.

B(w):

  1. Let n be the length of w.
  2. Compute f(n) using time constructibility, and store the value \lceil f(n)/\log f(n)\rceil in a binary counter. Decrement this counter before each step used in stages 3, 4, and 5. If the counter ever hits 0, REJECT.
  3. If w is not of the form \langle M \rangle 10^* for some TM M, REJECT.
  4. Simulate M on w.
  5. If M accepts, then REJECT. If M rejects, then ACCEPT.

We first need to show that B runs in O(f(n)) steps. Stages 1-3 can be completed in time O(f(n)) by the definition of time-constructibility.

For stages 4 and 5, we need to simulate the operation of M. To simulate M, we store the current state of the machine, the current tape, and the transition function. These objects will need to be constantly updated throughout the simulation, and need to be performed efficiently. We separate B‘s tape into tracks (e.g. even and odd positions), where on one track we store M‘s tape, and on another track, we store the current state of M along with a copy of M‘s transition function.

To keep the simulation efficient, we maintain that the description of M remains near the head of the TM. Whenever the position of M‘s head moves, we move the entire description of M along the second track. Because we consider the size of M to be a constant (not dependent on the input size provided the M), this only adds a constant overhead. Thus, we can simulate the operation of M with only constant overhead: if M runs in g(n) time, then B can simulate it in O(g(n)) time.

When B simulates the operation of M, it must also keep track of the counter at each step. We use a third track to store and update the counter. The length of this counter will be O(\log\big[f(n)/\log f(n)\big]) = O(\log f(n)). Thus updating this counter will require a O(\log f(n)) multiplicative overhead to the simulation of M, which means that the language L we constructed is decidable in O(f(n)) time.

Finally we need to show that no TM can decide L in time o(f(n)/\log f(n)). Suppose for contradiction there existed a TM T that decided L in time o(f(n)/\log f(n)). Since both T and B decide the same language, they should agree on all inputs. Run the TM B on input \langle T \rangle 10^k for k sufficiently large. B will simulate T(\langle T \rangle 10^k) in o(f(n)) steps, and will disagree with T on the same input. Thus the TM T cannot exist.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s