Ordinal Hierarchies and Naming Complexity Classes
Leonard J. Bass, Paul R. Young · Journal of the ACM · 1973
The relationship between computational complexity and hierarchies of computable Functions is explored.It is shown that known results of hierarchy theory have interesting applications to the Blum theory of computational complexity and, conversely, the Blum theory has applications to hierarchy theory.For example, it is shown that the Blum Speed-up Theorem guarantees the existence of nondegenerate hierarchies of computable functions through all the Church-Kleene constructive ordinal numbers without obtaining all total recursive functions in the hierarchy.In the other direction, a theorem of Kreisel and Parikh on the nonuniqueness of hierarchies forces a number of "irregularities" in the McCreight-Meyer notion of "class-determining measured sets."A variation of the well-known Borodin-Constable Gap Theorem is presented.In toto, still more evidence is presented for the claim originally advanced by Young that it is reasonable to expect an interplay between theories of computational complexity and known results in "pure" reeursion theory.