Teorema dello speedup di Blum
Da Wikipedia, l'enciclopedia encyclopedia
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).