On the structure of one-tape nondeterministic Turing machine time hierarchy
From MaRDI portal
Publication:1082813
DOI10.1016/0304-3975(85)90165-3zbMath0603.68047OpenAlexW2053772224MaRDI QIDQ1082813
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
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
