Teorema da aceleração de Blum

Teorema do speedup de Blum Na teoria da complexidade computacional, Teorema da aceleração de Blum, afirmado pela primeira vez por Manuel Blum em 1967, é um teorema fundamental sobre a complexidade de funções computáveis.

Cada função computável tem um número infinito de diferentes representações de programa em uma determinada linguagem de programação. Na teoria dos algoritmos, muitas vezes se esforça para encontrar um programa com a menor complexidade para uma determinada função computável e uma determinada medida de complexidade. (tal programa poderia ser chamado de ótimo). O teorema do speedup de Blum mostra que para qualquer medida de complexidade existem funções computáveis ​​que não são ótimas em relação a essa medida.[precisa de mais explicações] Isso também descarta a ideia de que existe uma maneira de atribuir a funções arbitrárias sua complexidade computacional, significando a atribuição a qualquer f da complexidade de um programa ótimo para f. Obviamente, isso não exclui a possibilidade de encontrar a complexidade de um programa ótimo para determinadas funções específicas.

Conteúdo 1 Teorema de aceleração 2 Veja também 3 Referências 4 External links Speedup theorem Given a Blum complexity measure {estilo de exibição (varphi ,Phi )} e uma função total computável {estilo de exibição f} com dois parâmetros, então existe um predicado computável total {estilo de exibição g} (uma função computável com valor booleano) para que para cada programa {estilo de exibição eu} por {estilo de exibição g} , existe um programa {estilo de exibição j} por {estilo de exibição g} de modo que para quase todos {estilo de exibição x} {estilo de exibição f(x,Phi _{j}(x))leq Phi _{eu}(x),} {estilo de exibição f} é chamada de função de aceleração. O fato de que pode estar crescendo tão rápido quanto desejado (desde que seja computável) significa que o fenômeno de ter sempre um programa de menor complexidade permanece mesmo que por "menor" nós queremos dizer "significativamente menor" (por exemplo, quadraticamente menor, exponencialmente menor).

Veja também o teorema da aceleração de Gödel Referências Blum, Manoel (1967). "Uma teoria independente da máquina da complexidade das funções recursivas" (PDF). Jornal da ACM. 14 (2): 322-336. doi:10.1145/321386.321395. De Emde Boas, Peter (1975). Becvar, Jorge (ed.). "Dez anos de aceleração". Anais de Fundamentos Matemáticos da Ciência da Computação, 4º Simpósio, Marianske Lazne, Setembro 1-5, 1975. Notas de aula em Ciência da Computação. Springer-Verlag. 32: 13-29. doi:10.1007/3-540-07389-2_179.. Weissstein esquerdo externo, Eric W. "Teorema da aceleração de Blum". MathWorld. Categorias: Teoremas na teoria da complexidade computacional