14.2. Relationships between Time and Space Classes

To gain a better understanding of space-bounded computation, let's look at the relationship between time classes and space classes.


TIME(f(n)) and SPACE(f(n))

Definition. TIME(f(n)) is the class of all decision (yes/no) problems that can be solved (deterministically) in time O(f(n)).

Definition. SPACE(f(n)) is the class of all decision (yes/no) problems that can be solved (deterministically) in space O(f(n)).

By definition, a program that loops forever uses infinitely much space.

Notice that we an define P and PSPACE in terms of TIME and SPACE classes.

Definition. P = k > 0TIME(nk).

Definition. PSPACE = k > 0SPACE(nk).


TIME(f(n)) ⊆ SPACE(f(n))

You cannot use more space than time.

Recall that our official model is a Turing machine. A Turing machine can only move its head to the right one cell per step.

So an algorithm that uses time O(f(n)) must also use space O(f(n)). As a consequence,

Theorem. For every function f(n), TIME(f(n)) ⊆ SPACE(f(n)).


SPACE(f(n)) ⊆ c > 1 TIME(cf(n))

The reverse of the observation above does not work. You can use a lot of time using a small amount of space.

Think of a computation that counts up to 2n. It only needs n bits to write down the current value of the counter.

But there are limits.

Theorem. For every function f(n), SPACE(f(n)) ⊆ c > 1 TIME(cf(n)).

Proof. Recall that a program that loops forever uses infinite space. If a program uses space O(f(n)), then it cannot loop forever.

How long can it run without looping forever if it has c⋅f(n) space?

A Turing machine has a tape alphabet; suppose that alphabet contains a symbols. With c⋅f(n) symbols, there are ac⋅f(n) configurations that can be written on the tape.

A Turing machine also has a finite collection of states. Suppose that there are s states. That increases the number of configurations by a factor of s.

Finally, the tape head can be in c⋅f(n) positions.

So the total number of different configurations is sc⋅f(n)⋅ac⋅f(n).

The dominant part is ac⋅f(n) = (ac)f(n).

Choosing d = ac, we see that there are only about d f(n) configurations.

The program cannot run more than that many steps without repeating a configuration. If it repeats a configuration, it is in an infinite loop. ◊