On eliminating nondeterminism from Turing machines which use less than logarithm worktape space

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

zbMATH Keywords

graph accessibility problem

Mathematics Subject Classification ID

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