Editing Speedup theorem

{{Short description|Computational theorem}}
{{for|the theorem that some mathematical proofs can be drastically shortened in stronger axiom systems|Gödel's speed-up theorem}}
{{unreferenced|date=August 2020}}
In [[computational complexity theory]], a '''speedup theorem''' is a [[theorem]] that for any [[algorithm]] (of a certain class) demonstrates the existence of a more [[efficient algorithm]] solving the same problem. 

Examples:
*[[Linear speedup theorem]], that the space and time requirements of a [[Turing machine]] solving a decision problem can be reduced by a multiplicative constant factor.
*[[Blum's speedup theorem]], which provides speedup by any computable function (not just linear, as in the previous theorem).

==See also==
* [[Amdahl's law]], the theoretical speedup in latency of the execution of a task at a fixed workload that can be expected of a system whose resources are improved.

==References==
{{Reflist}}

{{comp-sci-stub}}

[[Category:Theorems in computational complexity theory]]