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 between ideals and actualities, between dreams and achievements, the gap that can spur strong men to increased exertions, but can break the spirit of others—this gap is the most conspicuous, continuous land mark in American history. It is conspicuous and continuous not because Americans achieve little, but because they dream grandly. The gap is a standing reproach to Americans; but it marks them off as a special and singularly admirable community among the world’s peoples.”
—George F. Will (b. 1941)
“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)