7.3. Space-time theorems

Some relation of time and space complexity classes can be expressed by the following theorems.

Theorem 7.22.

Let  be a monotone increasing function. Then 
. 

Proof

Let . Then there exists a deterministic Turing machine with time complexity , such that . Let an input word of length . Since a Turing machine can write at most one new cell in every step, thus the size of tape used during the computation on the input cannot be greater, than the number of steps, i.e. . This means that , i.e. . Hence, by definition, , i.e. . ✓

The relation in opposite direction is a bit more complex.

Theorem 7.23.

Let  be a monotone increasing function and let .
Then there exists a constant , such that . 

Proof

Let be a deterministic Turing machine with space complexity , such that .

Assume that is a word of length , such that terminates on it.

By the properties of , it means that during the computation on the input if , then for all .

If there exists such that , then the Turing machine never terminates, since it implies or in more general , which means that the configurations in the computation of the Turing machine is periodic.

Hence, all configurations in the sequence are different, i.e. cannot be greater than the number of configurations having tape content not exceeding .

Let be the cardinality of . The number of words over of length exactly is , i.e. the number of words of length at most is .

If the cardinality of is , then the number of different configurations is at most , since a configuration may contain different state, different tape content and different read-write head position.

Since is constant, thus , if is large enough. Similarly , if is large enough. Furthermore, for large enough 's we have .

From the three inequality we get .

Let . By the above statements, for the length of the computation we have .

We found, that if terminates on an input word, it decides in at most time, whether it is in or not. The only problem is that not necessarily terminates on all input. To solve this problem construct the Turing machine :

The Turing machine is basically the same as , but it has a second tape on which stores all configurations after executing it (separated by some separation sign). Before turning to the execution of the next step, it checks whether there are the same configuration twice on the second tape. If the answer is yes, then has an infinite loop, i.e. it does not accept its input. Then terminates with "no" answer.

Of course, the computation of is longer than the computation of , since it should scan tape before every step. However, the length of the content of the second tape is not greater than the number of different configurations multiplied by the maximal size of a configuration, i.e. less than , which can be bounded by , if is large enough. Thus if the time complexity of is , then . Since , thus for sufficiently large 's we have , for some . Let . With this the inequality holds if is large enough, i.e. , whence . ✓