Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
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 constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.[1]
- ^ 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.
Previous Page Next Page
