“Speedup theorem”的意思、由来-开放百科全书

词条

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

1 : Theorems in computational complexity theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。