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).
Categoria:Teoremas em matemática discreta Categoria:Complexidade