On the structure of one-tape nondeterministic Turing machine time hierarchy

DOI10.1016/0304-3975(85)90165-3zbMath0603.68047OpenAlexW2053772224MaRDI QIDQ1082813

Kojiro Kobayashi

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90165-3

zbMATH Keywords

Kolmogorov complexityCrossing sequencesnondeterministic Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Immunity and pseudorandomness of context-free languages, An NP-complete language accepted in linear time by a one-tape Turing machine, Verifying time complexity of Turing machines, Verifying whether one-tape Turing machines run in linear time, THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA, Theory of one-tape linear-time Turing machines, Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

Cites Work

• On heads versus tapes
• On time hierarchies
• On alternation
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• An information-theoretic approach to time bounds for on-line computation
• Techniques for separating space complexity classes
• Relating refined space complexity classes
• Real time computation
• Tape bounds for time-bounded Turing machines
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Two Tapes are Better than One for Nondeterministic Machines
• Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>
• Two nonlinear lower bounds for on-line computations
• A Hierarchy Theorem for Polynomial-Space Recognition
• On the Computational Complexity of Algorithms
• Relations Between Time and Tape Complexities
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item