# 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.