An NP-complete language accepted in linear time by a one-tape Turing machine
From MaRDI portal
Publication:1183577
DOI10.1016/0304-3975(91)90054-6zbMath0745.68059MaRDI QIDQ1183577
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
68Q25: Analysis of algorithms and problem complexity
Related Items
Two-way automata and length-preserving homomorphisms, Weight-reducing Turing machines, One-way reversible and quantum finite automata with advice, Theory of one-tape linear-time Turing machines, Verifying whether one-tape Turing machines run in linear time, Converting nondeterministic two-way automata into small deterministic linear-time machines, THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
Cites Work