Improved simulation of nondeterministic Turing machines
From MaRDI portal
Publication:764330
DOI10.1016/J.TCS.2011.05.018zbMATH Open1253.68129OpenAlexW2064718200MaRDI QIDQ764330FDOQ764330
Authors: Subrahmanyam Kalyanasundaram, Richard J. Lipton, Farbod Shokrieh, Kenneth W. Regan 
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.018
Recommendations
- Improved simulation of nondeterministic Turing machines
- Deterministic simulation of non-deterministic Turing machines (detailed abstract)
- scientific article; zbMATH DE number 4078813
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- Exact computation of the number of accepting paths of an NTM
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Relations Among Complexity Measures
- 3-coloring in time
- Title not available (Why is that?)
- Finding a Minimum Circuit in a Graph
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Improving exhaustive search implies superpolynomial lower bounds
- On Time Versus Space
- Two-Tape Simulation of Multitape Turing Machines
- Non-uniform depth of polynomial time and space simulations.
- Finding a Maximum Independent Set
- Holographic Proofs and Derandomization
- Title not available (Why is that?)
- On time versus space. II
- Title not available (Why is that?)
Cited In (9)
- Improving the efficiency of non-deterministic computations
- Improved simulation of nondeterministic Turing machines
- Deterministic simulation of non-deterministic Turing machines (detailed abstract)
- Exact computation of the number of accepting paths of an NTM
- The hedge: an efficient storage device for Turing machines with one head
- Uniform simulations of nondeterministic real time multitape turing machines
- On efficient deterministic simulation of turing machine computations below logaspace
- An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
- Turing machine and its symbolic simulation
This page was built for publication: Improved simulation of nondeterministic Turing machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764330)
