In computational complexity theory the Gap Theorem is a major theorem about the complexity of computable functions.
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 first discovered and proved by Boris Trakhtenbrot in 1964 who published it in Russian as a result of which it received little attention in the Cold War era. Eight years later, the same theorem was published by Allan Borodin in 1972 in English and received widespread attention and as a result of which was named Borodin's Gap Theorem.
Read more about Gap Theorem: Gap Theorem
Famous quotes containing the words gap and/or theorem:
“the gap of today filling itself
as emptiness is distributed
in the idea of what time it is
when that time is already past”
—John Ashbery (b. 1927)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)