Saper dimostrare che un problema è NP-completo insegna a riconoscere la struttura comune di problemi lontanissimi. Qui seguo in dettaglio tre riduzioni classiche. Partono da 3-SAT, un problema di logica, e arrivano a tre problemi sui grafi. Lo schema che si impara qui si riutilizza quasi identico per molte altre dimostrazioni.
I problemi coinvolti
- 3-SAT: data una formula in forma normale congiuntiva in cui ogni clausola ha esattamente tre letterali, esiste un assegnamento che la soddisfa?
- Insieme indipendente (IS): dato un grafo G e un intero k, esistono k nodi a due a due non collegati?
- Cricca (CLIQUE): dato G e k, esistono k nodi a due a due collegati?
- Copertura di vertici (VC): dato G e k, esiste un insieme di k nodi tale che ogni arco abbia almeno un estremo nell'insieme?
Tutti stanno in NP: il certificato è l'assegnamento o l'insieme di nodi, e la verifica è immediata. Resta da mostrare che sono NP-difficili.
Riduzione 1: da 3-SAT a insieme indipendente
Sia φ una formula con m clausole. Costruiamo un grafo G così:
- Gadget delle clausole: per ogni clausola si creano tre nodi, uno per letterale, collegati fra loro a triangolo.
- Archi di conflitto: si collega ogni nodo etichettato x con ogni nodo etichettato ¬x, in qualunque clausola si trovino.
- Si pone k = m.
L'intuizione: scegliere un nodo in un triangolo significa scegliere quale letterale rende vera quella clausola. I triangoli impediscono di scegliere due nodi della stessa clausola; gli archi di conflitto impediscono di rendere veri insieme x e ¬x.
Correttezza, verso 1. Se φ è soddisfacibile, si fissa un assegnamento che la soddisfa. In ogni clausola almeno un letterale è vero: se ne sceglie uno per clausola. Si ottengono m nodi. Non sono nello stesso triangolo, e non ci sono archi di conflitto fra loro, perché un assegnamento non rende veri sia x sia ¬x. È un insieme indipendente di dimensione m.
Correttezza, verso 2. Se G ha un insieme indipendente di dimensione m, ogni triangolo ne contiene esattamente un nodo, perché due nodi dello stesso triangolo sono collegati. Si rendono veri i letterali corrispondenti; gli archi di conflitto garantiscono che non ci siano contraddizioni; le altre variabili si fissano a piacere. Ogni clausola ha un letterale vero, quindi φ è soddisfatta.
Costo. Il grafo ha 3m nodi e al più O(m²) archi: costruzione polinomiale.
Un esempio
φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z). Due triangoli: {x, y, ¬z} e {¬x, y′, z′}, dove l'apice indica la seconda copia. Archi di conflitto: x con ¬x, ¬z con z′. Con k = 2, l'insieme {y, y′} è indipendente: y e y′ sono in triangoli diversi e non sono in conflitto. Corrisponde all'assegnamento y = vero, che soddisfa entrambe le clausole.
Riduzione 2: da insieme indipendente a cricca
Il complemento di un grafo G, indicato con Ḡ, ha gli stessi nodi e un arco fra due nodi esattamente quando G non ce l'ha.
Un insieme S è indipendente in G se e solo se è una cricca in Ḡ: le coppie che in G non sono collegate in Ḡ lo sono tutte. La riduzione è quindi:
(G, k) ↦ (Ḡ, k)
Costruire Ḡ richiede di esaminare tutte le coppie di nodi, cioè tempo O(n²). CLIQUE è NP-completo.
Riduzione 3: da insieme indipendente a copertura di vertici
Sia G un grafo con n nodi. Vale un fatto semplice ma potente:
S è un insieme indipendente se e solo se V \ S è una copertura di vertici.
Infatti, se S è indipendente, nessun arco ha entrambi gli estremi in S, quindi ogni arco ha almeno un estremo fuori da S, cioè in V \ S. Il ragionamento si inverte senza difficoltà.
La riduzione è:
(G, k) ↦ (G, n − k)
Il grafo non cambia nemmeno: cambia solo la soglia. VC è NP-completo.
Che cosa insegnano queste riduzioni
| Riduzione | Tecnica | Idea |
|---|---|---|
| 3-SAT → IS | Gadget | Triangoli per le clausole, archi per le contraddizioni |
| IS → CLIQUE | Complemento | Mancanza di archi diventa presenza |
| IS → VC | Dualità | L'insieme e il suo complemento si scambiano i ruoli |
Alcune regole pratiche che uso nel costruire riduzioni:
- la direzione va dal problema noto al problema nuovo;
- ogni scelta nel problema di partenza deve avere un gadget corrispondente;
- i vincoli di coerenza, come «non x e ¬x insieme», diventano archi, numeri o clausole aggiuntive;
- bisogna dimostrare entrambe le direzioni del «se e solo se» e verificare che la costruzione sia polinomiale.
Conseguenze pratiche
IS, CLIQUE e VC sono quindi equivalenti per la risolvibilità esatta in tempo polinomiale, ma non lo sono per l'approssimazione: per la copertura di vertici esiste un algoritmo semplice che garantisce una soluzione al massimo doppia di quella ottima, mentre per la cricca non si conosce nulla di paragonabile e si sa che, se P ≠ NP, l'approssimazione è molto difficile. Le riduzioni polinomiali preservano la risposta sì o no, non la qualità delle soluzioni approssimate.
In sintesi
- Per provare la NP-completezza si mostra l'appartenenza a NP e si riduce da un problema NP-completo noto.
- Da 3-SAT a insieme indipendente: un triangolo per clausola e archi fra letterali opposti, con k uguale al numero di clausole.
- Insieme indipendente e cricca si scambiano passando al grafo complemento.
- S è indipendente se e solo se V \ S è una copertura di vertici: basta cambiare la soglia in n − k.
- Le riduzioni conservano la risposta esatta, non la qualità delle approssimazioni.
