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).

DefinizioneModifica

Data una funzione totale (ricorsiva)   (a due parametri), allora esiste una funzione totale   (booleana, ossia con  ) (o equivalentemente predicato ricorsivo) tale che per ogni programma (algoritmo)   per  , esiste un programma   per  , tale che per quasi tutti gli   si verifica che  

La funzione   è 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  , ne esiste sempre una (che implementa  ) più prestante.

BibliografiaModifica

Collegamenti esterniModifica