An NP-complete language accepted in linear time by a one-tape Turing machine

DOI10.1016/0304-3975(91)90054-6zbMath0745.68059OpenAlexW2046523441MaRDI QIDQ1183577

Pascal Michel

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90054-6

zbMATH Keywords

one-tape nondeterministic Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Weight-reducing Turing machines, Two-way automata and length-preserving homomorphisms, One-way reversible and quantum finite automata with advice, 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, Converting nondeterministic two-way automata into small deterministic linear-time machines

Cites Work

• On the structure of one-tape nondeterministic Turing machine time hierarchy
• On alternation
• Computational Complexity of One-Tape Turing Machine Computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item