On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
From MaRDI portal
Publication:1168735
DOI10.1016/0304-3975(82)90075-5zbMath0493.68046OpenAlexW2062531583MaRDI QIDQ1168735
Ivan Hal Sudborough, Burkhard Monien
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90075-5
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
On pebble automata ⋮ On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes ⋮ Isomorphisms and 1-L reductions ⋮ On efficient deterministic simulation of turing machine computations below logaspace ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ A survey of space complexity ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ A variant of inductive counting ⋮ Complete problems for space bounded subclasses of NP ⋮ Topological Bandwidth
Cites Work
- An extension of Savitch's theorem to small space bounds
- Space-bounded reducibility among combinatorial problems
- The NP-completeness of the bandwidth minimization problem
- Techniques for separating space complexity classes
- The polynomial-time hierarchy
- Lower bounds on space complexity for contextfree recognition
- Relationships between nondeterministic and deterministic tape complexities
- Relativization of questions about log space computability
- The Hardest Context-Free Language
- Unnamed Item
- Unnamed Item
- Unnamed Item