Np Completezza

1.4 Problemi NP-completi

ma il suo insieme di istanze positive corrisponde alle istanze negative di S ODDISFACIBILIT A` , e viceversa. Alla luce di quanto suesposto, verificare se una istanza (X , F) di FALSIT A` e` una istanza positiva, corrispondendo a verificare se la stessa istanza e` istanza negativa di S ODDISFACIBI ` , risulta essere inerentemente diverso (e probabilmente pi`u difficile) rispetto al caso in cui LIT A si intenda verificare se (X , F) e` istanza positiva di S ODDISFACIBILIT A` .

1.4 Problemi NP-completi Il concetto di problema completo in una determinata classe rispetto ad una certa riducibilit`a e` stato introdotto nella Definizione ??. Possiamo quindi definire un problema P ∈ NP come NP-completo se P e` completo in NP rispetto alla Karp-riducibilit`a polinomiale, vale a dire che p P e` NP-completo se, per ogni P1 ∈ NP, P1 ≤m P. p La relazione P1 ≤m P fa s`ı che saper risolvere P in tempo polinomiale comporti saper risolvere in tempo polinomiale anche P1 . Infatti, sia A un algoritmo polinomiale che decide P: allora, dato che per ipotesi deve esistere una Karp-riduzione polinomiale R da P1 a P, ogni istanza x di P1 pu`o essere decisa trasformandola in tempo polinomiale, mediante R, in una istanza R(x) di P ed applicando quindi A a tale istanza. Inoltre, la Karp-riducibilit`a polinomiale presenta l’ulteriore propriet`a che la classe NP, cos`ı come le classi P e PSPACE, e` chiusa rispetto ad essa (vedi Esercizio ??). Da ci`o deriva che, dati p due problemi P1 e P2 , se P1 e` NP-completo e P2 ≤m P1 , allora P2 ∈ NP. I problemi NP-completi possono svolgere un ruolo importante nell’ambito della determinazione della verit`a o della falsit`a della relazione P = NP: infatti, dato che ogni problema in NP e` per definizione riducibile ad un problema NP-completo, la possibilit`a di risolvere in tempo polinomiale un problema NP-completo comporterebbe che P = NP. Cos`ı come gi`a osservato per la classe P, il metodo pi`u naturale per mostrare l’NP-completezza di un problema di decisione P e` quello di trovare una Karp riduzione polinomiale da qualche altro problema P1 che gi`a si sa essere NP-completo. Infatti, dato che per ogni P2 ∈ NP p p si ha per definizione che P2 ≤m P1 , mostrare che P1 ≤m P comporta, per la transitivit`a della p Karp-riducibilit`a polinomiale (vedi Esercizio ??), che P2 ≤m P, e quindi che P e` NP-completo. Chiaramente, come gi`a evidenziato nella Sezione 1.1 per la P-completezza, questo processo richiede un problema NP-completo iniziale, la cui completezza deve evidentemente essere dimostrata mediante una qualche tecnica di tipo diverso. L’importanza del teorema di Cook, presentato sotto, sta proprio nel fatto che tale teorema mostra che ogni problema in NP e` polinomialmente Karp riducibile al problema S ODDISFA `. CIBILIT A Teorema 1.5 (Cook) Il problema S ODDISFACIBILIT A` `e NP–completo (rispetto alla Karp-riducibilit`a polinomiale). 19

Capitolo 1 – Trattabilita` ed intrattabilita`

Dimostrazione. Il problema si pu`o facilmente mostrare essere in NP: a tale scopo e` sufficiente considerare l’algoritmo non deterministico per S ODDISFACIBILIT A` presentato come Algoritmo 1.2. Come e` possibile verificare, l’algoritmo genera mediante una guess una assegnazione input X : insieme di variabili booleane, (c1 , . . . , cn ): insieme di clausole su V ; output boolean; begin guess una assegnazione f : X #→{TRUE,FALSE}; for each clausola ci ∈ F do if non esiste alcun ti,j ∈ ci soddisfatto da f then return NO; return VERO end.

Algoritmo 1.2: Algoritmo non deterministico per S ODDISFACIBILIT A` .

f , di lunghezza polinomiale, per poi verificare, in tempo polinomiale, che f soddisfa F. Alternativamente, S ODDISFACIBILIT A` pu`o essere dimostrato appartenere ad NP semplicemente osservando che l’assegnazione f e` un certificato di lunghezza polinomiale e verificabile in tempo polinomiale. Passiamo ora a mostrare, per mezzo di una tecnica di riduzione basata sul concetto di tableau, introdotto nella dimostrazione del Teorema 1.1, che, per ogni problema P ∈ NP, e` possibile definire una Karp-riduzione polinomiale da P a S ODDISFACIBILIT A` . La dimostrazione procede nel modo seguente, in cui per semplicit`a di esposizione facciamo riferimento al linguaggio L associato a P ed al linguaggio SAT associato a S ODDISFACIBILIT A` . ¯ Q, q0 , F , & una macchina di Turing non deterministica Dato che L ∈ NP,sia M = % , b, che accetta ogni stringa x ∈ L con | x |= n in tempo al pi`u p(n), dove p e` un opportuno polinomio, e sia d il grado di non determinismo di M. Sia inoltre m =| Q |. Dati M ed x ∈ ∗ , costruiremo una formula in forma normale congiuntiva tale che e` soddisfacibile se e solo se M accetta x in tempo al pi`u p(n), cio`e se e solo se x ∈ L. Al fine di semplificare la dimostrazione, e senza perdere in generalit`a, facciamo le seguenti ipotesi relativamente ad M: 1. M ha un solo nastro semi-infinito; 2. all’inizio, il nastro contiene la stringa in input x nelle prime n celle, mentre tutte le altre celle contengono il simbolo b. ¯ Analogamente al caso della dimostrazione del Teorema 1.1, consideriamo, senza perdita di ¯ Q, q0 , F , " &, la cui funzione generalit`a, la macchina di Turing non deterministica M" = % ,b, 20

1.4 Problemi NP-completi

di transizione e` definita nel modo seguente: "

(q, a) =

!

(q, a) se (q, a) e` definita {(q, a, i)} altrimenti.

La macchina di Turing M" ha lo stesso comportamento di M eccetto che ad ogni computazione massimale di M corrisponde una computazione di M" che cicla indefinitamente sulla stessa configurazione. Quindi, ad ogni computazione accettante di M corrisponde una computazione di M" che cicla su una configurazione di accettazione. Ricordiamo inoltre che, dato che ogni computazione accettante ha lunghezza al pi`u p(n), non pi`u di p(n) + 1 celle del nastro sono coinvolte nella computazione stessa. Inoltre, per ogni coppia (qi , aj ) con qi ∈ Q e aj ∈ ¯ , sia Di,j = (s0 , s1 , . . . , sr ) una qualunque enumerazione degli elementi di M! (qi , aj ) e sia di,j =| Di,j |. Ogni computazione eseguita da M" , in presenza di una specifica guess, su input x pu`o essere rappresentata, cos`ı come nella dimostrazione del Lemma 1.5, mediante un tableau T di dimensione (p(n)+1)×(p(n)+1), i cui elementi contengono coppie in ¯ ×(Q ∪{⊥}), con ⊥*∈ Q. Tale tableau deve soddisfare alcune propriet`a: anzitutto, ogni riga deve rappresentare una configurazione lecita di M" ; inoltre, la prima riga deve rappresentare la configurazione iniziale con x sulle prime n celle del nastro; infine, ogni riga deve rappresentare una configurazione derivata dalla configurazione rappresentata nella riga precedente mediante l’applicazione della funzione di transizione di M" . Si osservi poi che, per quanto detto, la condizione x ∈ L e` vera se e solo se esiste una computazione rappresentata da un tableau la cui ultima riga descrive una configurazione di accettazione. La formula che deriviamo rappresenta in modo formale le condizioni che devono essere verificate affinch´e un tableau rappresenti una computazione di accettazione di x, e si basa sui seguenti predicati, rappresentati nella formula da variabili booleane: k (0 ≤ i ≤ p(n), 0 ≤ j ≤ p(n), 0 ≤ k ≤ m), definita come S k se e solo se il secondo 1. Si,j i,j componente del contenuto di T [i, j] e` ⊥, se k =| Q |, o qk , se k <| Q |. k (0 ≤ i ≤ p(n), 0 ≤ j ≤ p(n), 0 ≤ k ≤| |), definita come C k se e solo se il primo 2. Ci,j i,j componente del contenuto di T [i, j] e` b, ¯ se k = 0, o ak , se k > 0.

3. Mik (1 ≤ i ≤ p(n), 1 ≤ k ≤ d), definita come Mik se e solo se all’i-esimo passo della computazione, la mossa eseguita e` la k-esima nell’insieme delle mosse possibili, che sono al pi`u d. La formula e` la congiunzione di 4 diverse formule, = M ∧ I ∧ A ∧ T , che codificano le propriet`a, sopra illustrate, che devono essere verificate da un tableau che rappresenti una computazione di accettazione. In particolare: 21

Capitolo 1 – Trattabilita` ed intrattabilita`

1. 2.

" M M = M e la riga i-esima di T rappresenti i i , dove i specifica le condizioni affinch´ una configurazione di M" ; I specifica che la prima riga di T deve rappresentare la configurazione iniziale di M" con input x;

A specifica che l’ultima riga di T deve rappresentare una configurazione di accettazione di M" ; " N 4. N = i N e all’i-esimo passo di computazione i , dove i specifica le condizioni affinch´ corrisponda l’esecuzione di una ed una sola tra le mosse possibili;

3.

5.

T specifica che ogni riga di T deve rappresentare una configurazione che deriva da quella rappresentata dalla riga precedente applicando la funzione di transizione di M.

Vediamo ora pi`u in dettaglio come le varie sottoformule di 1.

M i

e` la congiunzione di tre formule

M i

=

M1 i

∧

sopra introdotte sono definite. M2 i

∧

M3 i .

Dove:

M1 i

(a)

specifica che ogni cella T [i, j] deve rappresentare uno ed un solo valore come primo componente.Ci` o viene$ottenuto esprimendo tale formula come congiunzio" # M 11 1 = M 12 di coppie di sottoformule, in cui: ne M i i,j ∧ i,j j % k M 11 - i,j = k Ci,j specifica che T [i, j] deve rappresentare almeno un valore come primo componente; # $ " 12 = h k - M i,j h#=k Ci,j ∨ Ci,j specifica che la cella T [i, j] deve rappresentare al pi`u un valore come primo componente.

(b)

M 2 specifica che ogni cella T [i, j] deve rappresentare uno ed un solo valore come i secondo componente. Ci`o viene$ottenuto esprimendo tale formula come congiun" # M 21 2 = M 22 di due sottoformule, in cui: zione M i i,j ∧ i,j j % 21 = k - M i,j k Si,j specifica che T [i, j] deve rappresentare almeno un valore come secondo componente; # $ " 22 = h k - M i,j h#=k Si,j ∨ Si,j specifica che la cella T [i, j] deve rappresentare al pi`u un valore come secondo componente.

(c)

M3 specifica che esattamente una cella T [i, j] deve avere come secondo compoi nente un valore diverso da m =| Q |. Ci`o viene ottenuto esprimendo tale formula 3 31 32 = M ∧ M di due sottoformule, in cui: come congiunzione M i i i % m M 31 - i = j Si,j specifica che almeno una cella T [i, j] deve avere come secondo componente un valore diverso da m (corrispondente al simbolo ⊥);

22

1.4 Problemi NP-completi

-

$ " # m m = j#=l Si,j ∨ Si,l specifica che al pi`u una cella T [i, j] deve avere come secondo componente un valore diverso da m. M 32 i

Come si pu`o vedere, M e` in CNF ed ha lunghezza O(p(n)3 log n), in quanto e` composta da O(p(n)3 ) variabili booleane, ognuna identificata mediante O(log n) bit. Inoltre, la formula e` derivabile in tempo O(p(n)3 log n). 2.

I

e` la congiunzione di due formule

I

=

I1

∧

I 2.

Dove:

(a)

specifica il contenuto iniziale del nastro di M" , vale a dire i valori delle prime componenti in tutte le celle T [0, j]. Se x = ai0 ai1 . . . ain−1 e` la stringa in input, in−1 i0 i1 0 ∧ . . . ∧ C0 allora si avr`a I 1 = C0,0 ∧ C0,1 ∧ . . . ∧ C0,n−1 ∧ C0,n 0,p(n) .

(b)

I 2 specifica, attraverso i valori delle seconde componenti in tutte le celle T [0, j], che inizialmente la macchina di Turing M" si trova nello stato q0 e la sua testina e` 0 ∧S m ∧. . .∧S m posizionata sulla prima cella del nastro. Si ha quindi I 2 = S0,0 0,1 0,p(n) .

I1

Chiaramente, I e` in CNF (in effetti e` composta da tutte clausole comprendenti un unico termine), ha lunghezza O(p(n) log n) ed e` derivabile in tempo O(p(n) log n). 3.

Ae ` la disgiunzione di | F | formule booleane, ognuna delle quali specifica la condizione che M si trovi stato qk ∈ F , con la testina su una delle p(n) + 1 celle di nastro: #%nello $ % A = k . S qk ∈F j 0,j

