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 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, so it applies to time, space, or any other reasonable complexity measure.
Reference:
http://en.wikipedia.org/wiki/Gap_theorem
