From Wikipedia, the free encyclopedia
In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same problem. It may refer to:
- 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).
It may also refer to:
- Gödel's speed-up theorem, showing that some mathematical proofs can be drastically shortened in stronger axiom systems
|This disambiguation page lists mathematics articles associated with the same title.
If an internal link led you here, you may wish to change the link to point directly to the intended article.