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. [Lance Fortnow, Steve Homer, [http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf "A Short History of Computational Complexity] ", Bulletin of the European Association for Theoretical Computer Science, The Computational Complexity Column, Number 80, June, 2003] 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.

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 , o, omega$ such that $forall x;f(x) geq x$ , there exists a space bound $S(n)$ such that $DSPACE(f(S(n)) = DSPACE(S(n))$ .

See also

*Blum's speedup theorem

References

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

Gap theorem (disambiguation) — In mathematics, gap theorem may refer to:* The Weierstrass gap theorem. * The Hadamard gap theorem. * The gap theorem of Fourier analysis, a statement about the vanishing of discrete Fourier coefficients for functions that are identically zero on … Wikipedia
Ostrowski–Hadamard gap theorem — In mathematics, the Ostrowski–Hadamard gap theorem is a result about the analytic continuation of complex power series whose non zero terms are of orders that have a suitable gap between them. Such a power series is badly behaved in the sense… … Wikipedia
Info-gap decision theory — is a non probabilistic decision theory that seeks to optimize robustness to failure – or opportuneness for windfall – under severe uncertainty,[1][2] in particular applying sensitivity analysis of the stability radius type[3] to perturbations in… … Wikipedia
Coleman-Mandula theorem — The Coleman Mandula theorem, named after Sidney Coleman and Jeffrey Mandula, is a no go theorem in theoretical physics. It states that the only conserved quantities in a realistic theory with a mass gap, apart from the generators of the Poincaré… … Wikipedia
Coleman–Mandula theorem — The Coleman–Mandula theorem, named after Sidney Coleman and Jeffrey Mandula, is a no go theorem in theoretical physics. It states that space time and internal symmetries cannot be combined in any but a trivial way .[1] The only conserved… … Wikipedia
Adiabatic theorem — The adiabatic theorem is an important concept in quantum mechanics. Its original form, due to Max Born and Vladimir Fock (1928),cite journal |author=M. Born and V. A. Fock |title=Beweis des Adiabatensatzes |journal=Zeitschrift für Physik A… … Wikipedia
Prime number theorem — PNT redirects here. For other uses, see PNT (disambiguation). In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are… … Wikipedia
Fundamental theorem of algebra — In mathematics, the fundamental theorem of algebra states that every non constant single variable polynomial with complex coefficients has at least one complex root. Equivalently, the field of complex numbers is algebraically closed.Sometimes,… … Wikipedia
Prime gap — A prime gap is the difference between two successive prime numbers. The n th prime gap, denoted g n , is the difference between the ( n +1) th and the n th prime number, i.e.: g n = p n + 1 − p n .We have g 1 = 1, g 2 = g 3 = 2, and g 4 = 4. The… … Wikipedia
Semantic gap — The semantic gap characterizes the difference between two descriptions of an object by different linguistic representations, for instance languages or symbols. In computer science, the concept is relevant whenever ordinary human activities,… … Wikipedia

Academic Dictionaries and Encyclopedias

Gap theorem

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Gap theorem

Look at other dictionaries:

Share the article and excerpts

Direct link