Anche A e` chiaramente in CNF (in particolare, e` composta da un’unica clausola), ha lunghezza O(p(n) log n) ed e` derivabile in tempo O(p(n) log n). " N 4. N = i N i , dove i specifica che l’i-esimo passo di computazione corrisponde alla scelta di una ed una sola tra le mosse possibili. N1 N2 Si ha quindi che N i = i ∧ i , in cui: % 1 = k - N i k Mi specifica che l’i-esimo passo di computazione corrisponde alla scelta di almeno una tra le mosse possibili; # $ " 2 = h k specifica che l’i-esimo passo di computazione corri- N i h#=k Mi ∨ Mi sponde alla scelta di al pi`u una tra le mosse possibili.

Anche 5.

T

N

e` in CNF, ha lunghezza O(p(n) log n) ed e` derivabile in tempo O(p(n) log n).

"

= i Ti , dove Ti specifica le condizioni affinch´e la riga i-esima di T rappresenti una configurazione di M" derivata, attraverso l’applicazione della funzione di transizione , dalla configurazione rappresentata alla riga (i − 1)-esima. A sua volta, ogni formula 23

Capitolo 1 – Trattabilita` ed intrattabilita`

" ha la struttura Ti = j Ti,j , dove Ti,j specifica che il contenuto delle cella T [i, j] del tableau deve poter derivare, per mezzo della funzione di transizione, dal contenuto delle celle T [i − 1, j − 1], T [i − 1, j], T [i − 1, j + 1].6 % % % In particolare, poniamo Ti,j = qs ∈Q at ∈ ¯ 1≤k≤ds,t Ti,j,s,t,k , in cui Ti,j,s,t,k esprime la condizione che il contenuto della cella T [i, j] derivi dall’applicazione, al passo precedente, della k-esima transizione in M! (qs , at ). T i

