Molti problemi difficili da risolvere hanno una caratteristica curiosa: se qualcuno ci propone una soluzione, controllarla è facile. Trovare un percorso che visiti ogni città esattamente una volta può richiedere una ricerca enorme; verificare che un percorso dato lo faccia richiede solo di scorrerlo. La classe NP cattura esattamente questa idea. È spesso fraintesa, a partire dal nome: NP non significa «non polinomiale».
Prima definizione: verificatori
Un verificatore per un linguaggio A è un algoritmo V che riceve due input: un'istanza w e una stringa aggiuntiva c, detta certificato (o testimone). Deve valere:
w ∈ A se e solo se esiste un certificato c tale che V accetta ⟨w, c⟩
Il verificatore è polinomiale se il suo tempo di esecuzione è polinomiale nella lunghezza di w. Di conseguenza anche il certificato utile deve avere lunghezza polinomiale, perché V non avrebbe il tempo di leggerne uno più lungo.
NP è la classe dei linguaggi che hanno un verificatore polinomiale.
Il punto chiave è l'asimmetria:
- se w ∈ A, esiste un certificato che convince il verificatore;
- se w ∉ A, nessun certificato lo convince.
Non si chiede di trovare il certificato, solo che esista e che sia controllabile rapidamente.
Seconda definizione: macchine non deterministiche
Una macchina di Turing non deterministica decide un linguaggio in tempo t(n) se ogni ramo di calcolo si ferma entro t(n) passi e la macchina accetta quando almeno un ramo accetta.
NP è la classe dei linguaggi decisi da una macchina non deterministica in tempo polinomiale. Da qui il nome: Nondeterministic Polynomial time.
Le due definizioni sono equivalenti:
- da verificatore a macchina non deterministica: la macchina «indovina» il certificato, scrivendone un simbolo per ramo, poi esegue il verificatore;
- da macchina non deterministica a verificatore: il certificato è la sequenza di scelte che porta a un ramo accettante, e il verificatore simula la macchina seguendo quelle scelte.
Esempi di certificati
| Problema | Istanza | Certificato | Verifica |
|---|---|---|---|
| SAT | Formula booleana | Assegnamento di verità alle variabili | Si valuta la formula |
| Cammino hamiltoniano | Grafo, nodi s e t | Sequenza di nodi | Ogni nodo compare una volta, archi presenti |
| Cricca | Grafo, intero k | Insieme di k nodi | Ogni coppia è collegata |
| Somma di sottoinsieme | Numeri e obiettivo T | Sottoinsieme dei numeri | La somma è T |
| Numeri composti | Intero N | Un divisore d con 1 < d < N | Si divide N per d |
| 3-colorabilità | Grafo | Colore di ogni nodo | Archi con estremi di colori diversi |
In tutti i casi la verifica è chiaramente polinomiale, mentre la ricerca ingenua prova un numero esponenziale di candidati: 2ⁿ assegnamenti, n! ordinamenti, 2ⁿ sottoinsiemi, 3ⁿ colorazioni.
Dove sta NP rispetto alle altre classi
Valgono queste inclusioni:
P ⊆ NP ⊆ EXPTIME
- P ⊆ NP: se un problema si risolve in tempo polinomiale, il verificatore può ignorare il certificato e risolvere direttamente.
- NP ⊆ EXPTIME: un verificatore polinomiale si trasforma in un algoritmo deterministico provando tutti i certificati possibili, che sono al più esponenziali in numero.
Si sa che P ≠ EXPTIME, grazie al teorema di gerarchia temporale. Quindi almeno una delle due inclusioni è stretta, ma non sappiamo quale. Se P = NP, la seconda sarebbe stretta; se NP = EXPTIME, la prima.
L'asimmetria fra sì e no
La definizione di NP tratta in modo diverso le risposte positive e negative. Per mostrare che una formula è soddisfacibile basta un assegnamento. Per mostrare che non lo è, non si conosce alcun certificato breve: in generale bisogna convincersi che nessuno dei 2ⁿ assegnamenti funziona.
La classe dei complementi dei problemi in NP si chiama coNP. Si congettura che NP ≠ coNP, ma anche questo è aperto. Alcuni problemi stanno in entrambe: per esempio la primalità, che sta in P, e la fattorizzazione nella sua versione decisionale.
Malintesi frequenti
- «NP vuol dire non polinomiale»: falso. Tutti i problemi di P sono anche in NP.
- «I problemi NP sono quelli difficili»: impreciso. I problemi più difficili di NP sono gli NP-completi; NP contiene anche problemi facili.
- «Un problema NP richiede tempo esponenziale»: non lo sappiamo. Se P = NP, ogni problema in NP avrebbe un algoritmo polinomiale.
- «I problemi di ottimizzazione sono in NP»: NP contiene problemi decisionali, con risposta sì o no. Le versioni di ottimizzazione si collegano a quelle decisionali aggiungendo una soglia: «esiste un percorso di lunghezza al massimo k?».
In sintesi
- NP è la classe dei problemi le cui risposte positive hanno certificati verificabili in tempo polinomiale.
- Equivalentemente, è la classe dei problemi decisi da una macchina non deterministica in tempo polinomiale.
- SAT, cammino hamiltoniano, cricca, somma di sottoinsieme e 3-colorabilità sono esempi tipici.
- Valgono P ⊆ NP ⊆ EXPTIME, e almeno un'inclusione è stretta.
- Le risposte negative non hanno in generale certificati brevi: da qui la classe coNP.
