Computational Complexity and the Existence of Complexity Gaps
Allan Borodin · Journal of the ACM · 1972
Some consequences of the Blum axioms for step counting functions are investigated.Complexity classes of recursive functions are introduced analogous to the Hartmanis-Stearns classes of recursive sequences.Arbitrarily large "gaps" are shown to occur throughout any complexity hierarchy.