Per definire la formula

T i,j,s,t,k

distinguiamo i casi seguenti:

- la testina non e` posizionata sulle celle j −1, j o j +1 dell’i −1-esima configurazione: in tal caso, il contenuto della j-esima cella rimane invariato nell’i-esima configurazione, e la testina non viene posizionata su tale cella. Questa condizione viene espressa, per ogni carattere ar ∈#¯ che pu`o comparire come secondo $componente m m m r ∧ Si−1,j ∧ Si−1,j+1 ∧ Ci−1,j in T [i, j−1] dalla implicazione Si−1,j−1

r . =⇒ Ci,j

0 : Ci`o d`a luogo alla seguente definizione di Ti,j,s,t,k $ &# T0 r m m m r Si−1,j−1 ∨ Si−1,j ∨ Si−1,j+1 ∨ Ci−1,j ∨ Ci,j i,j,s,t,k = r

- la testina e` posizionata sulla cella j − 1 dell’i − 1-esima configurazione: in tal caso, il contenuto della j-esima cella rimane invariato nell’i-esima configurazione, ma elemenla testina pu`o essere posizionata su tale cella. #Sia (ql , ap , mq ) il k-esimo $ s t to di M! (qs , at ), e sia mq = d, allora si ha Si−1,j−1 ∧ Ci−1,j−1 ∧ Mik # $ p l ∧C 0 Si,j o deriva la definizione di Ti,j,s,t,k come i,j−1 . Da ci` # $ p T0 l s t k i,j,s,t,k = Si−1,j−1 ∨ Ci−1,j−1 ∨ Mi ∨ Si,j ∧ Ci,j−1

