Gap theorem

In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions.^[1]

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

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 proved independently by Boris Trakhtenbrot^[2] and Allan Borodin.^[3][4] Although Trakhtenbrot's derivation preceded Borodin's by several years, it was not known nor recognized in the West until after Borodin's work was published.

Statement

As an introductory example, suppose that we are considering time-complexity of a certain specific Turing machine model. The ${\displaystyle \operatorname {TIME} (n^{2})}$ is the set of total computable functions, such that there exists some ${\displaystyle \varphi }$ implementation of the function that computes it in time ${\displaystyle \leq n^{2}}$ given an input size of ${\displaystyle n}$.

In general, any total computable function ${\displaystyle t}$ defines some ${\displaystyle \operatorname {TIME} (t(n))}$ time-complexity class, and we expect that if ${\displaystyle t'(n)>t(n)}$, then ${\displaystyle \operatorname {TIME} (t'(n))}$ should be larger than ${\displaystyle \operatorname {TIME} (t(n))}$. The gap theorem states that this is not necessarily so. Indeed, for any total computable ${\displaystyle g}$ such that ${\displaystyle g(n)>n}$ for all ${\displaystyle n}$, there exists some total computable function ${\displaystyle t}$, such that ${\displaystyle \operatorname {TIME} (t(n))=\operatorname {TIME} (g(t(n)))}$. Intuitively, adding compute time is might not allow us to compute more functions.

More generally, suppose Φ is an abstract (Blum) complexity measure, then for any total computable function g for which ${\displaystyle g(x)\geq x}$ for every x, there is a total computable function t such that with respect to Φ, the complexity classes with boundary functions t and ${\displaystyle g\circ t}$ are identical.

Implications

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

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

Similarly for the special case of space complexity.

Because the bound ⁠${\displaystyle 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,^[5] and it does not contradict the time hierarchy theorem or space hierarchy theorem.^[6]

See also

• Blum's speedup theorem