Complexity Definitions and Results

Turing Machine Computable Functions

The class of Turing Machine Computable Functions is infinite but denumerable--i.e., it can be put in one-to-one correspondence with the Natural Numbers, 0, 1, 2, 3,...

The class of functions is non-denumerably infinite, thus there are many more functions that are not Turing Machine Computable than are. Consider, for example, the famous Halting Problem:

Let h(m,n) = 1 if Turing Machine m in the enumeration of Turing Machines halts on input n, 0 otherwise. h is not Turing Machine Computable, so if the Church-Turing Thesis is true, h is not solvable.

Put another way, if the Church-Turing Thesis is true there is no way to verify that an arbitrary program will compute arbitrary input.

The General Problem of Complexity and Computability

Within the class of Turing Computable Functions (alternatively, the class of Solvable Functions if the Church-Turing Thesis is true) there are further distinctions to be drawn in terms of the time and space requirements for computation.

Temporal Complexity

The time complexity of a halting Turing Machine TM is a function f(n) that maps any input of length n to the greatest number of steps required to compute the input. TM is a said to be an f(n)-time Turing Machine.

Where f(n) is bounded by a polynomial function, TM is said to be a polynomial-time Turing Machine. Where f(n) is bounded by an exponential function, TM is said to be an exponential-time Turing Machine.

Every function computable by a non-deterministic Turing Machine in polynomial time is computable by a deterministic Turing Machine in exponential time.

Polynomial differences in time are small, whereas exponential differences in time are large.

Define P to be the class of functions computable in polynomial time by a deterministic Turing Machine, and define NP to be the class of functions computable by a non-deterministic Turing Machine in polynomial time. Then the puzzle is whether P = NP.

Spatial Complexity

The space complexity of a halting Turing Machine TM is a function g(n) that maps any input of length n to the greatest number of cells required to compute the input. TM is said to be a g(n)-space Turing Machine.

Unlike time complexity, it turns out that there exists a deterministic Turing Machine with polynomial-bounded space complexity that computes every function computable by a non-deterministic Turing Machine. Thus an analog of the P = NP question does not arise for spatial complexity. Nevertheless, spatial complexity sets an important bound on the class of physically computable functions.