Gap theorem

The general form of the theorem is as follows.

Suppose Φ is an abstract (Blum) complexity measure. 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.

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 ${\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))}$.

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]

• Blum's speedup theorem