Speedup theorem

For the theorem that some mathematical proofs can be drastically shortened in stronger axiom systems, see Gödel's speed-up theorem.

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. ^[1]

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

1. Blum, Manuel (1967-04-01). "A Machine-Independent Theory of the Complexity of Recursive Functions". J. ACM. 14 (2): 322–336. doi:10.1145/321386.321395. ISSN   0004-5411.