En la teoría de la complejidad computacional , el teorema de aceleración de Blum , establecido 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 dado. En la teoría de los 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 (tal programa podría llamarse óptimo ). El teorema de aceleración de Blum muestra que para cualquier medida de complejidad hay funciones computables que no son óptimas con respecto a esa medida. Esto también descarta la idea de que hay 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.
Teorema de aceleración
Dada una medida de complejidad de Blum y una función computable total con dos parámetros, existe un predicado computable total (una función computable con valor booleano ) de modo que para cada programa por , existe un programa por para 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 permanece incluso si por "más pequeño" queremos decir "significativamente más pequeño" (por ejemplo, cuadráticamente más pequeño, exponencialmente más pequeño).
Ver también
Referencias
- Blum, Manuel (1967). "Una teoría independiente de la máquina de la complejidad de las funciones recursivas" (PDF) . Revista de la ACM . 14 (2): 322–336. doi : 10.1145 / 321386.321395 .
- Van Emde Boas, Peter (1975). Bečvář, Jiří (ed.). "Diez años de aceleración". Proceedings of Mathematical Foundations of Computer Science, IV Simposio, Mariánské Lázně, 1-5 de septiembre de 1975 . Apuntes de conferencias en Ciencias de la Computación. Springer-Verlag. 32 : 13-29. doi : 10.1007 / 3-540-07389-2_179 ..