Speedup theorem
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 article is issued from Wikipedia - version of the Tuesday, July 02, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.