Fondamenti di teoria della complessità computazionale EITC/IS/CCTF

Poiché la quantità di risorse necessarie per eseguire un algoritmo varia con la dimensione dell'input, la complessità è solitamente espressa come una funzione f(n), dove n è la dimensione dell'input e f(n) è la complessità del caso peggiore ( la quantità massima di risorse richiesta su tutti gli input di dimensione n) o la complessità del caso medio (la media della quantità di risorse su tutti gli input di dimensione n). Il numero di operazioni elementari richieste su un input di dimensione n è comunemente indicato come complessità temporale, in cui si ritiene che le operazioni elementari richiedano una quantità di tempo costante su un determinato computer e cambino solo di un fattore costante quando vengono eseguite su una macchina diversa. La quantità di memoria richiesta da un algoritmo su un input di dimensione n è nota come complessità spaziale.

Il tempo è la risorsa più comunemente considerata. Quando il termine "complessità" è usato senza qualificatore, di solito si riferisce alla complessità del tempo.

Le unità di tempo tradizionali (secondi, minuti e così via) non sono impiegate nella teoria della complessità poiché dipendono troppo dal computer scelto e dal progresso della tecnologia. Ad esempio, un computer oggi può eseguire un algoritmo sostanzialmente più velocemente di un computer degli anni '1960, ma ciò è dovuto a innovazioni tecnologiche nell'hardware del computer piuttosto che a una qualità intrinseca dell'algoritmo. L'obiettivo della teoria della complessità è quantificare le esigenze di tempo intrinseche degli algoritmi o le limitazioni temporali fondamentali che un algoritmo imporrebbe a qualsiasi computer. Ciò si ottiene contando quante operazioni di base vengono eseguite durante il calcolo. Queste procedure sono comunemente denominate passaggi perché si ritiene che richiedano tempo costante su una macchina particolare (cioè non sono influenzate dalla quantità di input).

Un'altra risorsa importante è la quantità di memoria del computer richiesta per eseguire algoritmi.

Un'altra risorsa spesso utilizzata è la quantità di operazioni aritmetiche. In questo scenario viene utilizzato il termine “complessità aritmetica”. La complessità temporale è generalmente il prodotto della complessità aritmetica per un fattore costante se è noto un vincolo superiore alla dimensione della rappresentazione binaria dei numeri che si verificano durante un calcolo.

La dimensione degli interi utilizzati durante un calcolo non è vincolata per molti metodi ed è irrealistico presumere che le operazioni aritmetiche richiedano una quantità di tempo fissa. Di conseguenza, la complessità temporale, nota anche come complessità di bit, può essere significativamente maggiore della complessità aritmetica. La difficoltà aritmetica di calcolare il determinante di una matrice intera nn, ad esempio, è O(n^3) per le tecniche standard (eliminazione gaussiana). Poiché la dimensione dei coefficienti potrebbe espandersi in modo esponenziale durante il calcolo, la complessità in bit degli stessi metodi è esponenziale in n. Se queste tecniche vengono utilizzate insieme all'aritmetica multimodulare, la complessità dei bit può essere ridotta a O(n^4).

La complessità dei bit, in termini formali, si riferisce al numero di operazioni sui bit richieste per eseguire un algoritmo. Eguaglia la complessità temporale fino a un fattore costante nella maggior parte dei paradigmi di calcolo. Il numero di operazioni sulle parole macchina richieste dai computer è proporzionale alla complessità dei bit. Per modelli di calcolo realistici, la complessità temporale e la complessità bit sono quindi identiche.

La risorsa che viene spesso considerata nell'ordinamento e nella ricerca è la quantità di confronti tra voci. Se i dati sono ben organizzati, questo è un buon indicatore della complessità temporale.

Su tutti i potenziali input, il conteggio del numero di passaggi in un algoritmo è impossibile. Poiché la complessità di un input aumenta con la sua dimensione, è comunemente rappresentato come una funzione della dimensione n dell'input (in bit), quindi la complessità è una funzione di n. Per gli input delle stesse dimensioni, tuttavia, la complessità di un algoritmo può variare notevolmente. Di conseguenza, vengono regolarmente impiegate una varietà di funzioni di complessità.

La complessità del caso peggiore è la somma di tutta la complessità per tutti gli input di dimensione n, mentre la complessità del caso medio è la somma di tutta la complessità per tutti gli input di dimensione n (questo ha senso, poiché il numero di possibili input di una data dimensione è finito). Quando il termine “complessità” viene utilizzato senza essere ulteriormente definito, viene presa in considerazione la complessità temporale del caso peggiore.

