Fra i problemi di NP alcuni sono speciali: se uno solo di essi avesse un algoritmo polinomiale, allora tutti i problemi di NP lo avrebbero. Sono i problemi NP-completi. La loro esistenza non è affatto ovvia, e il teorema di Cook-Levin la dimostra esibendo il primo esempio: il problema della soddisfacibilità booleana, SAT. Da lì, una catena di riduzioni ha mostrato che moltissimi problemi pratici sono NP-completi.
Riduzioni in tempo polinomiale
La nozione chiave è una versione «a costo limitato» della riduzione di mappatura. A è riducibile in tempo polinomiale a B, scritto A ≤ₚ B, se esiste una funzione f calcolabile in tempo polinomiale tale che:
w ∈ A se e solo se f(w) ∈ B
La proprietà fondamentale: se A ≤ₚ B e B ∈ P, allora A ∈ P. Basta calcolare f(w), che ha lunghezza polinomiale, e applicare l'algoritmo per B. La composizione di polinomi è un polinomio.
Le definizioni
- Un problema B è NP-difficile se per ogni A in NP vale A ≤ₚ B.
- Un problema B è NP-completo se è NP-difficile e appartiene a NP.
Un problema NP-difficile può anche stare fuori da NP: per esempio il problema della fermata è NP-difficile, ma non è nemmeno decidibile.
Conseguenza diretta delle definizioni:
se un problema NP-completo sta in P, allora P = NP.
Per questo la NP-completezza è considerata una forte evidenza che non esista un algoritmo polinomiale.
Il problema SAT
Una formula booleana usa variabili x₁, …, xₙ, gli operatori AND (∧), OR (∨), NOT (¬) e le parentesi. È soddisfacibile se esiste un assegnamento di valori vero/falso alle variabili che la rende vera.
SAT = {⟨φ⟩ : φ è una formula booleana soddisfacibile}
SAT è in NP: il certificato è l'assegnamento, e valutare la formula richiede tempo lineare.
Il teorema di Cook-Levin
SAT è NP-completo.
Poiché SAT è in NP, resta da mostrare che ogni problema A in NP si riduce in tempo polinomiale a SAT. Non conosciamo A: sappiamo solo che esiste una macchina non deterministica N che lo decide in tempo nᵏ. La riduzione deve funzionare per qualunque N.
L'idea della tabella
Fissata un'istanza w di lunghezza n, ogni ramo di calcolo di N su w si può rappresentare come una tabella di dimensione nᵏ × nᵏ:
- ogni riga è una configurazione di N;
- la prima riga è la configurazione iniziale con input w;
- ogni riga segue dalla precedente secondo una transizione di N;
- qualche riga contiene lo stato accettante.
Una tabella che rispetta queste regole è una tabella accettante. N accetta w se e solo se esiste una tabella accettante. La riduzione costruisce una formula φ che è soddisfacibile esattamente quando una tale tabella esiste.
Le variabili
Per ogni cella (i, j) della tabella e per ogni simbolo s che può comparire (simboli del nastro e stati), si crea una variabile xᵢ,ⱼ,ₛ, che sarà vera quando la cella (i, j) contiene s. Sono O(n²ᵏ), un numero polinomiale.
Le quattro parti della formula
La formula è la congiunzione φ = φ_cella ∧ φ_inizio ∧ φ_mossa ∧ φ_accetta.
- φ_cella: ogni cella contiene esattamente un simbolo. Per ogni cella si richiede che almeno una variabile sia vera e che non ce ne siano due vere insieme.
- φ_inizio: la prima riga codifica la configurazione iniziale, con lo stato iniziale e l'input w seguito da blank.
- φ_accetta: in qualche cella compare lo stato accettante.
- φ_mossa: ogni riga segue legalmente dalla precedente.
La parte più interessante è φ_mossa. Il trucco è osservare che una transizione modifica solo le celle vicine alla testina. Basta quindi controllare tutte le finestre 2 × 3, cioè blocchi di tre celle adiacenti in una riga e le tre celle sotto. Una finestra è legale se è compatibile con la funzione di transizione. Si dimostra che, se la prima riga è corretta e tutte le finestre sono legali, ogni riga è una configurazione che segue dalla precedente.
Il numero di finestre legali possibili dipende solo da N, non da n: è una costante. Per ogni posizione si scrive una disgiunzione sulle finestre legali, e la dimensione totale di φ_mossa resta polinomiale.
Il costo della riduzione
La formula φ ha dimensione O(n²ᵏ) e si scrive in tempo polinomiale, semplicemente elencando i vincoli. Quindi A ≤ₚ SAT, per ogni A in NP.
Da SAT agli altri problemi
Una volta noto un problema NP-completo, per dimostrare che un nuovo problema B lo è servono solo due passi:
- mostrare che B è in NP, esibendo un certificato verificabile;
- ridurre in tempo polinomiale un problema NP-completo noto a B.
Per transitività delle riduzioni, ogni problema di NP si riduce allora a B. Il primo anello della catena è di solito 3-SAT, la versione di SAT in cui la formula è una congiunzione di clausole con esattamente tre letterali ciascuna. Anch'essa è NP-completa, e la sua struttura regolare la rende facile da trasformare in grafi, numeri o tabelle.
In sintesi
- A ≤ₚ B significa che esiste una trasformazione polinomiale che preserva la risposta.
- Un problema NP-completo sta in NP e ogni problema di NP vi si riduce; se uno di essi fosse in P, sarebbe P = NP.
- Il teorema di Cook-Levin mostra che SAT è NP-completo codificando in una formula la tabella di calcolo di una macchina.
- Le finestre 2 × 3 controllano la legalità delle mosse con un numero costante di casi.
- Per i problemi successivi basta ridurre da un problema NP-completo già noto, di solito 3-SAT.
