Temporal and Spatial Complexity
Complexity Theory
It is one thing to say that a function is Turing Machine Computable, quite another to say that the function can be computed by a Turing Machine in the next hour, day, year, millenium, or, indeed, before the heat-death of the Universe. Very roughly, this is the problem of Temporal Complexity. Temporal Complexity involves the bounds on the time it takes for a given Turing Machine to compute its input.
Spatial Complexity involves the bounds on the amount of space a Turing Machine requires to compute its input, where space is crudely understood as the length of the Turing Machine's tape. A Turing Machine may require more space than exists in the known Universe, for example.
Computability Theory establishes the class of functions that are logically computable by the Universal Turing Machine. Temporal and Spatial Complexity Theory establishes the class of functions that are physically computable--that is, computable in the space and time of the Universe. To be sure, we're most interested in those computable in much less than the space and time of the Universe.
Temporal Complexity
The theory of Temporal Complexity asks a very simple question: how much time does a Turing Machine require? For a Turing Machine which fails to halt on its input the answer is an infinite amount of time, so henceforth we shall only consider Turing Machines which halt on all inputs. Furthermore, let us suppose that each operation - move left, move right, erase, write a character - takes no more and no less time than any other operation. The amount of time a Turing Machine takes to halt on a given input will then be exactly proportional to the number of operations it performs (or, more colloquially, the number of steps it takes), which allows us to use the number of steps as an (integer) measure of time.
One can imagine three approaches to analyzing Temporal Complexity. An optimist might be inclined to conduct a best-case analysis to discover the least number of steps a Turing Machine takes on various input strings. A pessimist would be more interested in conducting a worst-case analysis so as to find an upper bound on the number of steps. Finally, an average-case analysis might be conducted to find out the average number of steps required. Following Sipser (1997, pp. 225ff), let us be pessimists and define the running time of a deterministic Turing Machine as a function from the lengthof its input to the maximum number of steps the Turing Machine takes to halt on its input.25 Where n is the length of its input, the Turing Machine's running time is given by f(n). The pessimistic definition of running time for a nondeterministic Turing Machine is only slightly more complicated. Let the running time f(n) for a nondeterministic Turing Machine which halts on all inputs - specifically,every branch halts on every input - be the maximum number of steps required on any branch of computation for any input of length n. Thus the run-time of a nondeterministic Turing Machine (parent) is set to be the run-time of its slowest child.
In general, we expect f(n) to be large for large n, since the longer the input, the greater the number of steps a Turing Machine will require to either reject or compute the input. Taking our pessimism to the next logical step, we reinterpret the question of how long a Turing Machine takes to be the question, how quickly does f grow?
It turns out that f can grow either quickly or astonishingly quickly. Turing Machines which run in polynomial time have running times that are polynomial functions of the length of their input:f(n) = 2n3 + 8n2 + 6n + 21, for example. f grows fast, but not unmanageably fast. Turing Machines which only differ in running time by some polynomial factor (n2, 3n4, or what have you) are said to be polynomially equivalent. Of course, only differing by some polynomial factor may seem a cavalier way to put it, since n6 grows much faster than n2 as n increases. But the differences between polynomially equivalent Turing Machines are insignificant when compared to Turing Machines which run in exponential time. Turing Machines which run in exponential time have running times that are exponential functions of the length of their input: f(n) = 3n, for example. f grows astonishingly fast.
Consider that a modest input length of n = 100 results in a run-time of 10000 steps for a Turing Machine which halts on the input in the polynomial time of f(n) = n2, while a Turing Machine requiring an exponential running time of f(n) = 2n would take 1.26765x1030 steps to halt on the same input. Loosely speaking, functions which are computable in polynomial time are for the most part manageable by ordinary computing machinery; functions which are only computable in exponential time require at the very least strict limitations on input length if ordinary computing machinery is employed.27 A splendid example of a function requiring exponential running time is a brute-force search algorithm which searches through an exponentially large space of solutions by examining - hence, brute-force - each and every possible solution.
The reason for constructing a taxonomy of Turing Machines now becomes apparent. Every deterministic multi-tape Turing Machine which runs in polynomial time f(n) has an equivalent deterministic single-tape Turing Machine which runs in f2(n) time (Sipser 1997, p. 232). Deterministic multi-tape Turing Machines are thus polynomially equivalent to deterministic single-tape Turing Machines which run in polynomial time. Not so for nondeterministic Turing Machines. Every nondeterministic single-tape Turing Machine which runs in polynomial time f(n) has an equivalent deterministic single-tape Turing Machine which runs in 2f(n) time (Sipser 1997, p. 233). Where thereis at most a polynomial difference in running time between single and multi-tape deterministic Turing Machines which compute the same function, there is at most an exponential difference in running time between single-tape deterministic Turing Machines and single-tape nondeterministic Turing Machines which compute the same function. The upshot is that one's choice of computational model becomes extremely important where temporal complexity is concerned. Choice of computational model is less important where spatial complexity is concerned.
Spatial Complexity
Recall that our initial description of a Turing Machine involved a boxcar trundling to and fro across a linear tape of indefinite length. The amount of space required by a Turing Machine is understood to be the amount of tape (=number of cells) it requires to operate on a given input. Suppose we have a deterministic Turing Machine which halts on all inputs, and suppose we are just as pessimistic about spatial requirements as we are about temporal requirements. Then the running size or spatial complexity of the Turing Machine is a function g from the length of any input n to the greatest number of cells scanned. For example, a deterministic single-tape Turing Machine which reads n unbroken 1's and halts on the right-most 1 has a running size of n + 2: g(n) = n + 2.31
The (pessimistic) definition of running size for a nondeterministic Turing Machine parallels the definition of running time. Suppose we have a nondeterministic Turing Machine such that all branches halt on all inputs. Then the running time g(n) of the Turing Machine on input of length n is the greatest number of cells scanned on any branch.
According to Savitch's Theorem (Sipser 1997, p. 279), the (possibly) extraordinary difference in running time between nondeterministic Turing Machines and their deterministic counterparts is not mirrored by a similar difference in running size, since any nondeterministic Turing Machine with a running space of g(n) has an equivalent deterministic Turing machine with a running space of g2(n).
Where there is at most an exponential difference between deterministic and nondeterministic Turing Machines in running time, there is at most a polynomial difference between deterministic and nondeterministic Turing Machines in running size. Granted, a polynomial difference can be exceptional when it comes to budgeting memory costs for running a particular algorithm. But such costs are relatively minor when compared to the difference in processing costs between polynomial and exponential-time algorithms.
from Sipser, M. 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company.