:''See also
Gap theorem (disambiguation) In mathematics, gap theorem may refer to:
* The Weierstrass gap theorem in algebraic geometry
* The Ostrowski–Hadamard gap theorem on lacunary function
* The Fabry gap theorem on lacunary functions
* The ''gap theorem'' of Fourier analysis, a ...
for other gap theorems in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
.''
In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s.
It essentially states that there are arbitrarily large computable gaps in the hierarchy of
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
es. For any
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
that represents an increase in
computational resource
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
The simplest computational resources are computation time, the number of steps necessary to s ...
s, 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
Boris (Boaz) Abramovich Trakhtenbrot (russian: Борис Авраамович Трахтенброт, he, בועז טרכטנברוט; 19 February 1921 – 19 September 2016) was a Russian-Israeli mathematician in logic, algorithms, theory of co ...
and
Allan Borodin
Allan Bertram Borodin (born 1941) is a Canadian-American computer scientist who is a professor at the University of Toronto.[the West
West is a cardinal direction or compass point.
West or The West may also refer to:
Geography and locations
Global context
* The Western world
* Western culture and Western civilization in general
* The Western Bloc, countries allied with NATO ...](_blank)
until after Borodin's work was published.
Gap theorem
The general form of the theorem is as follows.
:Suppose is an
abstract (Blum) complexity measure. For any
total computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
for which
for every , there is a total computable function such that with respect to , the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
es with boundary functions and
are identical.
The theorem can be proved by using the Blum axioms without any reference to a concrete
computational model
A computational model uses computer programs to simulate and study complex systems using an algorithmic or mechanistic approach and is widely used in a diverse range of fields spanning from physics, chemistry and biology to economics, psychology, ...
, 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
such that
for all , there exists a time bound
such that
.
Because the bound 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 the
time hierarchy theorem
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, ...
or
space hierarchy theorem In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For exampl ...
.
[.]
See also
*
Blum's speedup theorem
In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions.
Each computable function has an infinite number of different program representa ...
References
{{Reflist
Theorems in computational complexity theory