Teorema da aceleração
Aspeto
![]() |
Esta é uma página de desambiguação que lista os artigos que podem ser associados a um ou vários títulos. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/20px-Disambig_grey.svg.png)
- Na teoria da complexidade computacional, um teorema da aceleração é um teorema que considera algum algoritmo que resolve um problema e demonstre a existência de um algoritmo mais eficiente que resolve o mesmo problema.
- O teorema da aceleração linear para máquinas de Turing mostra que os requirimentos de espaço e tempo de uma máquina de Turing que resolve o problema de decisão pode ser reduzido, a grosso modo, por qualquer fator constante multiplicativo.
- O teorema da aceleração de Blum provê uma aceleração por qualquer função computável (não somente linear, como no teorema anterior).