Nearly Linear Time
- Yuri Gurevich ,
- Saharon Shelah
Symposium on Logical Foundations of Computer Science in Pereslavl-Zalessky, USSR Springer Lecture Notes in Computer Science 363 |
The notion of linear time is very sensitive to machine model. In this connection we introduce and study class NLT of functions computable in nearly linear time n(log n)O(1) on random access computers or any other “reasonable” machine model (with the standard multitape Turing machine model being “unreasonable” for that low complexity class). This gives a very robust approximation to the notion of linear time. In particular, we give a machine-independent definition of NLT and a natural problem complete for NLT.