Gap theorem

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.

WikiProject Computer science or the Computer science Portal may be able to help recruit one.

If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

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.^[1] 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 in 1964^[2] and Allan Borodin in 1972.^[3] 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.

[edit] Gap theorem

Given two total computable functions $f$ and $g$ with

$\forall x \; x \leq g(x),$

then there exists a total computable function $h$ with

$\forall x \; f(x) \leq h(x)$

and the complexity classes with boundary function $h$ and $g \circ h$ are identical.

For the special case of time complexity, this can be stated in more modern notation as:

for any total computable function $f \, : \, \omega \,\to\, \omega$ such that $\forall x\;f(x) \geq x$ , there exists a time bound

T (n)

such that

D T I M E (f (T (n)) = D T I M E (T (n))

[edit] See also

Blum's speedup theorem

[edit] References

^ Lance Fortnow, Steve Homer, "A Short History of Computational Complexity", Bulletin of the European Association for Theoretical Computer Science, The Computational Complexity Column, Number 80, June, 2003
^ Boris Trakhtenbrot (1964). "Turing computations with logarithmic delay" (in Russian). Algebra and Logic 3 (4): 33-48.
^ Allan Borodin (January 1972). "Computational complexity and the existence of complexity gaps". Journal of the ACM 19 (1): 158-174. doi:10.1145/321679.321691.