=⇒

s t ∧ Ci−1,j+1 ∧ Mik mento di M! (qs , at ) e sia mq = s, allora si ha Si−1,j+1 # $ p l T 0 Si,j ∧ Ci,j+1 . Da ci`o deriva la definizione di i,j,s,t,k come # $ p T0 l s t k i,j,s,t,k = Si−1,j+1 ∨ Ci−1,j+1 ∨ Mi ∨ Si,j ∧ Ci,j+1

=⇒

Altrimenti, nel caso in cui mq *= d, nella formula non compare alcuna espressione per Ti,j,s,t,k . - la testina e` posizionata sulla cella j + 1 dell’i − 1-esima configurazione: in tal caso, il contenuto della j-esima cella rimane invariato nell’i-esima configurazione, ma la testina pu`o essere posizionata su tale cella. # Sia (ql , ap , mq ) il k-esimo $ ele-

6 In particolare, se j = 0 la formula Ti,0 si riferir`a alle sole celle T [i − 1, 0], T [i − 1, 1], mentre se j = p(n) la formula Ti,p(n) si riferir`a alle sole celle T [i − 1, p(n) − 1], T [i − 1, p(n)].

24

1.4 Problemi NP-completi

Altrimenti, nel caso in cui mq *= s, nella formula non compare alcuna espressione per Ti,j,s,t,k . - la testina e` posizionata sulla cella j dell’i−1-esima configurazione: in tal caso, il contenuto della j-esima cella pu`o cambiare nell’i-esima configurazione. Sia (ql , ap , mq$) # s t il k-esimo elemento di M! (qs , at ) e sia mq = i, allora si ha Si−1,j ∧ Ci−1,j ∧ Mik # $ p l T 0 =⇒ Si,j ∧ Ci,j . Da ci`o deriva la definizione di i,j,s,t,k come # $ p T0 l s t k i,j,s,t,k = Si−1,j ∨ Ci−1,j ∨ Mi ∨ Si,j ∧ Ci,j

Altrimenti, nel caso in cui mq *= i, nella formula non compare alcuna espressione per Ti,j,s,t,k . Si osservi che ogni formula Ti,j e` composta da una quantit`a costante di predicati C ed S, ognuno dei quali ha dimensione O(log n). Pur non essendo in CNF, ogni formula pu`o poi essere facilmente trasformata in una formula ˆ Ti,j in CNF equivalente, anch’essa composta da O(1) predicati, e quindi anch’essa di dimensione O(log n). Da ci`o deriva che l’intera formula tempo O(p(n)2 log n).

T

ha dimensione O(p(n)2 log n) ed e` derivabile in

Se si considera ora l’intera formula , e` possibile verificare che la componente dominante nella sua dimensione e` quella relativa alla dimensione di M , dal che risulta che la dimensione di e` O(p(n)3 log n), e l’intera formula pu`o essere derivata in tempo O(p(n)3 log n). Lasciamo per esercizio (vedi Esercizio 1.7) la semplice verifica che la formula e` soddisfacibile se e solo se esiste una computazione accettante di M. !

Esercizio 1.6 Verificare che, nella dimostrazione del teorema precedente, la formula e` soddisfacibile, dato un certo input x, se e solo se esiste una computazione accettante di M a partire da tale input.

Una volta individuato, mediante il teorema di Cook, un primo problema NP-completo e` possibile ora fare riferimento alla tecnica standard per provare che un problema P e` NPcompleto. Tale tecnica, riassumiamo, e` basata su due passi: 1. dimostrare che P ∈ NP; p

2. dato un problema P " NP-completo, mostrare che P " ≤m P, fornendo una procedura che, in tempo polinomiale, trasforma ogni istanza di P " in una istanza equivalente di P. 25

Capitolo 1 – Trattabilita` ed intrattabilita`

