Gap theorem

See also Gap theorem (disambiguation) for other gap theorems in mathematics.

In computational complexity theory the Gap Theorem is a major theorem about the complexity of computable functions.

It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes. For any computable function that represents an increase in computational resources, one can find a resource bound such that the set of functions computable within the expanded resource bound is the same as the set computable within the original bound.

The theorem was first discovered and proved by Boris Trakhtenbrot in 1964 who published it in Russian as a result of which it received little attention in the Cold War era. The theorem was published by Allan Borodin in 1972 in English and received widespread attention and as a result of which was named Borodin's Gap Theorem.

Gap theorem

The general form of the theorem is as follows.

Suppose $\Phi$ is an abstract (Blum) complexity measure. For any total computable function g for which $g(x)\geq x$ for every $\,x$, there is a total computable function t such that with respect to $\Phi$, the complexity classes with boundary functions $t$ and $g\circ t$ are identical.

The theorem can be proved by using the Blum axioms without any reference to a concrete computational model, so it applies to time, space, or any other reasonable complexity measure.

For the special case of time complexity, this can be stated more simply as:

for any total computable function $g\,:\,\omega \,\to \,\omega$ such that $g(x)\geq x$ for all $\,x$, there exists a time bound $T(n)$ such that $DTIME(g(T(n)))=DTIME(T(n))$.

Because the bound T(n) may be very large (and often will be nonconstructible) the Gap Theorem does not imply anything interesting for complexity classes such as P or NP, and it does not contradict time hierarchy theorem or space hierarchy theorem.

See also

• Blum's speedup theorem