Teorema da aceleração

Desambiguação Esta é uma página de desambiguação que lista os artigos que podem ser associados a um ou vários títulos.
 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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.