Come primo esempio di dimostrazione “standard” di NP-completezza, mostriamo che il problema 3-S ODDISFACIBILIT A` , ottenuto da S ODDISFACIBILIT A` considerando nella sua definizione soltanto clausole aventi 3 termini, e` NP-completo. 3-S ODDISFACIBILIT A` I STANZA : Una formula CNF F su un insieme X di variabili booleane, con ogni clausola composta da esattamente 3 termini. P REDICATO : Esiste una assegnazione f : X #→ {VERO , FALSO } che soddisfa F? Teorema 1.6 Il problema 3-S ODDISFACIBILIT A` `e NP-completo. Dimostrazione. Mostriamo inizialmente che 3-S ODDISFACIBILIT A` e` in NP: infatti, data F, una assegnazione f : X #→ {VERO , FALSO } e` chiaramente un certificato di lunghezza polinomiale verificabile in tempo polinomiale. p Al fine di provare che 3-S ODDISFACIBILIT A` ≤m S ODDISFACIBILIT A` mostriamo dapprima una possibile riduzione da istanze di S ODDISFACIBILIT A` ad istanze di 3-S ODDISFACIBILIT A` . Consideriamo un’istanza generica (X , C ) di 3-S ODDISFACIBILIT A` , dove X = {x1 , x2 , . . . , xn } e` un insieme di variabili booleane e C = {c1 , c2 , . . . , cm } e` un insieme di clausole su X . Da (X , C ) otterremo una istanza (X " , C " ) di 3-S ODDISFACIBILIT A` in cui da ogni clausola ci ∈ C vengono derivati un insieme di clausole a tre termini Ci" definite su X e su un insieme di variabili Xi" tali che X ∩ Xi = ∅: di conseguenza, si avr`a che l’istanza di 3-S ODDISFACIBILIT A` " " m " risultante avr`a X " = X ∪ (∪m i=1 Xi ) e C = ∪i=1 Ci . Il numero e la struttura delle clausole in Ci" dipenderanno dal numero | ci | di termini nella clausola ci nel modo seguente: 1. | ci |= 1. Sia ci = {z}: allora, Xi" = {yi1 , yi2 } e Ci" = {{z1 , yi1 , yi2 }, {z1 , y1i , yi2 }, {z1 , yi1 , y2i }, {z1 , y 1i , y 2i }}. Si noti che una assegnazione che soddisfa ci (che cio`e rende vero il termine z), comunque esteso a piacere a yi1 , yi2 soddisfa anche Ci" ; inoltre, una assegnazione che soddisfa Ci" dovr`a necessariamente rendere z vero (altrimenti una delle quattro clausole non pu`o essere soddisfatta) e, quindi, soddisfa anche ci . Da ci`o possiamo concludere che l’insieme di clausole in Ci" e` soddisfatto da tutti e soli gli assegnamenti (comunque estesi) tali che z = VERO , gli assegnamenti cio`e che soddisfano ci . 2. | ci |= 2. Sia ci = {z, v}: allora, Xi" = {yi1 } e Ci" = {{z, v, yi1 }, {z, v, y 1i }}. Si noti che una assegnazione che soddisfa ci (che cio`e rende vero uno almeno tra i termini z e v), comunque esteso a piacere a yi1 soddisfa anche Ci" ; inoltre, una assegnazione che soddisfa Ci" dovr`a necessariamente rendere almeno un termine tra z e v vero (altrimenti una delle due clausole non pu`o essere soddisfatta) e, quindi, soddisfa anche ci . In questo caso, le due clausole in Ci" sono soddisfatte da tutti e soli gli assegnamenti (comunque estesi) tali che z = VERO o v = FALSO , e quindi da tutti e soli gli assegnamenti che soddisfano ci . 26

1.4 Problemi NP-completi

3. | ci |= 3. Sia ci = {z, v, w}: dato che in questo caso ci ha esattamente i tre termini richiesti nella definizione di 3-S ODDISFACIBILIT A` , Xi" = ∅ e Ci" = {{z, v, w}}. Chiaramente, Ci" e` soddisfatta da tutti e soli gli assegnamenti che soddisfano ci . j

