:''See also Gap theorem (disambiguation) for other gap theorems in 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 ...

, 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 d ...

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 ...

es. For any

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 ...

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

g(x) \geq x

for every , there is a total computable function such that with respect to , the

es with boundary functions and

g \circ t

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

g : \, \omega \,\to\, \omega

such that

g(x) \geq x

for all , there exists a time bound

T(n)

such that

\mathsf(g(T(n))) = \mathsf(T(n))

. 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, ...

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 ...

References

{{Reflist Theorems in computational complexity theory