Linear speedup theorem
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another k-tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k>1 .[1][2] If the original machine is non-deterministic, then the new machine is also non-deterministic. The concrete constants 2 and 3 in 2n+3 can be lowered, for example, to n+2.[1]
Complexity
Initialization requires 2n+3 steps. In the simulation, 6 steps of N simulate m steps of M. Choosing m>6c produces the running time .
References
- ^ a b Christos Papadimitriou (1994). "2.4. Linear speedup". Computational Complexity. Addison-Wesley.
- ^ Thomas A.Sudkamp (1994). "14.2 Linear Speedup". Languages and Machines: An Introduction to the Theory of Computer Science. Addison-Wesley.