Fra P e NP(-completi)

 

Proseguo dal post precedente.

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. 

Come al solito le definizioni sono mere convenzioni e dunque il fatto notevole è che nei primi anni 70 Cook, Karp e Levin mostrarono non tanto che esistono problemi NP-completi quanto che molti problemi concreti erano proprio NP-completi. 

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... :-)

La fattorizzazione non è un problema NP-completo (che si sappia)

Questa storia della dimostrazione (ormai quasi definitivamente smontata) che P≠NP sta riportando in superficie il diffusissimo errore secondo cui se P≠NP allora i crittografi e i loro clienti potranno dormire sonni tranquilli (ho citato la mia amica Sylvie, ma è un'affermazione piuttosto frequente).

L'errore consiste nel considerare il problema della fattorizzazione dei numeri composti un problema NP-completo, cosa che non è affatto dimostrata e, anzi, ci sono forti indicazioni che portano a credere che non sia tale: se avete tempo, vi ri-consiglio caldamente tutte le lezioni del corso di Scott Aaronson: Quantum Computing Since Democritus; se avete fretta e vi interessa la questione della "difficoltà" della fattorizzazione, potete limitarvi alla lezione n° 6: P, NP, and Friends.

Che quello della fattorizzazione sia un problema NP-completo è un fraintendimento molto diffuso, io lo scoprii proprio quando mi imbattei nelle lectures di Scott Aaronson: in realtà molto probabilmente si tratta di un problema "più semplice" dei problemi NP-completi, per cui potrebbe benissimo darsi che si scopra che sia un problema "facile" (P) senza che ciò implichi che siano facili anche i problemi NP-completi (molto più probabilmente si tratta di un problema che ricade in un classe intermedia fra P e NP). Detto al contrario: anche se fossimo in grado di dimostrare che i problemi NP-completi sono "davvero" difficili, il problema della fattorizzazione dei numeri composti (e dunque il problema di violare un codice crittografico) potrebbe benissimo rientrare nella categoria dei problemi "facili" (P).

Tant'è che per il problema della fattorizzazione esiste un algoritmo quantistico (il famoso algoritmo di Shor) capace di risolverlo in tempo polinomiale, mentre — nonostante si senta spesso dire il contrario — non è noto alcun algoritmo quantistico capace di risolvere problemi NP-completi in tempo polinomiale, e se mai un giorno si dovesse scoprirne uno, sarebbe sicuramente molto diverso dall'algoritmo di Shor.

Vi siete persi?

Spero di riuscire a buttar giù un "riassuntino" della faccenda quanto prima (cioè: ho già cominciato a scrivere qualcosa, ma sta venendo più lungo di quel che credessi; così ho pensato di uscire subito con questo post giusto per (tentare di) restare "sulla notizia"...).

 

Prima di chiudere, però, vorrei dire due parole sul perché questa questione dell'equivalenza (o meno) delle classi P e NP mi appassiona tanto.

Il fatto è che non si tratta di uno dei problemi da un milione di dollari, o di uno dei più difficili problemi matematici ancora irrisolti, ma si tratta del Problema tout court: se tutti i problemi NP fossero risolvibili polinomialmente, sarebbe possibile programmare un computer per risolvere in poco tempo anche tutti gli altri problemi da un milione di dollari.

C'è addirittura chi crede che l'impossibilità algoritmica di risolvere problemi NP-completi in tempo polinomiale sia consustanziale alla stessa struttura fisica di cui è fatto il mondo.

Come chi?, ma Scott Aaronson, no? :-)