Teorema da aceleração

Esta é uma página de desambiguação que lista os artigos que podem ser associados a um ou vários títulos.
Se uma ligação interna o conduziu até aqui, sugerimos que a corrija para apontá-la diretamente ao artigo adequado.

Nota: Para teoremas de aceleração na teoria das provas, veja Teorema da Aceleração de Gödel.

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).