Teorema da aceleração de Blum

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

Dada uma medida de complexidade de Blum $(\phi ,\mathrm{\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,{\mathrm{\Phi }}_j(x))\le {\mathrm{\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).

Ver também

• Teorema da aceleração
• Teorema da Aceleração de Gödel

• Predefinição:Citation
• 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.

Ligações externas

• Predefinição:MathWorld