Teoria della complessità computazionale

La teoria della complessità è un ramo dell'informatica teorica che si occupa di studiare la difficoltà intrinseca di risolvere vari problemi computazionali.

Si focalizza su una domanda fondamentale: perché alcuni problemi sono considerati computazionalmente difficili e altri no?

Questa disciplina non solo esplora la natura dei problemi, ma cerca anche di stabilire un quadro per confrontare e classificare la loro complessità in modo sistematico e quantificabile.

Cerca di comprendere i limiti di ciò che può essere calcolato in pratica, non solo in teoria, valutando la quantità di risorse, come tempo e spazio (memoria), necessarie per risolvere un dato problema.

Questo campo si distingue dalla teoria della calcolabilità, che si interessa principalmente di determinare se un problema è computabile, senza considerare le risorse necessarie per la sua soluzione.

Origini e sviluppi storici

La teoria della complessità computazionale emerse negli anni '60 e '70 come una disciplina distinta all'interno dell'informatica, grazie al lavoro di ricercatori come Jack Edmonds, Stephen Cook, e Leonid Levin. Uno dei primi e più influenti risultati fu la formalizzazione della classe di problemi NP-completi da parte di Cook nel 1971, che aprì la strada a un'ampia ricerca sulla difficoltà computazionale e sulla relazione tra diverse classi di problemi.

Le classi di complessità principali

Uno degli sviluppi più significativi in teoria della complessità è stata l'introduzione di schemi di classificazione che organizzano i problemi computazionali basandosi sulla loro difficoltà.

Questo sistema di classificazione permette agli scienziati di identificare e provare la difficoltà computazionale di specifici problemi, anche quando non è possibile dimostrarne direttamente la complessità.

Questi schemi sono analoghi alla tavola periodica degli elementi, dove i problemi vengono catalogati in base alla loro "pesantezza" computazionale, simile a come gli elementi chimici sono ordinati per numero atomico e proprietà chimiche. Anche nella tavola periodica si parte dall'elemento chimico più leggero (l'idrogeno) per arrivare agli atomi più pesanti.

In particolare, la teoria della complessità classifica i problemi computazionali in diverse classi, basate sulla quantità di risorse richieste per risolverli. Le classi più studiate includono:

• P: La classe dei problemi che possono essere risolti in tempo polinomiale da una macchina di Turing deterministica. Questa classe rappresenta i problemi considerati "facilmente" risolvibili.
• NP: La classe dei problemi per i quali una soluzione può essere verificata in tempo polinomiale da una macchina di Turing deterministica. Comprende tutti i problemi in P, e si sospetta che includa problemi non risolvibili in tempo polinomiale.
• NP-Completo: Una sottoclasse di NP che comprende i problemi più difficili in NP, nel senso che se un problema NP-completo può essere risolto in tempo polinomiale, allora tutti i problemi in NP possono essere risolti in tempo polinomiale.
• Co-NP: La classe Co-NP è costituita dai problemi il cui complemento è in NP. In altre parole, per i problemi in Co-NP, è possibile verificare rapidamente (in tempo polinomiale) una soluzione negativa.
• PSPACE: La classe dei problemi risolvibili con una quantità polinomiale di memoria, senza restrizioni sul tempo. Include tutte le classi P, NP, e Co-NP.  È più generale di P e NP e include problemi che potrebbero richiedere tempo esponenziale per essere risolti.
• EXPTIME: I problemi in EXPTIME sono quelli che possono essere risolti in tempo esponenziale rispetto alla dimensione dell'input. Questa classe contiene problemi che sono significativamente più difficili da risolvere rispetto a quelli in P o NP.
• SPACE: Simile a PSPACE, ma senza la limitazione al polinomiale. Include problemi che possono essere risolti in qualsiasi quantità di spazio.
• NC: La classe NC è formata dai problemi che possono essere risolti efficientemente su una macchina parallela, cioè in tempo polinomiale utilizzando un numero polinomiale di processori.
• AC: Una sottoclasse di NC, la classe AC comprende problemi risolvibili con circuiti booleani di profondità logaritmica e porte logiche con un numero arbitrario di ingressi.
• BPP: BPP sta per Bounded Error Probabilistic Polynomial time. Comprende i problemi che possono essere risolti in tempo polinomiale con un algoritmo probabilistico che ha una probabilità di errore inferiore a 1/3 per ogni input.
• #P: La classe #P comprende i problemi di conteggio, che sono correlati ai problemi decisionali in NP. Un problema #P è il problema di contare il numero di soluzioni di un problema in NP.
• L: La classe L (Logspace) comprende i problemi che possono essere risolti utilizzando una quantità di memoria logaritmica. È una sottoclasse molto limitata rispetto a PSPACE.
• EXPSPACE: Simile a EXPTIME, ma per la complessità spaziale. Comprende i problemi che possono essere risolti utilizzando una quantità di spazio esponenziale.

Queste e altre classi di complessità aiutano i ricercatori a comprendere la struttura dei problemi computazionali e le relazioni tra di loro, facilitando lo sviluppo di algoritmi efficienti e la determinazione dei limiti teorici del calcolo.

Generalmente, per risolvere un problema computazionale si cerca la strada più "facile", quella che consuma meno risorse di memoria e tempo di elaborazione. Fa eccezione la crittografia, dove i problemi computazionalmente "difficili" sono utili per garantire la protezione e la sicurezza dei dati. Ad esempio, un codice segreto è robusto se richiede enorme quantità di tempo e risorse computazionali per essere decifrato.

Questioni aperte e ricerca attuale

La questione se P sia uguale a NP è uno dei problemi aperti più celebri della matematica e dell'informatica. La sua soluzione avrebbe implicazioni profonde per la teoria della complessità, la crittografia, l'ottimizzazione, e molti altri campi. Nonostante decenni di intensa ricerca, il problema rimane irrisolto.

La ricerca contemporanea in teoria della complessità si estende anche al di là delle classi classiche come P e NP, esplorando nuovi modelli di calcolo (ad esempio, il calcolo quantistico) e nuove classi di complessità. Questi sforzi mirano a comprendere meglio la natura del calcolo e a sviluppare nuove tecniche per affrontare problemi computazionali complessi.

In conclusione, la teoria della complessità computazionale continua a essere un campo di studio vibrante e fondamentale nell'informatica, offrendo intuizioni cruciali sui limiti del calcolo e guidando lo sviluppo di algoritmi efficienti. Con le sue questioni aperte e i continui sviluppi, promette di rimanere al centro dell'attenzione scientifica per molti anni a venire.