ON THE NOTION OF LINEAR TIME COMPUTABILITY
Erich Grädel · International Journal of Foundations of Computer Science · 1990
To capture the informal concept of linear time computability, we propose and discuss the class TIME(n 1+ ), consisting of all functions which are computable by a Successor RAM with exponent at most one; the exponent of a function is the infimum of all rational numbers r such that the function is computable in time O(n r ). This class properly contains the class NLT (“Nearly Linear Time”)—proposed by Gurevich and Shelah—which contains all functions computable by a Successor RAM in time O(n(log n) k ) for some k∈N. Both classes are very robust under changes of the underlying machine model: using the same time bounds they can be defined by Random Access Computers, Storage Modification Machines, Kolmogorov algorithms, Random Access Turing machines etc.; this distinguishes them from similar classes defined by ordinary Turing machines. However, we show that TIME(n 1+ ) can be defined e.g. by multi-dimensional Turing machines or by Turing machines which can jump; this is probably not true for NLT. Furthermore we consider two notions of completeness for TIME(n 1+ ) and construct complete problems. These problems are based on restrictions of Gurevich’s function logic for P.