Teorema dello speedup

Nella teoria della complessità computazionale un teorema dello speedup (in inglese speed-up significa velocizzare) è un teorema che considera alcuni algoritmi che risolvono determinati problemi e dimostra l'esistenza di algoritmi più efficienti per risolvere gli stessi problemi.

Il teorema dello speedup lineare per le macchine di Turing dimostra che lo spazio e il tempo richiesti da una macchina di Turing per risolvere un problema decidibile possono essere ridotti, in parole povere, di un qualunque fattore costante moltiplicativo. Come conseguenza si ha che è sempre possibile migliorare la velocità di esecuzione di un algoritmo (a patto di utilizzare più memoria) oppure che è sempre possibile diminuire lo spazio occupato in memoria (a patto di aumentare il tempo di esecuzione), tuttavia i miglioramenti sono al più lineari.

Il teorema dello speedup di Blum dimostra la velocizzazione di qualunque funzione calcolabile (non solo lineare, come nel precedente teorema). Data la desiderata funzione di speedup, deduce l'esistenza di un problema decidibile tale che qualunque algoritmo in grado di risolverlo può essere velocizzato.