Theorems on the time hierarchy for random access machines

A. G. Ivanov

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VIII, Tome 88 (1979), pp. 62-72

Résumé

Time hierarchy for some types of random access machines (RAM) is studied. The main result states that if $T(n)$ is a function computable by а RAM in time $\widetilde T(n)$ then there is a set $A$ of strings in the alphabet $\{0,1\}$ that can be recognized by some RAM in time $21T(n)+6\widetilde T(n)+25n$, but no RAM recognizes. A in time $T(n)$. As a consequence of this result we obtain a hierarchy theorem which is finer than that of Cook and Eechow. We introduce a set $\mathscr T$ of functions which contains a lot of interesting functions (such as polynoms of degree $>1$, $n\log n$, $2^n$, etc.). For the set $\mathscr T$ we show that for any function $T(n)\in\mathscr T$ and any $c>1$ there exists a set that can be recognized by some RAM in time $c\cdot T(n)$, but no RAM recognizes it in time $T(n)$. We also introduce RAM with register length restrictions. Some results are given which compare the run times for recognizing sets using RAM and RAM with register length restrictions.