|
See also Gap theorem (disambiguation) for other gap theorems in mathematics. In computational complexity theory the Gap theorem is an important theorem about the complexity of computable functions. The theorem was proved independently by Boris Trakhtenbrot in 1964 and Allan Borodin in 1972. The theorem can be proved by using the Blum axioms without any reference to a concrete computational model.
Gap theorem Given two total computable functions and with then there exists a total computable function with and the complexity classes with boundary function and are identical. | ||||||||
|
| |||||||||
 |
|
| |