4. | ci |= k ≥ 4. Sia ci = {z1 , z2 , . . . , zk }: allora avremo Xi" = {yi , 1 ≤ j ≤ k − 3} e , zk−2 , yik−3 }, {y k−3 , zk−1 , zk }}. Ci" = {{z1 , z2 , yi1 }, {y1i , z3 , yi2 }, {y2i , z4 , yi2 }, . . . , {yk−4 i i In questo caso, si noti che una assegnazione f che soddisfa ci dovr`a rendere almeno un termine in {zi . . . , zk } vero: sia zr il primo di tali termini (siano cio`e tutti i termini zj con j < i posti a falso dall’assegnazione), allora, l’estensione f " di f in cui yi1 = VERO , yi2 = VERO , . . . , yir−2 = VERO , yir−1 = VERO , . . . , yik−3 = FALSO soddisfa l’insieme di clausole Ci" . Inoltre, si osservi che una assegnazione f " che soddisfa Ci" dovr`a necessariamente porre a vero almeno un termine zr (altrimenti una delle clausole non viene j soddisfatta, indipendentemente dai valori assegnati alle variabili yi ): evidentemente, tale assegnazione soddisfer`a anche ci . Da quanto detto, si pu`o concludere che (1) se esiste una assegnazione f su X che soddisfa C , esso pu`o essere esteso, come illustrato sopra, ad ottenere una assegnazione f " su X " che soddisfa C " e (2) se esiste una assegnazione f " su X " che soddisfa C " , la stessa assegnazione soddisfa anche C. Da ci`o evidentemente deriva che C e` soddisfacibile se e solo se lo e` C " . Si osservi infine che la trasformazione pu`o chiaramente essere effettuata in tempo polinomiale, e precisamente O(nm). ! Come altro esempio di dimostrazione di NP-completezza, mostriamo ora che il seguente problema C OPERTURA CON N ODI e` NP-completo. C OPERTURA

CON

N ODI

I STANZA : Grafo G = (V , E), intero K > 0 P REDICATO : Esiste un sottoinsieme V " ⊆ V tale che | V " |≤ K e ∀(u, v) ∈ E u ∈ V " o v ∈ V "? Teorema 1.7 Il problema C OPERTURA

CON

N ODI `e NP-completo.

Dimostrazione. Mostriamo che C OPERTURA CON N ODI appartiene ad NP: infatti, dato un sottoinsieme V " ⊆ V tale che | V " |≤ K e ∀(u, v) ∈ E u ∈ V " o v ∈ V " e` chiaramente un certificato di lunghezza polinomiale, verificabile in tempo polinomiale. Per provare la completezza di C OPERTURA CON N ODI in NP, mostriamo che 3-S ODDI ` ≤pm C OPERTURA CON N ODI. Sia data una istanza generica (X , C ) di 3-S ODDI SFACIBILIT A ` : a partire da (X , C ) deriviamo un grafo G = (V , E) ed un intero K > 0 tali che SFACIBILIT A 27

Capitolo 1 – Trattabilita` ed intrattabilita`

G ha una copertura con nodi di dimensione non superiore a K se e solo se l’insieme di clausole C e` soddisfacibile. L’insieme V dei nodi di G e` definito come segue: • ad ogni variabile xi ∈ X sono associati due nodi xi , x i ∈ V ; • ad ogni clausola cj ∈ C sono associati tre nodi cj1 , cj2 , cj3 ∈ V . Per quanto riguarda l’insieme E degli archi di G (vedi Figura 1.8): • esiste un arco (xi , x i ) ∈ E per ogni xi ∈ X ; • per ogni clausola cj = {tj1 , tj2 , tj3 } ∈ C , introduciamo tre archi (cj1 , cj2 ), (cj2 , cj3 ), (cj3 , cj1 ). Inoltre, introduciamo un arco per ogni termine tjs (s = 1, 2, 3) in cj nel modo seguente: sia tjs = xk ∈ X : introduciamo allora un arco (cjs , xk ) se tjs = xk o un arco (cjs , x k ) se tjs = x k . Si osservi che | V |= 2 | X | + 3 | C | e che | E |=| X | + 6 | C |, e che la trasformazione pu`o essere effettuata in tempo polinomiale. Poniamo inoltre K =| X | + 2 | C |. Ad una prima analisi, si pu`o verificare che non esistono coperture di nodi su G di taglia inferiore a K : infatti, per ognuno degli | X | archi del tipo (xi , x i ) almeno uno tra i due nodi estremi dovr`a essere inserito in una copertura, mentre per ognuna delle | C | componenti cj1 , cj2 , cj3 almeno due dei tre nodi devono a loro volta entrare a far parte della copertura stessa. Mostriamo ora che se (X , C ) e` soddisfacibile allora esiste una copertura V " di taglia K su G. Sia f una assegnazione che soddisfa (X , C ): allora, per ogni variabile xi , se f (xi ) = VERO inseriamo in V " il nodo xi , altrimenti inseriamo il nodo x i . Inoltre, per ogni clausola cj = {tj1 , tj2 , tj3 }, sia tjs ∈ cj un termine, che deve necessariamente esistere, tale che f (tjs ) = VERO : inseriamo allora in V " i due nodi {cjr | r *= s}. E` immediato verificare che tale insieme di K nodi rappresenta effettivamente una copertura di nodi di G. Per quanto riguarda l’implicazione inversa, sia V " una copertura dei nodi di G con | V " |≤ K . Per quanto osservato sopra, dovr`a essere necessariamente | V " |= K : in effetti, V " dovr`a necessariamente includere 1 nodo per ogni arco del tipo (xi , x i ) e due nodi per ogni componente cj1 , cj2 , cj3 . Deriviamo una assegnazione f che soddisfa (X , C ) nel modo seguente: per ogni xi ∈ X , f (xi ) = VERO se xi ∈ V " , altrimenti f (xi ) = FALSO . Tale assegnazione soddisfer`a (X , C ) in quanto, per ogni clausola cj , la corrispondente componente cj1 , cj2 , cj3 in G avr`a esattamente un nodo cjs ∈ V − V " : tale nodo necessariamente sar`a collegato ad un nodo associato al termine tjs , appartenente necessariamente a V " . Dato che e` stato posto f (tjs ) = VERO , ne deriva che cj e` soddisfatta. ! Introduciamo ora il seguente problema I NSIEME I NDIPENDENTE. 28

1.4 Problemi NP-completi

Variabile xi

=⇒

xi

xi

Clausola xi ∨ xj ∨ xk

=⇒

xi

xj xk

F IGURA 1.8 Riduzione da 3-S ODDISFACIBILIT A` a C OPERTURA CON N ODI.

I NSIEME I NDIPENDENTE I STANZA : Grafo G = (V , E), K > 0 intero P REDICATO : Esiste un insieme indipendente di taglia ≥ K , cio`e un U ⊆ V tale che | U |≥ K e * ∃(u, v) ∈ E con u ∈ U ∧ v ∈ U ?

Teorema 1.8 Il problema I NSIEME I NDIPENDENTE `e NP-completo. Dimostrazione. Il risultato deriva immediatamente, osservando che, dato un grafo G = (V , E), un sottoinsieme di nodi V " ⊆ V e` un vertex cover se e solo se V − V " e` un insieme indipendente. Infatti, dal fatto che V " e` un vertex cover, deriva che non esiste alcun arco (u, v) ∈ E con u, v ∈ V − V " , da cui consegue che V − V " . Allo stesso modo, se V " e` un insieme indipendente, allora V − V " e` un vertex cover. E` quindi possibile risolvere una istanza %G = (V , E), K & di C OPERTURA CON N ODI semplicemente trasformandola in una istanza %G = (V , E), | V | −K & di I NSIEME I NDIPEN DENTE. ! Mostriamo ora che il problema C RICCA e` NP-completo. C RICCA I STANZA : Grafo G = (V , E), intero K > 0. P REDICATO : Esiste V " ⊆ V con | V " |≥ K e tale che per ogni coppia u, v ∈ V " (u, v) ∈ E? Teorema 1.9 Il problema C RICCA `e NP-completo. 29

Capitolo 1 – Trattabilita` ed intrattabilita`

Dimostrazione. E` sufficiente osservare che, dato un grafo G = (V , E), un sottoinsieme V " ⊆ V di nodi e` un insieme indipendente se e solo se forma un sottografo completo nel grafo complementare Gc = (V , Ec ), tale che (u, v) ∈ Ec se e solo se (u, v) *∈ E. Per risolvere una qualunque istanza %G = (V , E), K & di I NSIEME I NDIPENDENTE e` quindi sufficiente risolvere l’istanza sottografo completo nel grafo complementare Gc = (V , Ec ), tale che (u, v) ∈ Ec se e solo se (u, v) *∈ E. Per risolvere una qualunque istanza %Gc = (V , Ec ), K & di C RICCA . ! Introduciamo ora il seguente problema. C OPERTURA

CON I NSIEMI

I STANZA : Insieme S, collezione C = {s1 , s2 , . . . , sn } di sottoinsiemi di S, intero K > 0. ' P REDICATO : Esiste un sottoinsieme C " di C che copre S, vale a dire tale che si ∈C ! = S, avente cardinalit`a | C " |≤ K ?

Esercizio 1.7 Dimostrare che il problema C OPERTURA CON I NSIEMI e` NP–completo. [Suggerimento: Definire una Karp-riduzione polinomiale da C OPERTURA CON N ODI.]

Infine, definiamo il seguente problema. C ICLO H AMILTONIANO I STANZA : Grafo G = (V , E). P REDICATO : Esiste un ciclo hamiltoniano in G, vale a dire una sequenza di n =| V | archi (vi1 , vi2 ), (vi2 , vi3 ), (vi3 , vi4 ), . . . , (vin , vi1 ) che attraversa ogni nodo una ed una sola volta?

Teorema 1.10 Il problema C ICLO H AMILTONIANO `e NP-completo. Dimostrazione. Il problema e` chiaramente in NP, in quanto, data una sequenza di nodi, la verifica che essi formino un ciclo hamiltoniano pu`o essere effettuata in tempo polinomiale. Per mostrare la NP-hardness di C ICLO H AMILTONIANO utilizziamo una Karp-riduzione polinomiale da C OPERTURA CON N ODI: tale riduzione, data una istanza %G, K & di C OPER TURA CON N ODI , deriva da essa una istanza G " di C ICLO H AMILTONIANO tale che G " ha un circuito hamiltoniano se e solo se esiste un vertex cover di dimensione al pi`u K su G. Il grafo G " e` derivato nel modo descritto di seguito. 30

1.4 Problemi NP-completi

1. Per ogni arco (u, v) in G viene definito un sottografo (gadget) guv composto da 12 nodi e 14 archi (si veda la Figura 1.9). I gadget relativi a tutti gli archi di G saranno collegati tra loro utilizzando, per ogni gadget, soltanto i collegamenti tratteggiati in figura, e quindi archi incidenti sui soli nodi (u, v, 1), (u, v, 6), (v, u, 1),(v, u, 6). Come si pu`o vedere in Figura 1.10, un gadget pu`o essere attraversato da tre soli possibili cammini hamiltoniani, che corrisponderanno ai casi in cui soltanto u, soltanto v o sia u che v sono presenti nel vertex cover.

(u, v, 1)

(u, v, 2)

(u, v, 3)

(u, v, 4)

(u, v, 5)

(u, v, 6)

(v, u, 1)

(v, u, 2)

(v, u, 3)

(v, u, 4)

(v, u, 5)

(v, u, 6)

F IGURA 1.9 Gadget corrispondente ad un arco

2. In G " sono inoltre presenti K nodi cover. 3. Per ogni nodo u in G, i gadget corrispondenti a tutti gli archi incidenti su u sono collegati in sequenza. In particolare, siano (u, vi1 ), (u, vi2 ), . . . , (u, vik ) gli archi incidenti su u, ordinati in modo arbitrario: i relativi gadget sono collegati dagli archi ((u, vi1 , 6)(u, vi2 , 1)), ((u, vi2 , 6)(u, vi3 , 1)), . . . ,((u, vik−1 , 6)(u, vik , 1)). Inoltre, i nodi (u, vi1 , 1) e (u, vik , 6) sono collegati a tutti i K nodi cover Il grafo G " pu`o chiaramente essere costruito in tempo polinomiale a partire da G.

u, v in vertex cover

v in vertex cover

u in vertex cover

F IGURA 1.10 Possibili cammini hamiltoniani in un gadget

Qualunque ciclo hamiltoniano in G " sar`a necessariamente diviso in K tratti, ognuno dei quali inizia e termina in un nodo cover ed e` composto da una sequenza di gadget relativi a tutti 31

Capitolo 1 – Trattabilita` ed intrattabilita`

gli archi incidenti su uno stesso nodo. Quindi, un ciclo hamiltoniano H su G " e` associato ad un insieme di nodi VH di G: dato che ogni gadget e` attraversato dal ciclo, ne consegue che ogni arco in G e` coperto dai nodi in VH , e che quindi H e` un vertex cover di dimensione K . Al contrario, se assumiamo che G abbia un vertex cover di dimensione K , possiamo facilmente costruire, utilizzando per ogni arco l’associazione tra presenza di nodi nel vertex cover e cammino nel gadget relativo (mostrata in Figura 1.10), un ciclo hamiltoniano sull’intero grafo ! G ". Si noti che nel caso del seguente problema C ICLO E ULERIANO , simile al precedente, si pu`o invece mostrare che C ICLO E ULERIANO ∈ P. C ICLO E ULERIANO I STANZA : Grafo G = (V , E). P REDICATO : Esiste un ciclo euleriano in G, vale a dire una sequenza di m =| E | archi (vi1 , vi2 ), (vi2 , vi3 ), (vi3 , vi4 ), . . . , (vim , vi1 ) che include ogni arco una ed una sola volta? Esempio 1.3 Un esempio di ciclo hamiltoniano e di ciclo euleriano e` mostrato in Figura 1.11.

Esercizio 1.8 Dimostrare che il problema C ICLO E ULERIANO e` risolubile in tempo polinomiale.

Osserviamo ora che in generale, dato un problema P, se restringiamo il problema stesso ad un sottoinsieme delle possibili istanze otteniamo un suo sottoproblema P " (come nel caso di 3-S ODDISFACIBILIT A` rispetto a S ODDISFACIBILIT A` ) che certamente non e` pi`u difficile da risolvere rispetto a P: in effetti vale banalmente la relazione P " ≤r P per qualunque riducibilit`a ≤r , in quanto ogni istanza di P " e` istanza di P. E` interessante per`o in tale situazione chiedersi se la restrizione introdotta sull’insieme delle istanze comporta una maggiore facilit`a di risoluzione del problema. Ci chiediamo cio`e se P ≤r P " : se tale relazione e` vera allora, almeno rispetto alla riducibilit`a considerata, P e P " sono equivalenti mentre, altrimenti, P e` effettivamente pi`u difficile di P " . Ci`o risulta particolarmente interessante nel caso in cui P sia NP-completo, in quanto ci chiediamo se il sottoproblema P " considerato e` ancora NP-completo o meno. Ad esempio, nel caso di S ODDISFACIBILIT A` e di 3-S ODDISFACIBILIT A` abbiamo gi`a visto che la restrizione introdotta dal considerare soltanto istanze con clausole di esattamente 3 termini non rende il problema pi`u facile, rispetto alla Karp-riducibilit`a polinomiale, in quanto p 3-S ODDISFACIBILIT A` e` anch’esso NP-completo e quindi si ha che S ODDISFACIBILIT A` ≤m 3S ODDISFACIBILIT A` . 32

1.4 Problemi NP-completi

4 7

8

5

9

3

6 10

2

1

14

15

13 12 11

16

17 Grafo

Hamiltoniano

Euleriano

F IGURA 1.11 Esempi di cicli hamiltoniano ed euleriano.

Esistono per`o delle diverse restrizioni di S ODDISFACIBILIT A` per le quali si ha un effettivo miglioramento della relativa difficolt`a di soluzione. Una di tali restrizioni e` quella relativa a S ODDISFACIBILIT A` DI FORMULE DI H ORN: chiaramente S ODDISFACIBILIT A` DI p ` (e quindi S ODDISFACIBILIT A` DI FORMULE DI FORMULE DI H ORN≤m S ODDISFACIBILIT A p H ORN∈ NP), mentre non si ha S ODDISFACIBILIT A` ≤m S ODDISFACIBILIT A` DI FORMULE DI H ORN, a meno che LOGSPACE = P = NP. Un secondo sottoproblema di S ODDISFACIBILIT A` che e` sostanzialmente pi`u semplice di esso e` 2-S ODDISFACIBILIT A` , vale a dire la restrizione al caso in cui ogni clausola e` composta da al pi`u 2 termini. Anche in questo caso e` possibile mostrare che 2-S ODDISFACIBILIT A` ∈ P mostrando che esiste un algoritmo che risolve tale problema in tempo polinomiale (vedi p Teorema 1.11): ne deriva quindi che non si ha S ODDISFACIBILIT A` ≤m 2-S ODDISFACIBILIT A` , a meno che P = NP. Teorema 1.11 Il problema 2-S ODDISFACIBILIT A` pu`o essere risolto in tempo polinomiale. Dimostrazione. Data una istanza (F, X ) di 2-S ODDISFACIBILIT A` , consideriamo il grafo orientato G(F, X ) definito nel modo seguente: 1. per ogni variabile xi ∈ X esistono due nodi ni , ni , corrispondenti ai due termini xi e x i ; 2. per ogni clausola ti ∨ tj , dove ti e tj sono termini, esistono in G i due archi < t i , tj > e < t j , ti >. 33

