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 is said to be space-constructible if there exists a TM that on input outputs and uses space. We assume that .
Theorem (Space Hierarchy). For any space-constructible function , there exists a language such that can be decided by a TM using space and there does not exist a TM that decides using space.
Recall the difference between “little-o” and “big-O” for bounding a function. means that grows at most the rate of , up to constants; means that grows strictly slower than asymptotically. More precisely,
For example, the Space Hierarchy theorem implies that a language is recognizable by a TM using space, but no TM exists that recognizes the language and uses space.
languages accepted by TM’s that use at most space.
languages accepted by TM’s that run for at most steps.
Consider the current “configuration” of a TM, specified by head position, tape contents. Therefore, with space , we can bound the number of configurations as:
Thus we can simulate the NTM using a DTM in 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 as the set of TM’s M and strings such that has a tape alphabet of constant size and does not accept and using space and time . The proof then follows from the following two claims.
Claim 1: There exists a TM that decides using space .
Proof: We construct the following TM on input (if the input is not in this form, reject):
- Mark space on the tape.
- Simulate on
- If tries to use more space, reject.
- If time used is , reject.
- If accepts, reject.
- If rejects, accept.
Claim 2: No TM using space can decide .
Proof: Suppose there exists such a TM . Consider whether ? If , when run on , is supposed to accept it using space since decide , which is contradict to the fact that . And if the case will be similar. Thus no such TM could exist.
Note that such a contradiction doesn’t happens on since uses either space or time when simulating itself.
The following theorem gives a similar result as the Space Hierarchy Theorem for time, but with a factor.
Definition: We say that a function , where , is time-constructible if the function that maps to the binary representation of is computable in time .
Theorem (Time Hierarchy Theorem): For any time-constructible function , there exists a language such that can be decided by a TM using time and cannot be decided by any TM using time.
Proof (of Time Hierarchy Theorem): Consider the following TM that, in time , decides a language which we will show is not decidable in time.
- Let be the length of .
- Compute using time constructibility, and store the value in a binary counter. Decrement this counter before each step used in stages 3, 4, and 5. If the counter ever hits , REJECT.
- If is not of the form for some TM , REJECT.
- Simulate on .
- If accepts, then REJECT. If rejects, then ACCEPT.
We first need to show that runs in steps. Stages 1-3 can be completed in time by the definition of time-constructibility.
For stages 4 and 5, we need to simulate the operation of . To simulate , 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 ‘s tape into tracks (e.g. even and odd positions), where on one track we store ‘s tape, and on another track, we store the current state of along with a copy of ‘s transition function.
To keep the simulation efficient, we maintain that the description of remains near the head of the TM. Whenever the position of ‘s head moves, we move the entire description of along the second track. Because we consider the size of to be a constant (not dependent on the input size provided the ), this only adds a constant overhead. Thus, we can simulate the operation of with only constant overhead: if runs in time, then can simulate it in time.
When simulates the operation of , 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 . Thus updating this counter will require a multiplicative overhead to the simulation of , which means that the language we constructed is decidable in time.
Finally we need to show that no TM can decide in time . Suppose for contradiction there existed a TM that decided in time . Since both and decide the same language, they should agree on all inputs. Run the TM on input for sufficiently large. will simulate in steps, and will disagree with on the same input. Thus the TM cannot exist.