Verifying whether one-tape Turing machines run in linear time

DOI10.1016/j.jcss.2019.08.004zbMath1436.68106arXiv1312.0496OpenAlexW2967571932WikidataQ127356913 ScholiaQ127356913MaRDI QIDQ2009635

David Gajser

Publication date: 29 November 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.0496

zbMATH Keywords

lower boundslinear timerunning timecrossing sequenceone-tape Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Verifying time complexity of Turing machines
• A Turing machine time hierarchy
• Nontrivial lower bounds for the least common multiple of some finite sequences of integers
• Theory of one-tape linear-time Turing machines
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• An NP-complete language accepted in linear time by a one-tape Turing machine
• Arithmetical hierarchy and complexity of computation
• Some combinatorial game problems require Ω( n ^k ) time
• Separating Nondeterministic Time Complexity Classes
• Computational Complexity of One-Tape Turing Machine Computations
• One-tape, off-line Turing machine computations