Complexity classes

For any integer function f let TIME(f(n)) denote the class of all languages that can be accepted by a (deterministic) Turing machine that halts within cf(n)+k steps on every input of length n. Here c and k are constants that depend on the machine, but not on the input string. Their role is just to say that in measuring time complexity classes we don't care for a constant factor and constant number of steps. Likewise NTIME(f(n)) denotes the class of all languages that can be accepted by a nondeterministic Turing machine that, for certain constants c and k, halts within cf(n)+k steps on every input of length n.

SPACE(f(n)) is the class of languages hat can be accepted by a (deterministic) Turing machine with a read-only input tape and a work tape, that visits never more than f(n) cells of its work tape. NSPACE(f(n)) is defined likewise, using nondeterministic machines.

Theorem: SPACE(cf(n)+k) = SPACE(f(n)) and NSPACE(cf(n)+k) = NSPACE(f(n)) for any constants c > 0 and k > 0.

This is the case because a finite amount of tape cells can be simulated by states in the control space of a Turing machine. Moreover, the space needed by a Turing machine can be reduced by a constant factor when representing blocks of tape cells by single tape cells, thereby multiplying the size of the tape alphabet.

Thus also in the space complexities constant factors and constant numbers of tape cells do not matter.
As indicated in class, a similar account can be given for time complexity (instead of saying that constants do not matter).
Time complexities smaller than n are not very useful, as the least a Turing machine should do is reading its input, which costs n steps. In the definition of space complexity, the distinction between the input tape and the work tape is only relevant for complexities f(n) < n. It allows us to define space complexities smaller than n in a meaningful way. For space complexities > n one could equivalently use the number of space cells on a single tape that starts with input n.

Some relations between the complexity classes are:

TIME(f(n)) SPACE(f(n)) NSPACE(f(n)) and TIME(f(n)) NTIME(f(n)) NSPACE(f(n)).
If language L is in NTIME(f(n)), then there is a constant d such that L in TIME(d^f(n)).
If f(n) log(n) then NSPACE(f(n)) SPACE(f(n)²).
If language L is in SPACE(f(n)) with f(n) log(n), then there is a constant d such that L is in TIME(d^f(n)).

P is the union of the complexity classes TIME(n^k) for k a constant.
NP is the union of the complexity classes NTIME(n^k) for k a constant.
EXPTIME is the union of the complexity classes TIME(2^{n^k}) for k a constant.
PSPACE is the union of the complexity classes SPACE(n^k) for k a constant.
NPSPACE is the union of the complexity classes NSPACE(n^k) for k a constant.
EXPSPACE is the union of the complexity classes SPACE(2^{n^k}) for k a constant.
L is SPACE(log(n)).
NL is NSPACE(log(n)).

We have L NL P NP PSPACE = NPSPACE EXPTIME EXPSPACE.

Rob van Glabbeek

rvg@cs.stanford.edu