Speedup theorem

For speedup theorems in proof theory, see Gödel's speed-up 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.

The linear speedup theorem for Turing machines shows that the space and time requirements of a Turing machine solving a decision problem can be reduced, roughly speaking, by any multiplicative constant factor.

Blum's speedup theorem provides speedup by any computable function (not just linear, as in the previous theorem). Given the desired speedup function, it deduces the existence of a decision problem such that any algorithm solving it can be sped up.