Gap theorem

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.

  1. ^ Fortnow, Lance; Homer, Steve (June 2003). "A Short History of Computational Complexity" (PDF). Bulletin of the European Association for Theoretical Computer Science (80): 95–133. Archived from the original (PDF) on 2005-12-29.
  2. ^ Trakhtenbrot, Boris A. (1967). The Complexity of Algorithms and Computations (Lecture Notes). Novosibirsk University.
  3. ^ Borodin, Allan (1969). "Complexity classes of recursive functions and the existence of complexity gaps". In Fischer, Patrick C.; Ginsburg, Seymour; Harrison, Michael A. (eds.). Proceedings of the 1st Annual ACM Symposium on Theory of Computing, May 5–7, 1969, Marina del Rey, CA, USA. Association for Computing Machinery. pp. 67–78.
  4. ^ Borodin, Allan (January 1972). "Computational complexity and the existence of complexity gaps". Journal of the ACM. 19 (1): 158–174. doi:10.1145/321679.321691. hdl:1813/5899.