La complessità del caso peggiore e del caso medio è notoriamente difficile da calcolare correttamente. Inoltre, questi valori esatti hanno poca applicazione pratica perché qualsiasi cambiamento nella macchina o nel paradigma di calcolo varierebbe leggermente la complessità. Inoltre, l’utilizzo delle risorse non è importante per valori piccoli di n, quindi la facilità di implementazione è spesso più attraente della bassa complessità per n piccoli.

Per questi motivi, la maggior parte dell'attenzione è rivolta al comportamento della complessità per n alto, cioè al suo comportamento asintotico quando n si avvicina all'infinito. Di conseguenza, la notazione O grande è comunemente usata per indicare la complessità.

Modelli computazionali

La scelta di un modello di calcolo, che consiste nello specificare le operazioni essenziali che vengono eseguite in un'unità di tempo, è importante per determinarne la complessità. Questa viene talvolta definita macchina di Turing multinastro quando il paradigma di calcolo non è descritto specificamente.

Un modello deterministico di calcolo è quello in cui gli stati successivi della macchina e le operazioni da eseguire sono interamente definiti dallo stato precedente. Le funzioni ricorsive, il calcolo lambda e le macchine di Turing furono i primi modelli deterministici. Le macchine ad accesso casuale (note anche come macchine RAM) sono un paradigma popolare per la simulazione di computer del mondo reale.

Quando il modello di calcolo non è definito, di solito si assume una macchina di Turing multinastro. Sulle macchine di Turing multinastro, la complessità temporale è la stessa delle macchine RAM per la maggior parte degli algoritmi, sebbene per ottenere questa equivalenza potrebbe essere necessaria una notevole attenzione nel modo in cui i dati vengono archiviati in memoria.

Varie scelte possono essere fatte in alcune fasi del calcolo in un modello di calcolo non deterministico, come le macchine di Turing non deterministiche. Nella teoria della complessità, tutte le opzioni possibili sono considerate contemporaneamente e la complessità temporale non deterministica è la quantità di tempo richiesta quando vengono sempre fatte le scelte migliori. Per dirla in altro modo, il calcolo viene eseguito contemporaneamente su tutti i processori (identici) necessari e il tempo di calcolo non deterministico è il tempo impiegato dal primo processore per completare il calcolo. Questo parallelismo può essere utilizzato nell'informatica quantistica utilizzando stati entangled sovrapposti durante l'esecuzione di algoritmi quantistici specializzati, come ad esempio la fattorizzazione di minuscoli interi di Shor.

Anche se tale modello di calcolo non è attualmente praticabile, ha un significato teorico, in particolare in relazione al problema P = NP, che chiede se le classi di complessità prodotte utilizzando “tempo polinomiale” e “tempo polinomiale non deterministico” come minimo superiore i limiti sono gli stessi. Su un computer deterministico, la simulazione di un algoritmo NP richiede "tempo esponenziale". Se un compito può essere risolto in tempo polinomiale su un sistema non deterministico, appartiene alla classe di difficoltà NP. Se un problema è in NP e non è più semplice di qualsiasi altro problema NP, si dice NP-completo. Il problema dello zaino, il problema del commesso viaggiatore e il problema della soddisfacibilità booleana sono tutti problemi combinatori NP-completi. L'algoritmo più noto ha una complessità esponenziale per tutti questi problemi. Se uno qualsiasi di questi problemi potesse essere risolto in tempo polinomiale su una macchina deterministica, allora tutti i problemi NP potrebbero essere risolti anche in tempo polinomiale e verrebbero stabiliti P = NP. A partire dal 2017, è ampiamente assunto che P NP, il che implica che le peggiori situazioni di problemi NP sono fondamentalmente difficili da risolvere, ovvero richiedono molto più tempo di qualsiasi intervallo di tempo fattibile (decenni) date interessanti lunghezze di input.

Calcolo parallelo e distribuito

L'elaborazione parallela e distribuita implica la divisione dell'elaborazione su più processori che operano tutti contemporaneamente. La distinzione fondamentale tra i vari modelli è la modalità di invio dei dati tra i responsabili. La trasmissione dei dati tra processori è in genere molto rapida nel calcolo parallelo, mentre il trasferimento dei dati tra processori nel calcolo distribuito avviene attraverso una rete ed è quindi sostanzialmente più lento.

Un calcolo su N processori richiede almeno il quoziente di N del tempo impiegato da un singolo processore. In realtà, poiché alcune attività secondarie non possono essere parallelizzate e alcuni processori potrebbero dover attendere un risultato da un altro processore, questo limite teoricamente ideale non verrà mai raggiunto.

