Obbiettivo di questa sezione `e quello di classificare dal punto di vista della complessit`a computazionale i problemi in NP, selezionando in particolare quelli computazionalmente difficili. A tal riguardo la nozione centrale `e la relazione di riducibilit`a polinomiale.
Definizione 13.2 Consideriamo due problemi di decisione π1 = hI1, q1i e π2 = hI2, q2i, dove I1 e I2 sono gli insiemi delle istanze, mentre q1 e q2 i rispettivi predicati. Diciamo che π1 `e polinomialmente
riducibile a π2, scrivendo π1<p π2, se esiste una funzione f : I1 −→ I2tale che: 1. f `e calcolabile in tempo polinomiale da una RAM secondo il criterio logaritmico, 2. per ogni x ∈ I1, q1(x) = 1 se e solo se q2(f (x)) = 1.
Diremo che f definisce una riduzione polinomiale da π1a π2o anche che π1 `e riducibile a π2mendiante la funzione f .
`
E facile verificare che la riduzione polinomiale gode della propriet`a transitiva. Infatti, dati tre prob-lemi di decisione π1 = hI1, q1i, π2 = hI2, q2i e π3 = hI3, q3i, se π1 <p π2mediante una funzione f , e π2 <pπ3mediante una funzione g, allora la funzione composta h(x) = g(f (x)) definisce una riduzione polinomiale da π1 a π3: per ogni x ∈ I1, q1(x) = 1 se e solo se q3(h(x)) = 1; inoltre la funzione h `e calcolabile da una RAM che, su input x ∈ I1, simula prima la macchina che calcola f , ottenendo f (x), e quindi la macchina che calcola g, ricavando g(f (x)). Il tempo richiesto da quest’ultimo calcolo `e comunque polinomiale perch´e maggiorato dalla composizione di due polinomi.
La nozione di riducibilit`a polinomiale permette di individuare una sorta di “ordine di difficolt`a ” dei problemi in NP. Il seguente risultato ci dice che se π1 <p π2 e π2 `e computazionalmente facile, cio`e appartiene a P, allora anche p1 `e computazionalmente facile.
Proposizione 13.3 Dati due problemi di decisione π1 = hI1, q1i e π2 = hI2, q2i, se π1 <p π2 e π2 appartiene a P, allora anche π1 appartiene a P.
Dimostrazione. Sia f la funzione che definisce una riduzione polinomiale da π1 a π2 e sia M una RAM che calcola f in tempo p(n), per un opportuno polinomio p. Se π2 ∈ P allora esiste una RAM M0che risolve π2in tempo q(n), dove q `e un’altro polinomio. Allora possiamo definire una RAM M00 che, su input x ∈ I1, calcola la stringa y = f (x) ∈ I2 simulando la macchina M ; quindi M00simula la macchina M0su input f (x) e mantiene la risposta di quest’ultima. Poich´e la lunghezza di f (x) `e al pi`u data da p(|x|), la complessit`a in tempo di M00 `e maggiorata da un polinomio:
TM00(|x|) ≤ p(|x|) + q(p(|x|))
Il risultato precedente permette di interpretare la relazione <pcome una relazione di “maggior diffi-colt`a computazionale” tra problemi. In questo contesto diventa allora interessante individuare i problemi computazionalmente pi`u difficili da risolvere, che chiameremo NP-completi e che saranno i massimi della relazione <p.
Definizione 13.3 Un problema di decisione π `e NP-completo se
1. π appartiene a NP,
2. per ogni π0∈ NP si verifica π0 <p π.
Intuitivamente i problemi NP-completi sono quindi i problemi pi`u difficili nella classe NP. L’esistenza di un algoritmo che risolve in tempo polinomiale un problema NP-completo implicherebbe l’equivalenza delle classi P e NP. Tuttavia l’ipotesi P=NP `e considerata molto improbabile, dato l’elevato numero di problemi in NP per i quali non sono stati trovati algoritmi polinomiali, anche se finora nessuno ha formalmente provato che le due classi sono diverse 3. Quindi dimostrare che un problema π `e NP-completo significa sostanzialmente provare che il problema `e intrattabile ovvero che, quasi certamente, π non ammette algoritmi di soluzione che lavorano in tempo polinomiale.
13.4.1 Riduzione polinomiale da SODD a CLIQUE
Presentiamo ora un esempio di riduzione polinomiale tra problemi di decisione.
Proposizione 13.4 SODD `e polinomialmente riducibile a CLIQUE.
Dimostrazione. Descriviamo una funzione f tra le istanze dei due problemi che definisce la riduzione. Sia φ una formula in FNC definita dalla uguaglianza
φ = E1· E2· . . . · Ek
dove Ei = (`i1+ `i2+ · · · + `iti) per ogni i = 1, 2, . . . , k, e ciascun `ij `e un letterale. Allora f (φ) `e l’istanza del problema CLIQUE data dall’intero k, pari al numero di clausole di φ, e dal grafo G = hV, Ei definito nel modo seguente:
3
Il problema di dimostrare che P `e diverso da NP `e considerato oggi uno dei pi`u importanti problemi aperti della teoria degli algoritmi.
- V = {[i, j] | i ∈ {1, 2, . . . , k}, j ∈ {1, 2, . . . , ti}}; - E = {{[i, j], [u, v]} | i 6= u, `ij 6= `uv}.
Quindi i nodi di G sono esattamente le occorrenze di letterali in φ, mentre i suoi lati sono le coppie di letterali che compaiono in clausole distinte e che non sono l’uno il negato dell’altro.
`
E facile verificare che la funzione f `e calcolabile in tempo polinomiale.
Proviamo ora che φ ammette un assegnamento che la rende vera se e solo se G ha una clique di dimensione k. Supponiamo che esista un tale assegnamento A. Chiaramente A assegna valore 1 ad almeno un letterale `iji per ogni clausola Ei di φ. Sia {j1, j2, . . . , jk} l’insieme degli indici di questi letterali. Allora l’insieme C = {[i, ji] | i = 1, 2, . . . , k} `e una clique del grafo G perch´e, se per qualche i, u ∈ {1, 2, . . . , k}, `iji = `uju, l’assegnamento A non potrebbe rendere veri entrambi i letterali.
Viceversa, sia C ⊆ V una clique di G di dimensione k. Allora, per ogni coppia [i, j], [u, v] in C, abbiamo i 6= u e `ij 6= `uv. Sia ora S1l’insieme delle variabili x tali che x = `ij per qualche [i, j] ∈ C. Analogamente, denotiamo con S0 l’insieme delle variabili y tali che y = `ij per qualche [i, j] ∈ C. Definiamo ora l’assegnamento A che attribuisce valore 1 alle variabili in S1 e valore 0 alle variabili in S0. A `e ben definito perch´e, essendo C una clique, l’intersezione S1∩ S0 `e vuota. Inoltre A rende vera la formula φ, perch´e per ogni clausola Ei vi `e un letterale `iji che assume valore 1.
13.4.2 Riduzione polinomiale da SODD a 3-SODD
Il problema SODD pu`o essere ridotto polinomialmente anche a una sua variante che si ottiene restrin-gendo le istanze alle formule booleane in FNC che possiedono solo clausole con al pi`u 3 letterali.
3-SODD
Istanza: un formula booleana ψ = F1· F2· . . . · Fk, dove Fi = (`i1+ `i2+ `i3) per ogni i = 1, 2, . . . , k e ogni `ij `e una variabile o una variabile negata.
Domanda: esiste una assegnamento di valori 0 e 1 alle variabili che rende vera ψ?
Proposizione 13.5 SODD `e polinomialmente riducibile a 3-SODD.
Dimostrazione. Sia φ una formula booleana in FNC e sia E = (`1+ `2+ · · · + `t) una clausola di φ dotata di t ≥ 4 letterali. Sostituiamo E in φ con un prodotto di clausole f (E) definito da
f (E) = (`1+ `2+ y1) · (`3+ y1+ y2) · (`4+ y2+ y3) · . . . · (`t−2+ yt−4+ yt−3) · (`t−1+ `t+ yt−3) dove y1, y2, . . . , yt−3sono nuove variabili.
Proviamo ora che esiste un assegnamento che rende vera la clausola E se e solo se ne esiste uno che rende vera f (E). Infatti, se per qualche i `i = 1, basta porre yj = 1 per ogni j < i − 1 e yj = 0 per ogni j ≥ i − 1; in questo modo otteniamo un assegnamento che rende vera f (E). Viceversa, se esiste un assegnamento che rende vera f (E) allora deve esistere qualche letterale `i che assume valore 1. Altrimenti `e facile verificare che il valore di f (E) sarebbe 0. Ne segue che lo stesso assegnamento rende vera la E.
Operando questa sostituzione per tutte le clausole di φ dotate di pi`u di 3 addendi, otteniamo una formula 3-FNC che soddisfa le condizioni richieste. `E inoltre evidente che il tempo di calcolo necessario per realizzare la sostituzione `e polinomiale.