Il problema P contro NP è probabilmente la domanda aperta più famosa dell'informatica teorica, ed è uno dei problemi del millennio scelti dal Clay Mathematics Institute. Si enuncia in una riga: ogni problema la cui soluzione si verifica rapidamente si può anche risolvere rapidamente? La maggior parte degli esperti ritiene che la risposta sia no, ma nessuno è riuscito a dimostrarlo. Vale la pena capire con precisione che cosa si chiede, che cosa dipende dalla risposta e perché le tecniche note non bastano.
La domanda in forma precisa
Sappiamo che P ⊆ NP: ciò che si risolve in tempo polinomiale si verifica anche in tempo polinomiale. La domanda è se l'inclusione sia stretta:
P = NP oppure P ≠ NP?
Grazie alla NP-completezza, la domanda si riduce a un singolo problema. Basta prendere SAT, o qualsiasi altro problema NP-completo:
- se SAT ha un algoritmo polinomiale, allora P = NP;
- se si dimostra che SAT non ne ha, allora P ≠ NP.
Scenario 1: P = NP
Se P = NP, ogni problema con soluzioni verificabili in fretta avrebbe anche un algoritmo polinomiale per trovarle. Le conseguenze dipenderebbero molto da come lo si dimostra.
- Una dimostrazione costruttiva ed efficiente, con un algoritmo di grado basso e costanti ragionevoli, sconvolgerebbe la pratica: molti problemi di pianificazione, scheduling, progettazione di circuiti e allocazione di risorse diventerebbero risolvibili in modo esatto.
- La crittografia a chiave pubblica come la conosciamo perderebbe le sue basi. Data una chiave pubblica, verificare che una chiave privata candidata sia quella giusta è facile; con P = NP lo diventerebbe anche trovarla. Più in generale non esisterebbero funzioni unidirezionali, cioè facili da calcolare e difficili da invertire.
- La ricerca di dimostrazioni diventerebbe meccanizzabile per dimostrazioni di lunghezza ragionevole: verificare una dimostrazione formale è facile, quindi lo diventerebbe anche trovarla.
Ma una dimostrazione di P = NP potrebbe anche essere non costruttiva, o fornire un algoritmo in n¹⁰⁰⁰. In quel caso il risultato teorico sarebbe enorme, ma l'impatto pratico immediato quasi nullo.
Scenario 2: P ≠ NP
È lo scenario ritenuto più probabile. Confermerebbe ciò che l'esperienza suggerisce: per i problemi NP-completi non esiste un algoritmo efficiente che funzioni su tutte le istanze. Ma anche qui servono precisazioni.
- P ≠ NP riguarda il caso peggiore. Molte istanze industriali di SAT, anche molto grandi, vengono risolte di routine dai solutori moderni. La difficoltà teorica non impedisce il successo pratico su istanze strutturate.
- P ≠ NP non basta per la crittografia. Questa richiede problemi difficili nel caso medio, cioè su istanze generate a caso, non solo su qualche istanza patologica. Servono ipotesi più forti di P ≠ NP.
- Resterebbero comunque aperte altre domande, come NP contro coNP o P contro PSPACE.
I problemi intermedi
Se P ≠ NP, ogni problema di NP è in P oppure è NP-completo? No. Il teorema di Ladner dimostra che, se P ≠ NP, esistono problemi in NP che non sono né in P né NP-completi: i problemi NP-intermedi.
Gli esempi costruiti nella dimostrazione sono artificiali, ma ci sono candidati naturali, problemi in NP per cui non si conosce né un algoritmo polinomiale né una dimostrazione di NP-completezza:
- la fattorizzazione degli interi, nella sua versione decisionale;
- l'isomorfismo di grafi: due grafi dati sono lo stesso grafo con i nodi rinominati?
- il logaritmo discreto.
Fattorizzazione e logaritmo discreto sono alla base di schemi crittografici molto diffusi: la loro sicurezza poggia proprio sul fatto che nessuno conosce algoritmi classici efficienti.
Perché è così difficile
Non è solo questione di mancanza di idee: sono stati dimostrati teoremi che escludono intere famiglie di tecniche.
- Relativizzazione. Esistono oracoli A per cui P^A = NP^A e oracoli B per cui P^B ≠ NP^B. Molte tecniche classiche, come la diagonalizzazione, funzionano allo stesso modo con qualsiasi oracolo. Quindi da sole non possono risolvere la questione.
- Dimostrazioni naturali. Una vasta classe di argomenti combinatori sui circuiti, se riuscisse a separare P da NP, permetterebbe anche di rompere generatori pseudocasuali che si ritengono sicuri. Questo rende improbabile che tali argomenti funzionino.
- Algebrizzazione. Un'estensione della barriera di relativizzazione esclude anche tecniche algebriche che avevano permesso altri risultati importanti.
Ogni dimostrazione di P ≠ NP dovrà quindi usare idee sostanzialmente diverse da quelle che hanno avuto successo finora.
Come convive il mondo reale con il dubbio
Nel lavoro quotidiano P contro NP non resta un'astrazione. Quando un problema si rivela NP-completo, le strategie sono note:
- sfruttare la struttura delle istanze reali, spesso molto più semplici del caso peggiore;
- accettare soluzioni approssimate con garanzie di qualità;
- usare euristiche e solutori specializzati, misurandone le prestazioni sulle istanze che contano;
- limitare un parametro del problema, come la dimensione di una soluzione, quando resta piccolo.
In sintesi
- P contro NP chiede se tutto ciò che si verifica in fretta si possa anche risolvere in fretta.
- Basta decidere la questione per un solo problema NP-completo, per esempio SAT.
- P = NP minerebbe le funzioni unidirezionali, ma l'impatto pratico dipenderebbe dall'efficienza dell'algoritmo.
- Se P ≠ NP, il teorema di Ladner garantisce problemi intermedi; fattorizzazione e isomorfismo di grafi sono candidati.
- Relativizzazione, dimostrazioni naturali e algebrizzazione escludono molte tecniche note.
