Speedup theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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: