Gap theorem

[1] It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes.

The theorem was proved independently by Boris Trakhtenbrot[2] and Allan Borodin.

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.

For the special case of time complexity, this can be stated more simply as: Because the bound ⁠

⁠ may be very large (and often will be nonconstructible) the Gap Theorem does not imply anything interesting for complexity classes such as P or NP,[5] and it does not contradict the time hierarchy theorem or space hierarchy theorem.