Verifying whether one-tape Turing machines run in linear time

DOI10.1016/J.JCSS.2019.08.004MaRDI QIDQ2009635zbMATH OpenOpenAlexWikidataFDO

Authors 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

crossing sequencelinear timelower boundsone-tape Turing machinerunning time

Mathematics Subject Classification ID

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

Abstract: We discuss the following family of problems, parameterized by integers $Cgeq2$ and $Dgeq1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$? Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good non-deterministic and co-non-deterministic lower bounds. Specifically, these problems can not be solved in $o(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in $O(q^{C+2})$ non-deterministic time and not in $o(q^{(C-1)/2})$ non-deterministic time by multi-tape Turing machines.

Recommendations

• Verifying time complexity of Turing machines
• An NP-complete language accepted in linear time by a one-tape Turing machine
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• SOFSEM 2004: Theory and Practice of Computer Science
• Theory of one-tape linear-time Turing machines

Cites work

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

Cited in

(6)

• Theory of one-tape linear-time Turing machines
• An NP-complete language accepted in linear time by a one-tape Turing machine
• Verifying time complexity of Turing machines
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• Two Tests for the Linearity of Sequential Machines
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: Verifying whether one-tape Turing machines run in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009635)