Upward and Downward Diagonalization over Axiomatic Complexity Classes

Abstract

This report considers special cases of the question ""What conditions on u() and t() guarantees that $R^{\Phi}_{t}() \neq $R^{\Phi}_{u}()$?" where $R^{\Phi}_{t}()$ is the class of recursive functions whose $\Phi$ complexity is bounded by t(). In particular the condition $\stackrel{inf}{n\rightarrow\infty} \frac{t(n)}{u(n)} = 0$ and $\stackrel{lim}{n\rightarrow\infty} \frac{t(n)}{u(n)} = 0$ are examined, and it is shown that certain results of Hartmanis, Stearns and Hennis are in one sense the best possible. It is then shown that the diagonalization techniques used in results of this type are of two different sorts, upward and downward. The differences are made precise and very general conditions are found under which each type applies. These conditions widely generalize several well-known results for time and tape complexity measures. In the final section, the report considers some properties of a special class of names for complexity classes. The techniques used in Lemma 3.3 and Theorems 5.1 and 7.1 are new and promise wider application. Also, new results of Borodin and McCreight and Meyer are used, but otherwise the methods are those of Blum.