La questione chiave della complessità è quindi sviluppare algoritmi in modo che il prodotto del tempo di calcolo per il numero di processori sia il più vicino possibile al tempo necessario per eseguire lo stesso calcolo su un singolo processore.

Calcolo quantistico

Un computer quantistico è un computer con un modello di calcolo basato sulla meccanica quantistica. La tesi di Church-Turing vale per i computer quantistici, il che implica che qualsiasi problema che un computer quantistico può risolvere può essere risolto anche da una macchina di Turing. Tuttavia, alcuni compiti potrebbero teoricamente essere risolti utilizzando un computer quantistico piuttosto che un computer classico con una complessità temporale significativamente inferiore. Per il momento, questo è strettamente teorico, poiché nessuno sa come sviluppare un pratico computer quantistico.

La teoria della complessità quantistica è stata creata per studiare i diversi tipi di problemi che possono essere risolti dai computer quantistici. Viene utilizzato nella crittografia post-quantistica, che è il processo di creazione di protocolli crittografici resistenti agli attacchi dei computer quantistici.

Complessità del problema (limiti inferiori)

L'ultima delle complessità degli algoritmi che possono risolvere il problema, comprese le tecniche non ancora scoperte, è la complessità del problema. Di conseguenza, la complessità di un problema è uguale alla complessità di qualsiasi algoritmo che lo risolva.

Di conseguenza, qualsiasi complessità data nella notazione O grande rappresenta una complessità sia dell'algoritmo che del problema che lo accompagna.

D'altra parte, ottenere limiti inferiori non banali alla complessità dei problemi è spesso difficile e ci sono poche strategie per farlo.

Per risolvere la maggior parte dei problemi, è necessario leggere tutti i dati di input, operazione che richiede tempo proporzionato all'entità dei dati. Di conseguenza, tali problemi hanno una complessità almeno lineare, o, in grande notazione omega, una complessità di Ω(n).

Alcuni problemi, come quelli di computer algebra e geometria algebrica computazionale, hanno soluzioni molto ampie. Poiché l'output deve essere scritto, la complessità è vincolata dalla dimensione massima dell'output.

Il numero di confronti richiesti per un algoritmo di ordinamento ha un limite inferiore non lineare di Ω(nlogn). Di conseguenza, i migliori algoritmi di ordinamento sono i più efficienti poiché la loro complessità è O(nlogn). Il fatto che ci siano n! modi per organizzare n cose porta a questo limite inferiore. Perché ogni confronto divide questa raccolta di n! ordini in due pezzi, il numero di N confronti necessari per distinguere tutti gli ordini deve essere 2N > n!, implicando O(nlogn) dalla formula di Stirling.

Ridurre un problema a un altro problema è una strategia comune per ottenere vincoli di complessità ridotta.

Sviluppo dell'algoritmo

La valutazione della complessità di un algoritmo è un elemento importante del processo di progettazione poiché fornisce informazioni utili sulle prestazioni attese.

È un malinteso frequente che, a causa della legge di Moore, che prevede la crescita esponenziale della moderna potenza dei computer, la valutazione della complessità degli algoritmi diventi meno rilevante. Ciò non è corretto perché la maggiore potenza consente l'elaborazione di enormi quantità di dati (big data). Ad esempio, qualsiasi algoritmo dovrebbe funzionare bene in meno di un secondo quando si ordina in ordine alfabetico un elenco di poche centinaia di voci, come la bibliografia di un libro. D'altra parte, per un milione di voci (ad esempio i numeri di telefono di una grande città), gli algoritmi di base che richiedono O(n2) confronti dovrebbero eseguire un trilione di confronti, che impiegherebbero tre ore a una velocità di 10 milioni di confronti al secondo. Quicksort e merge sort, d'altra parte, richiedono solo confronti nlogn (come complessità nel caso medio per il primo, come complessità nel caso peggiore per il secondo). Ciò produce circa 30,000,000 di confronti per n = 1,000,000, che richiederebbero solo 3 secondi a 10 milioni di confronti al secondo.

Di conseguenza, la valutazione della complessità può consentire l'eliminazione di molti algoritmi inefficienti prima dell'implementazione. Questo può essere utilizzato anche per mettere a punto algoritmi complessi senza dover testare tutte le possibili varianti. Lo studio della complessità consente di concentrare lo sforzo per aumentare l'efficienza di un'implementazione determinando i passaggi più costosi di un algoritmo complesso.