Capitolo 1 – Trattabilita` ed intrattabilita`

I due archi rappresentano le due implicazioni logiche t i =⇒ tj e t j =⇒ ti definite dalla necessit`a di soddisfare la clausola. Si osservi che una clausola e` soddisfatta se e solo se per nessuno dei due archi ad essa corrispondenti si ha che il primo nodo ha assegnato il valore VERO mentre il secondo ha assegnato il valore FALSO . Si pu`o osservare facilmente (vedi Esercizio 1.10) che se per una variabile xi ∈ X esiste in G un cammino dal nodo ni al nodo ni (o viceversa), allora la formula F non e` soddisfacibile. Consideriamo ora il caso in cui tale condizione non si verifichi per nessuna variabile in X : e` possibile verificare allora che, per costruzione, non esiste alcun nodo ti da cui e` possibile raggiungere sia un nodo tj che il nodo negato t j . Costruiamo una assegnazione di verit`a che soddisfi F semplicemente scegliendo iterativamente un nodo ti cui non e` stato assegnato alcun valore, assegnando ad esso e a tutti i nodi da esso raggiungibili il valore VERO , ed assegnando ai nodi che corrispondono alle negazioni di tali nodi il valore FALSO . Da quanto detto poc’anzi, ci`o determina una assegnazione consistente con il vincolo che, per ogni i, i nodi ti e t i devono avere assegnati valori diversi. Dato che, ad ogni iterazione, viene determinata l’assegnazione per almeno una coppia di nodi, ne consegue che il procedimento termina in un tempo finito, assegnando un valore VERO o FALSO per ogni nodo, e quindi, per costruzione del grafo, determinando una assegnazione di verit`a che soddisfa F. !

Esercizio 1.9 Dimostrare che, nella dimostrazione del Teorema 1.11, se esiste nel grafo G(F , X ) un cammino da ni a ni (o da ni a ni ), allora la formula F non e` soddisfacibile.

In generale, possiamo considerare la relazione
34