Gap theorem explained

See also Gap theorem (disambiguation) for other gap theorems in mathematics.

In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot 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^[2] and Allan Borodin.^{[3] [4]} Although Trakhtenbrot's derivation preceded Borodin's by several years, it was not known nor recognized in the West 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 for which

g(x) \geq x for every, there is a total computable function such that with respect to, the complexity classes 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, 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 DTIME (g(T(n))) = DTIME (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,^[5] and it does not contradict the time hierarchy theorem or space hierarchy theorem.^[6]

See also

• Blum's speedup theorem

Notes and References

1. Lance . Fortnow . Steve . Homer . A Short History of Computational Complexity . https://web.archive.org/web/20051229063702/http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf . dead . 2005-12-29 . Bulletin of the European Association for Theoretical Computer Science . 95–133 . 80 . June 2003.
2. Book: Trakhtenbrot, Boris A.. The Complexity of Algorithms and Computations (Lecture Notes). 1967. Novosibirsk University.
3. Book: Borodin, Allan . Allan Borodin . Fischer . Patrick C. . Ginsburg . Seymour . Harrison . Michael A. . Complexity classes of recursive functions and the existence of complexity gaps . 67–78 . Association for Computing Machinery . Proceedings of the 1st Annual ACM Symposium on Theory of Computing, May 5–7, 1969, Marina del Rey, CA, USA . 1969.
4. Borodin, Allan. Computational complexity and the existence of complexity gaps. Journal of the ACM. 19. 1. 158–174. January 1972 . 10.1145/321679.321691. free. 1813/5899. free.
5. Book: Computing Handbook, Third Edition: Computer Science and Software Engineering. Teofilo. Gonzalez. Teofilo F. Gonzalez . Jorge. Diaz-Herrera. Allen. Tucker. CRC Press. 2014. 9781439898529. Chapter 7: Complexity Theory. Eric W.. Allender. Eric Allender. Michael C.. Loui. Kenneth W.. Regan. 79. Fortunately, the gap phenomenon cannot happen for time bounds t that anyone would ever be interested in. .
6. Book: Zimand, Marius. Computational Complexity: A Quantitative Perspective. 196. North-Holland Mathematics Studies. Elsevier. 2004. 9780080476667. 42. .