ON THE NOTION OF LINEAR TIME COMPUTABILITY

DOI10.1142/S0129054190000217zbMath0732.68040OpenAlexW2030147970MaRDI QIDQ3358229

Erich Grädel

Publication date: 1990

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054190000217

zbMATH Keywords

multi- dimensional Turing machinesKolmogorov algorithmslinear time computabilityRandom Access ComputersRandom Access Turing machinesStorage Modification Machines

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Algebraic and logical characterizations of deterministic linear time classes, Graph properties checkable in linear time in the number of vertices, A descriptive complexity approach to the linear hierarchy., On quasilinear-time complexity theory, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, Nonerasing, counting, and majority over the linear time hierarchy