The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs
Andreas Blass (Partially supported by NSF grant DMS--9505118. Mathematics Department, University of Michigan)
Yuri Gurevich (Partially supported by NSF grant DMS--9505118. Mathematics Department, University of Michigan)
Abstract: 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 is to prove lower bounds for natural linear time problems.
|