E' venuto fuori un post molto lungo, anche se più breve di quel che avrei voluto...
Chiariamo innanzitutto alcuni aspetti del tutto generali sui criteri alla base della classificazione della complessità computazionale di un problema.
Efficienza algoritmica come limite superiore alla complessità di un problema
La legge di scala (polinomiale, esponenziale, etc) delle risorse computazionali (tempo, memoria, etc) in ragione della taglia del problema (le cifre del numero da fattorizzare, il numero di amminoacidi della proteina da foldare) è, strettamente parlando, una caratteristica dell'algoritmo, non del problema: posso infatti benissimo immaginare di risolvere un problema P con un algoritmo che scala esponenzialmente, basta essere sufficientemente "ingenuo" e "sprecone".
Dato però un algoritmo capace di risolvere un certo problema, posso comunque dire qualcosa sulla complessità computazionale del problema: essa certamente non sarà superiore alla complessità dell'algoritmo.
Quando dunque voglio parlare di
complessità di un problema in termini di risorse, dovrò necessariamente parlare di complessità
non maggiore di quella del miglior algoritmo noto: potrà sempre succedere di scoprire un algoritmo più efficiente per un problema, dimostrando così che la sua complessità computazionale era effettivamente più piccola di quella che credevamo (e storicamente è proprio successo così per alcuni problemi che sembravano più "difficili" di quel che erano, uno per tutti il
test di primalità, il problema, cioè, di stabilire se un numero è primo o meno — senza dover trovare esplicitamente i suoi fattori primi).
L'unico modo che avremmo per poter dire che un problema è davvero, intrinsecamente "difficile" sarebbe quello di dimostrare che non è matematicamente possibile trovare un algoritmo più efficiente di una certa complessità, ma questo finora, che io sappia, non è mai accaduto per nessun problema.
Di conseguenza, dunque, le classi di complessità dei problemi tendono ad essere degli insiemi "concentrici" in cui le classi più "complesse" includono quelle più semplici (e.g. P è un sottoinsieme di NP). In realtà non è sempre necessariamente così per tutte le possibili classificazioni e comunque quasi sempre non abbiamo garanzie che l'inclusione sia propria, che esistano cioè problemi che hanno una qualche complessità minima (e.g. un problema che sia in NP ma non in P — che equivarrebbe appunto a dimostrare che P!=NP).
Esempi semplici
Chiarito il senso generale del concetto di "classe di complessità di un problema", possiamo passare ad alcune classi specifiche: P è la classe di problemi per cui si conosce un algoritmo di soluzione che scala polinomialmente nel tempo, EXP quella dei problemi di cui si conosce un algoritmo di soluzione che scala esponenziale nel tempo; PSPACE è quella dei problemi di cui si conosce un algoritmo di soluzione che scala polinomialmente nell'uso di memoria (space), fosse anche in tempo infinito. Evidentemente, per quanto detto prima, P è un sottoinsieme di EXP. Si può poi dimostrare che PSPACE è un sottoinsieme di EXP e dunque la catena di inclusioni "concentriche" è: EXP ⊇ PSPACE ⊇ P.
NP
Bene, veniamo dunque ai problemi NP. La classe NP è definita in modo un po' diverso (è per questo che dicevo che non tutte le classi sono "concentriche": ad esempio sia NP che coNP includono P, ma entrambe non sono (probabilmente) l'una il sottoinsieme dell'altra — a meno che NP=coNP o addirittura che P=NP, e allora sarebbe P=NP=coNP... Se vi interessa dare uno sguardo "grafico" allo
Zoo della complessità potete dare un'occhiata a uno di questi
diagrammi delle inclusioni; se vi interessano i dettagli potete perdervi nel
Complexity Zoo Qwiki).
Dicevamo, NP: si può definire la classe NP con una legge di scala degli algoritmi, ma per farlo bisogna cambiare definizione di algoritmo: i problemi NP sono quelli per cui è noto un algoritmo
non-deterministico (da cui la
N della sigla NP) capace di risolverlo in tempi polinomiali. Gli algoritmi non-deterministici (o equivalentemente le macchine di Turing non-deterministiche) rappresentano un modello computazionale molto utile a livello teorico ma di scarsa rilevanza pratica, dal momento che non è possibile costruirne una realizzazione fisica. Praticamente tutti i moderni computer sono invece delle
macchine di Von Neumann che implementano una macchina di Turing universale
deterministica, e infatti quando si parla di algoritmi senza ulteriori specificazioni si intendono sempre algoritmi
deterministici o per macchine di Turing
deterministiche.
Esiste però una definizione del tutto equivalente, che tira in ballo i soliti algoritmi deterministici: i problemi NP sono quei problemi per cui è noto un algoritmo (deterministico) capace di verificare la soluzione in tempi polinomiali.
Per la cronaca, i problemi NP stanno fra PSPACE e P, ovvero: EXP ⊇ PSPACE ⊇ NP ⊇ P.
NP-completezza: un limite inferiore alla complessità di un problema?
E i tanto chiacchierati problemi NP-completi? Qui le cose si fanno più intricate... e più affascinanti. In effetti quella dei problemi NP-completi non è nemmeno una classe di complessità in senso proprio del termine (non la troverete, infatti, nel
super-mega-complicatissimo-diagramma-di-inclusione).
Il punto cruciale è che la definizione di problema NP-completo cerca di fare quello che le classi di complessità di cui abbiamo parlato finora non possono fare: rappresentare un limite inferiore alla complessità di un problema. Dico cerca perché, ovviamente, se ci riuscisse veramente avrebbe appunto dimostrato che P≠NP. E tuttavia, pur non riuscendoci, il procedimento escogitato per la definizione di NP-completezza, la riduzione polinomiale, è in grado di gettare nuova luce su tutta teoria della complessità computazionale.
Abbiamo, dunque, molti problemi NP che ci sembrano difficili. Ma alcuni di essi, come il
test di primalità, abbiamo scoperto essere solo apparentemente difficili — nel 1975 si riuscì a dimostrare che il test di primalità era un problema NP, ma
ci vollero 27 anni perché fosse "risolto"
con un algoritmo polinomiale!
Come distinguere, dunque, i problemi che sembrano difficili da quelli che lo sono davvero? Distinguerli proprio sulla base della difficoltà è una petizione di principio, significherebbe sapere che sono difficili, ovvero che P≠NP. Quello che fa, invece, la definizione di NP-completezza è trovare una caratteristica comune a quasi tutti i problemi che, ancora oggi, ci paiono difficili, caratteristica che invece non hanno i problemi facili, che stanno in P. Di più: questa caratteristica è tale per cui, se davvero P≠NP, allora i problemi in NP che non stanno in P sono proprio (almeno) i problemi NP-completi. Detto più precisamente, i problemi NP-completi sono certamente "i più difficili" fra i problemi NP (sempre se P≠NP, altrimenti "tutti i problemi NP sono facili come quelli in P").
Quel
quasi tutti si riferisce al fatto che esistono alcuni problemi NP che ci paiono difficili (cioè di cui non abbiamo ancora trovato un algoritmo polinomiale per risolverli) ma che non siamo riusciti a dimostrare essere NP-completi — e il problema della fattorizzazione dei numeri composti, alla base di quasi tutte le tecniche crittografiche usate comunemente, è proprio uno di questi. Se davvero P≠NP e dunque non tutti i problemi NP sono ugualmente facili, ciascuno di questi problemi potrebbe, più o meno indipendentemente dagli altri:
- essere "semplicemente" un problema P, come il test di primalità, e un giorno, chissà, riusciremo a trovare un algoritmo di soluzione polinomiale;
- essere anch'esso un problema NP-completo, solo che ancora non siamo riusciti a dimostrarlo;
- essere di una complessità computazionale intermedia.
E qui arriva il bello.
Riduzione polinomiale, NP-hard e, finalmente, la definizione di NP-completezza
Ho quasi finito, ma, prima di concludere con la questione della fattorizzazione e delle tecniche crittografiche, direi che è il caso di spiegare in cosa consiste questa mitica NP-completezza, la proprietà di alcuni problemi NP che sembra caratterizzarne la (apparente) difficoltà.
L'elemento fondamentale è il concetto di
riduzione e in particolare di
riduzione polinomiale. Ne esistono di due tipi diversi (di Cook e di Karp), ma per amor di brevità sarò impreciso e dirò che ho ridotto il problema A al problema B se, data la soluzione del problema A, so trovare la soluzione al problema B con un algoritmo al più polinomiale. Definisco ora un problema B come
NP-hard se un qualsiasi problema NP può essere ridotto polinomialmente a B: se, cioè, con un oracolo capace di darmi istantaneamente la soluzione di B, so risolvere qualsiasi problema NP in tempi polinomiali. Definisco finalmente i problemi
NP-completi come quei problemi NP-hard che siano anche problemi NP.
Il fatto che una soluzione "facile" ad uno qualsiasi di questi problemi dischiuderebbe automaticamente le porte a tutti gli altri problemi in NP ne fa chiaramente i rappresentati "più difficili" della classe NP. Non solo: ci dice anche che la "difficoltà" dei problemi NP-completi è essenzialmente la stessa, come se si trattasse di un unico problema sotto diverse sembianze: se uno qualunque di questi problemi ha una soluzione facile, allora tutti quanti ce l'hanno e, di fatto, P=NP; se riuscite a dimostrare che uno qualunque di essi non può avere una soluzione polinomiale, allora nessun'altro potrà averla e, di fatto, avete dimostrato che P≠NP; uno per tutti, tutti per uno.
Per dimostrare, dunque, che un problema NP è NP-completo è sufficiente dimostrare che è riducibile ad uno qualsiasi degli altri problemi di cui è stata già dimostrata la NP-completezza. La scoperta di problemi NP-completi procedette perciò con un effetto valanga: più problemi rientravano nella categoria, più facile diventata ricondurvene di nuovi. Le dimostrazioni di NP-completezza diventarono routine e al momento si contano
più di tremila problemi NP-completi.
Il problema della fattorizzazione: fra P e NP-completi
Esistono però alcune — poche — notevoli eccezioni: problemi NP, cioè, che (ancora) ci paiono difficili (e dunque sospettiamo non siano P), di cui purtuttavia non si riesce a dimostrare l'NP-completezza. Esempi di problemi di questo tipo sono l'
isomorfismo fra grafi, il
logaritmo discreto e, udite udite, il problema della
fattorizzazione.
Del resto ci sono ragioni piuttosto profonde per
credere che la fattorizzazione non sia un problema NP-completo: per esempio un'istanza di problemi NP-completo può, in generale, avere nessuna, una o centomila soluzioni diverse; la fattorizzazione di un numero composto, invece, è unica. Questa sorta di
struttura del problema della fattorizzazione è in effetti sfruttata dal
crivello dei campi di numeri, il miglior algoritmo noto di fattorizzazione, che scala più o meno come 2 alla radice cubica di
n, qualcosa che qualcuno definisce pur sempre come un andamento
sub-esponenziale.
Le possibili relazioni fra P, NP e coNP.
Se il problema della fattorizzazione fosse NP-completo, la relazione corretta sarebbe la (b).
Inoltre il problema della fattorizzazione non solo appartiene a NP ma anche
coNP, la classe di complessità complementare a NP secondo una precisa
definizione che non mi dilungherò a discutere (è già diventato troppo lungo questo post, devo sbrigarmi a chiudere!). Ora, la relazione (insiemistica) fra NP e coNP (ed anche con P) non è nota con certezza matematica, ma ci sono diversi indizi che suggeriscono che NP≠coNP. Ebbene, se la fattorizzazione fosse NP-completa, significherebbe proprio che NP=coNP. Per quel che ne sappiamo, poi, potrebbe pure darsi che l'intersezione fra NP e coNP (a cui certamente appartiene il problema della fattorizzazione) coincida con P stesso (ovvero la fattorizzazione è risolvibile in tempo polinomiale) e purtuttavia P e NP non coincidano!
Per non parlare, poi, del fatto che per il problema della fattorizzazione, e non per alcun problema NP-completo, siamo riusciti a trovare un algoritmo
quantistico, quello di
Shor, capace di trovare la soluzione in tempi polinomiali.
Ma, appunto, non ne parlerò, si è già fatto troppo tardi.
Sono sicuro che non è rimasto più nessuno, fin qui, a leggere... :-)
