Improved simulation of nondeterministic Turing machines

DOI10.1016/j.tcs.2011.05.018zbMath1253.68129OpenAlexW2064718200MaRDI QIDQ764330

Richard J. Lipton, Farbod Shokrieh, Subrahmanyam Kalyanasundaram, 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

complexityalgorithmsdeterminismsimulationTuring machinesnondeterminism

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On time versus space. II
• Improving exhaustive search implies superpolynomial lower bounds
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• On Time Versus Space
• Finding a Maximum Independent Set
• Finding a Minimum Circuit in a Graph
• Relations Among Complexity Measures
• 3-coloring in time
• Two-Tape Simulation of Multitape Turing Machines
• Holographic Proofs and Derandomization
• Fundamentals of Computation Theory