Teorema dello speedup di Blum

Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili.

Ogni funzione calcolabile ha un infinito numero di differenti rappresentazioni in un dato linguaggio di programmazione. Nella teoria della computabilità si ha spesso la necessità di trovare un algoritmo di minor complessità per una data funzione calcolabile e una data classe di complessità.

Il teorema dello speedup di Blum sostiene che per ogni classe di complessità esistono funzioni calcolabili per la cui elaborazione non esistono programmi più efficienti (veloci).

Definizione

Data una funzione totale (ricorsiva) $r(x,y)$ (a due parametri), allora esiste una funzione totale $f$ (booleana, ossia con $Codf=\{0,1\}$) (o equivalentemente predicato ricorsivo) tale che per ogni programma (algoritmo) $i$ per $f$, esiste un programma $j$ per $f$, tale che per quasi tutti gli $x$ si verifica che $r(x,\Phi _{j}(x))\leq \Phi _{i}(x)$

La funzione $r$ è detta funzione speedup.

Semplificando, esistono svariati algoritmi per i quali non esiste un algoritmo più veloce, in quanto per ogni macchina di Turing che implementa il programma $i$, ne esiste sempre una (che implementa $j$) più prestante.

Bibliografia

• Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, in Journal of the ACM, vol. 14, 1967, pp. 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.

Collegamenti esterni

• (EN) Eric W. Weisstein, Teorema dello speedup di Blum, su MathWorld, Wolfram Research.