Editing Linear speedup theorem (section)

{{Short description|Speeding up Turing machines by increasing tape symbol complexity}}
In [[computational complexity theory]], the '''linear speedup theorem''' for [[Turing machine]]s states that given any [[real number|real]] ''c''&nbsp;>&nbsp;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 {{nowrap|''f''(''n'')/''c'' + 2''n'' + 3}}, where ''k''&nbsp;>&thinsp;1.<ref name=papadi>{{cite book|author = Christos Papadimitriou|author-link = Christos Papadimitriou| title = Computational Complexity | chapter = 2.4. Linear speedup | publisher = Addison-Wesley | year = 1994}}</ref><ref name=sudkamp>{{cite book|author = Thomas A. Sudkamp|author-link = Thomas A. Sudkamp| title = Languages and Machines: An Introduction to the Theory of Computer Science | chapter = 14.2 Linear Speedup | publisher = Addison-Wesley | year = 1994}}</ref>
If the original machine is [[Non-deterministic Turing machine|non-deterministic]], then the new machine is also non-deterministic.
The constants 2 and 3 in 2''n''&thinsp;+&thinsp;3 can be lowered, for example, to ''n''&thinsp;+&thinsp;2.<ref name=papadi/>

The theorem also holds for Turing machines with 1-way, [[Read-only Turing machine|read-only]] input tape and <math>k\ge 1</math> work tapes.<ref name="WW">{{cite book |last1=Wagner |first1=K. |title=Computational Complexity |last2=Wechsung |first2=G. |date=1986 |publisher=Springer |isbn=978-9027721464}}</ref>

For single-tape Turing machines, linear speedup holds for machines with execution time at least <math>n^2</math>. It provably does not hold for machines with time <math>t(n)\in \Omega(n\log n)\cap o(n^2)</math>.<ref name="WW" />