Teorema dello speedup

Questa voce o sezione sugli argomenti matematica e algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

Questa voce sugli argomenti matematica e algoritmi è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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.