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 ${\displaystyle (\varphi ,\Phi )}$ e uma função computável total ${\displaystyle f}$ com dois parâmetros, então existe um predicado computável total ${\displaystyle g}$ (uma função computável booleana valorada) tal que para todo programa ${\displaystyle i}$ para ${\displaystyle g}$, existe um programa ${\displaystyle j}$ para ${\displaystyle g}$ tal que para quase todo ${\displaystyle x}$

${\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x)\,}$

${\displaystyle 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

Referências

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

Ligações externas

• Weisstein, Eric W. «Blum's Speed-Up Theorem» (em inglês). MathWorld