The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs
Andreas R. Blass, Yuri Gurevich · 2020
We prove the Linear Time Hierarchy Theorems for random access machines and Gurevich abstract state machines. One long-term goal of this line or research isto prove lower bounds for natural linear time problems. 1