Teorema da aceleração de Blum

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria da complexidade computacional, o teorema da aceleração de Blum ou teorema do aumento da velocidade de Blum (do inglês, Blum's speedup theorem), inicialmente definido por Manuel Blum em 1967, é um teorema fundamental sobre a complexidade de funções computáveis.

Cada função computável possui um número infinito de representações em programas diferentes em uma dada linguagem de programação. Na teoria dos algoritmos, muitas vezes procura-se encontrar um programa com a menor complexidade para uma dada função computável e uma medida de complexidade (tal programa poderia se denominar ótimo). O teorema da aceleração de Blum mostra que, para qualquer medida de complexidade, existem funções computáveis que não têm programas ótimos. Isto também descarta a ideia de que existe uma maneira de atribuir às funções arbitrárias as suas próprias complexidades computacionais, significando a atribuição de qualquer f da complexidade de um programa ótimo para f. É claro que isto não exclui a possibilidade de encontrar a complexidade de um programa ótimo para determinadas funções específicas.

Teorema da aceleração[editar | editar código-fonte]

Dada uma medida de complexidade de Blum (\varphi, \Phi) e uma função computável total f com dois parâmetros, então existe um predicado computável total g (uma função computável booleana valorada) tal que para todo programa i para g, existe um programa j para g tal que para quase todo x

f(x, \Phi_j(x)) \leq \Phi_i(x) \,

f é chamada função de aceleração. O fato de que ele pode crescer tão rápido quanto se deseja (desde que ainda seja computável) significa que o fenômeno de sempre ter um programa de menor complexidade permanece, mesmo se por "menor" nós queremos dizer "significativamente menor" (por exemplo, quadraticamente menor, exponencialmente menor).

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • Blum, Manuel (1967), "A Machine-Independent Theory of the Complexity of Recursive Functions", Journal of the ACM 14: 322–336, doi:10.1145/321386.321395 
  • Peter van Emde Boas, Ten years of speedup, Proceedings of MFCS (Jirí Becvár, ed.), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp. 13–29.

Links externos[editar | editar código-fonte]