Improved simulation of nondeterministic Turing machines

DOI10.1016/J.TCS.2011.05.018MaRDI QIDQ764330zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmssimulationcomplexitydeterminismnondeterminismTuring machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3765164 (Why is no real title available?)
• scientific article; zbMATH DE number 1332665 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• 3-coloring in time
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Finding a Maximum Independent Set
• Finding a Minimum Circuit in a Graph
• Holographic Proofs and Derandomization
• Improving exhaustive search implies superpolynomial lower bounds
• Non-uniform depth of polynomial time and space simulations.
• On Time Versus Space
• On time versus space. II
• Relations Among Complexity Measures
• Two-Tape Simulation of Multitape Turing Machines

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)