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:
“She isn’t harassed. She’s busy, and it’s glamorous to be busy. Indeed, the image of the on- the-go working mother is very like the glamorous image of the busy top executive. The scarcity of the working mother’s time seems like the scarcity of the top executive’s time.... The analogy between the busy working mother and the busy top executive obscures the wage gap between them at work, and their different amounts of backstage support at home.”
—Arlie Hochschild (20th century)
“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)