En la teoría de la complejidad computacional , el teorema de aceleración de Blum , enunciado por primera vez por Manuel Blum en 1967, es un teorema fundamental sobre la complejidad de las funciones computables .
Cada función computable tiene un número infinito de representaciones de programas diferentes en un lenguaje de programación determinado . En la teoría de algoritmos , a menudo uno se esfuerza por encontrar un programa con la menor complejidad para una función computable dada y una medida de complejidad dada (dicho programa podría llamarse óptimo ). El teorema de aceleración de Blum muestra que para cualquier medida de complejidad, existe una función computable tal que no existe un programa óptimo que la calcule, porque cada programa tiene un programa de menor complejidad. Esto también descarta la idea de que existe una manera de asignar a funciones arbitrarias su complejidad computacional, es decir, la asignación a cualquier f de la complejidad de un programa óptimo para f . Por supuesto, esto no excluye la posibilidad de encontrar la complejidad de un programa óptimo para determinadas funciones específicas.
Dada una medida de complejidad de Blum y una función computable total con dos parámetros, entonces existe un predicado computable total (una función computable con valor booleano ) de modo que para cada programa para , existe un programa para de modo que para casi todos
se llama función de aceleración . El hecho de que pueda crecer tan rápido como se desee (siempre que sea computable) significa que el fenómeno de tener siempre un programa de menor complejidad persiste incluso si por "menor" entendemos "significativamente más pequeño" (por ejemplo, cuadráticamente más pequeño, exponencialmente más pequeño).
