Algoritmi e Strutture Dati--Lecture Noteslibeccio.di.unisa.it/ASDII/2004/Appunti/ParteA2004.pdf4...

Note per Algoritmi e Strutture Dati

Argomenti Avanzati

Anno Accademico 2004-2005

Giuseppe Persiano

Dipartimento di Informatica ed Appl. “Renato M. Capocelli”

Universita di Salerno

Indice

Capitolo 1. NP-completezza 51. La classe P 52. La classe NP 63. La classe NP-complete 74. Un primo linguaggio NP-completo 95. Il linguaggio CNF-SAT 106. Il linguaggio 3SAT 117. Il linguaggio 2SAT 118. Il linguaggio Clique 129. Decisione e ricerca 1310. Esercizi 14Note bibliografiche 15

Capitolo 2. Introduzione agli algoritmi probabilistici 171. Ripasso di probabilita discreta 172. Eventi indipendenti 193. Approssimazione per MaxSat 204. Chernoff bound 235. Verifica probabilistica 256. Esercizi 27

Bibliografia 29

3

4 INDICE

SommarioQuesto documento contiene note per la Parte A del secondo corso di Algoritmi e Strutture Dati

che l’autore ha tenuto presso la Facolta di Scienze dell’Universita di Salerno nell’anno accademico2004/2005.

La versione aggiornata di questo documento si trovahttp://libeccio.dia.unisa.it/ASDII/2004/Appunti/ParteA2004.pdf.

http://libeccio.dia.unisa.it/ASDII/2004/Appunti/ParteA2004.pdf

CAPITOLO 1

NP-completezza

1. La classe P

Iniziamo con le seguenti semplici definizioni.

Definizione 1.1. Un linguaggio sull’alfabeto Σ e un sottoinsieme di Σ∗ (l’insieme delle stringhedi lunghezza finita su Σ).

Tipicamente, l’alfabeto Σ coincide con l’insieme 0, 1. La teoria dell’NP-completezza e le defini-zoni delle classi P e NP sono invarianti rispetto alla scelta dell’alfabeto purche questi contenga almenodue simboli.

Definizione 1.2. Un algoritmo A decide il linguaggio L se

A(x) = 1 se e solo se x ∈ L.

Definizione 1.3. Il linguaggio L appartiene alla classe P (in simboli L ∈ P) se esiste un algoritmoA tale che

(1) A decide L;(2) esiste una costante c ≥ 0 tale che per ogni x ∈ 0, 1∗ A si ferma dopo al piu |x|c passi.

E facile verificare che ciascuno dei seguenti linguaggi appartiene a P.(1) L = x|xha un numero pari di 0;(2) L = x|x e la rappresentazione binaria di una potenza di 2;(3) Il linguaggio L di tutte le quadruple (G, u, v, k) tali che

• G e la rappresentazione di un grafo (ad esempio G e la matrice di adiacenza di un grafo).Per comodita, e con un piccolo abuso di notazione, indicheremo con G sia il grafo che lasua rappresentazione.• u e V sono due vertici di G che si trovano a distanza al piu k.

1.1. Grafi di Eulero. Il seguente problema risale ad Eulero.

Definizione 1.4. Un grafo G = (V,E) si dice euleriano se esiste una permutazione degli archie0, · · · , em−1 di G tale che, denotando con (ui, vi) gli estremi dell’arco ei abbiamo che

vi = ui+1 mod m

per i = 0, · · · ,m− 1.

In altre parole un grafo e euleriano se esiste un ciclo nel grafo G che visita tutti gli archi una eduna sola volta.

Teorema 1.5. Un grafo G e euleriano se e solo se G e connesso e tutti i vertici di G hanno gradopari.

Dimostrazione.

(1) La condizione e necessaria.Ovvia.

5

6 1. NP-COMPLETEZZA

(2) La condizione e sufficiente.Supponiamo che tutti i vertici di G abbiano grado pari. Costruiremo un ciclo di Eulero

usando la seguente ben nota proprieta dei grafi. Se tutti i vertici di un grafo hanno gradopari allora certamente il grafo contiene un ciclo.

Pertanto sia C1 un ciclo di G. C1 puo essere costruito in vari modi; ad esempio, scegliendoun vertice arbitrario u ∈ G di grado positivo e scegliendo ad ogni passo arbitrariamente unodei vicini del vertice corrente fin quando non torniamo in u.

Rimuoviamo da G tutti gli archi C1. Se G non ha piu archi, abbiamo terminato e C1 e ilciclo richiesto.

Altrimenti continuiamo a costruire cicli C2, · · · , Ck fin quando tutti gli archi di G sonostati inclusi in un ciclo.

Osserviamo che, denotando con Gi = (V,Ei) il grafo che si ottiene rimuovendo da G gliarchi dei cicli C1, · · · , Ci−1, abbiamo che tutti i vertici di Gi hanno ancora grado pari e quindisiamo garantiti che Gi contiene un ciclo.

Terminiamo la dimostrazione mostrando come fondere i cicli C1, · · · , Ck ottenuti in ununico ciclo che contiene tutti gli archi di G. Osserviamo, che poiche il grafo G e con-nesso e i cicli C1, · · · , Ck contengono tutti gli archi di G, certamente esisteranno due ci-cli, siano essi senza perdita di generalita C1 e C2, che hanno un vertice in comune. Piuprecisamente sia C1 = 〈a0, · · · , al−1〉 e sia C2 = 〈b0, · · · , br−1〉 e supponiamo che ai e bj

siano lo stesso vertice. Allora possiamo fondere i due cicli in unico ciclo C cosı definitoC = 〈a0, · · · , ai, bj+1 · · · , br−1.b0, · · · , bj−1, bj , ai+1, · · · , al−1〉.

Quindi l’algortimo procede a fondere cicli fino a quando non otteniamo un unico ciclo checomprende tutti gli archi di G.

Grazie al teorema precedente possiamo concludere che il linguaggio che consiste di tutte le stringheche sono la descrizione di un grafo euleriano appartiene alla classe P.

2. La classe NP

In questa sezione definiamo la classe di linguaggi NP. Informalmente un linguaggio L e in NP, se epossibile verificare in tempo polinomiale l’appartenenza di una stringa x al linguaggio L. Formalmenteabbiamo la seguente definizione.

Definizione 1.6. Un linguaggio L appartiene alla classe NP se un algoritmo A(·, ·) polinomialenella lunghezza del primo input tale che

(1) per ogni stringa x ∈ L esiste una stringa y ∈ 0, 1? tale che A(x, y) = 1;(2) per ogni x 6∈ L e per ogni y ∈ 0, 1?, A(x, y) = 0.

In altre parole se L ∈ NP allora per ogni x ∈ L esiste un certificato y di lunghezza polinomialenella lunghezza di x che e “verificato” da A in tempo polinomiale e se x 6∈ L non esiste alcun certificatoy. L’algoritmo A e anche chiamato algoritmo polinomiale di verifica. Nota che, poiche il tempo diesecuzione di A e polinomiale nella lunghezza del primo input, y ha a sua volta lunghezza polinomiale.

Consideriamo ad esempio il seguente linguaggio

Clique= (G, k)|G e un grafo che ha un sottografo completo di taglia k.Per provare che Clique∈ NP dobbiamo esibire un algoritmo polinomiale A che soddisfa la Definizio-ne 1.6.

Consideriamo il seguente algoritmo.

3. LA CLASSE NP-complete 7

A((G, k), (v1, · · · , vl))

01. if l 6= k then02. return 0;03. for i = 1 to k04. for j = i + 1 to k05. if vi = vj then06. return 0;07. for i = 1 to k08. for j = i + 1 to k09. if (vi, vj) non appartiene all’insieme degli archi di G then10. return 0;10. return 1;

L’algoritmo riceve una coppia (G, k) ed un certificato (v1, · · · , vl) per l’appartenenza di (G, k) allinguaggio Clique. L’algoritmo A verifica che il certificato consiste di k vertici (righe 01-02), chetutti i k vertici del certificato sono differenti (righe 03-06) e che i vertici del certificato costituisconoun sottografo completo di G (righe 07-10). Se tutte le verifiche hanno successo l’algoritmo restituisce1; altrimenti l’algoritmo restituisce 0. Osserviamo che se G ha un sottografo completo di taglia kcostituito dai vertici (v1, · · · , vk) allora l’algoritmo A con input (G, k) e (v1, · · · , vk) restituisce 1.Quindi la condizione 1 della Definizione 1.6 e soddisfatta.

Se invece G non ha nessun sottografo completo di taglia k allora per ogni sequenza di vertici(v1, · · · , vl) almeno una delle seguenti tre condizioni deve essere soddisfatta:

(1) l 6= k; in questo caso A restituisce 0 alla riga 02;(2) qualche vertice di G appare due volte nella lista; in questo caso A restituisce 0 alla riga 06;(3) i k vertici sono distinti ma per qualche coppia (i, j) l’arco (vi, vj) non e un arco di G; in

questo caso A restituisce 0 alla riga 10.Quindi se (G, k) 6∈Clique, non esiste nessun certificato per cui A restituisce in output il valore 1. Lacondizione 2 della Definizione 1.6 e pertanto soddisfatta.

Nel prossimo teorema proviamo che L ∈ P allora L ∈ NP.

Teorema 1.7. P ⊆ NP.

Dimostrazione. Sia L ∈ P. Allora esiste un algoritmo deterministico A che, su input x,restituisce 1 se e solo se x ∈ L. Si consideri il seguente algoritmo B.

B(x, y)01. return (A(x));

Osserviamo che se x ∈ L allora B(x, 0) = A(x) = 1 e quindi 0 e un certificato. Se invece x 6∈ L alloraper ogni possibile certificato y abbiamo che B(x, y) = A(x) = 0.

Non e noto se P 6= NP. Sebbene la maggior parte degli studiosi creda che P 6= NP non abbiamoancora una prova. La Teoria dell’NP-completezza (che verra discussa nella prossima sezione) identificai linguaggi piu difficili di NP. Se almeno uno di essi ha un algoritmo polinomiale che lo decide alloraP = NP.

3. La classe NP-complete

Abbiamo le seguenti definizioni.

8 1. NP-COMPLETEZZA

Definizione 1.8 (Riduzione). Sia L1 e L2 due linguaggi. Diciamo che L1 si riduce a L2 (insimboli L1 ≤p L2) se esiste un algoritmo polinomiale R tale che

R(x) ∈ L2 se e solo se x ∈ L1.

Definizione 1.9 (NP-completo). Un linguaggio L e NP-completo se(1) L ∈ NP;(2) per ogni linguaggio L′ ∈ NP abbiamo che L′ ≤p L.

Denotiamo con NP-complete la classe dei linguaggi NP-completi.

Si noti la similarita della definizione di linguaggio NP-completo con la definizione di massimo diun insieme I definito come quell’elemento x ∈ I tale che, per ogni y ∈ I, vale y ≤ x. La nozione dilinguaggio NP-completo esprime formalmente il concetto di linguaggio piu difficile di NP. Il seguenteteorema rafforza la nostra intuizione dicendoci che se un linguaggio NP-completo appartiene a P alloratutti i linguaggi in NP possono essere decisi in tempo polinomiale.

Teorema 1.10. Sia L un linguaggio NP-completo. Se L ∈ P allora P = NP.

Dimostrazione. Sia L′ un linguaggio in NP. Mostriamo un algoritmo polinomiale A′ che decideL′.

Poiche L ∈ P allora esiste un algoritmo polinomiale A che decide L. Inoltre, siccome L e NP-completo e L′ ∈ NP allora esiste un algoritmo polinomiale R che riduce L′ a L. Consideriamo ora ilseguente algoritmo A′

A′(x)01. y ← R(x);02. return (A(y));

Chiaramente l’algoritmo A′ e polinomiale. Supponiamo che x ∈ L′. Allora, per le proprieta dellariduzione R, y ∈ L e quindi A(y) = 1. Supponiamo ora che x 6∈ L′. Allora y 6∈ L e quindi A(y) = 0.Possiamo quindi concludere che A′ e polinomiale e decide L′ e quindi L′ ∈ P.

Un altro modo di leggere il teorema precedente e che se un linguaggio L e NP-completo allora Le da considerarsi “difficile”. Infatti se P 6= NP, allora non esiste alcuna algoritmo polinomiale chedecide L.

Il prossimo teorema e particolarmente utile per provare che un linguaggio e NP-completo. Infatti,seguendo la definizione, per provare che un linguaggio L e NP-completo dobbiamo provare che ognilinguaggio in NPsi riduce ad esso il che puo essere particolarmente difficile. Invece grazie al prossimoteorema bastera mostrare che un linguaggio NP-completo si riduce a L. Iniziamo con il provare ilseguente lemma.

Lemma 1.11 (Transitivita della relazione ≤p.). Sia L,L1 e L2 tre linguaggi tali che L2 ≤p L1 eL1 ≤p L. Allora L2 ≤p L.

Dimostrazione. Per ipotesi esistono due riduzioni polinomiali R1 e R2 tali che• x ∈ L2 se e solo se R2(x) ∈ L1;• x ∈ L1 se e solo se R1(x) ∈ L.

Consideriamo il seguente algoritmo.

R(x)01. y1 ← R2(x);02. y ← R1(y1);03. return (y);

4. UN PRIMO LINGUAGGIO NP-COMPLETO 9

Per le proprieta degli algoritmi R1 e R2 abbiamo che se x ∈ L2 allora y1 ∈ L1 e quindi y ∈ L; inoltrese x 6∈ L2 allora y1 6∈ L1 e quindi y 6∈ L. Pertanto per l’algoritmo R vale la proprieta x ∈ L2 se e solose R(x) ∈ L. Inoltre l’algoritmo R e polinomiale e quindi abbiamo che L2 ≤p L.

Abbiamo quindi il seguente teorema.

Teorema 1.12. Sia L un linguaggio NPe sia L1 un linguaggio NP-completo tale che L1 ≤p L.Allora L e NP-completo.

Dimostrazione. Sia L2 un qualsiasi linguaggio NP. Allora L2 ≤p L1. Applicando il Lemma 1.11abbiamo che L2 ≤p L. Inoltre per ipotesi abbiamo che L ∈ NP e quindi L e NP-completo.

Grazie al Teorema 1.12, per provare che un linguaggio e NP-completo basta provare che un altrolinguaggio (che gia sappiamo essere NP-completo) si riduce ad esso. Abbiamo pero bisogno di unprimo linguaggio NP-completo da cui partire.

4. Un primo linguaggio NP-completo

In questa sezione presentiamo la prima prova di NP-completezza per il linguaggio S. Questorisultato sara usato come “base” per le ulteriori dimostrazioni di completezza che useranno la proprietadi transitivita della riducibilita (Teorema 1.12).

Il linguaggio S (S sta per super in quanto S e un linguaggio super :-) ) consiste delle triple (A, x, 1k)dove

(1) A e la descrizione in un qualche linguaggio (ad esempio C) di un algoritmo;(2) x e una stringa in 0, 1?;(3) 1k e la rappresentazione unaria dell’intero k.

tali che esiste y ∈ 0, 1? per cui A su input (x, y) si ferma in ≤ k passi e da in output 1.

Teorema 1.13. S e NP-completo.

Dimostrazione. Prima di tutto proviamo che S ∈ NP. Infatti consideriamo il seguente algoritmopolinomiale di verifica come richiesto dalla Def. 1.6.

B((A, x, 1k), y)

01. simula A su input (x, y);02. se A si ferma in ≤ k passi03. return A(x, y);04. return 0;

Il numero di passi e eseguito da B su input (A, x, 1k) e ≤ k+costante e l’input di B ha lunghezzaalmeno k. Pertanto B e polinomiale.

Se (A, x, 1k) ∈ S allora per definizione di S esiste y ∈ 0, 1? per cui A su input (x, y) si ferma in≤ k passi e da in output 1. Quindi B su input (A, x, 1k) e y da in output 1.

Se invece (A, x, 1k) 6∈ S allora per definizione di S non esiste y ∈ 0, 1? per cui A su input (x, y)si ferma in ≤ k passi e da in output 1. Quindi B su input (A, x, 1k) ed un qualsiasi y da in output0.

A partire dal linguaggio S possiamo provare la completezza di altri linguaggi. Proviamo ora che illinguaggio CircuitSat e NP-completo mostrando che S si riduce ad esso. Il linguaggio CircuitSatconsiste di tutti i circuiti booleani C per cui esiste un input y tale che C(y) = 0. Ovviamente

10 1. NP-COMPLETEZZA

CircuitSat ∈ NP. Mostriamo ora informalmente che S ≤p CircuitSat. La riduzione, su input(A, x, 1k) restituisce un circuito C che prende come input y e “simula” il comportamento di k passidi un algoritmo A su input (x, y). Ovviamente, per ogni (A, x, 1k) ∈ L esiste y tale che C(y) = 1 eviceversa. Abbiamo quindi il seguente teorema.

Teorema 1.14. [Cook-Levin] Il linguaggio CircuitSat e NP-completo.

5. Il linguaggio CNF-SAT

Una formula booleana Φ sulle variabili (x1, · · · , xn) e una formula che contiene i connettivi logici∧ (AND), ∨ (OR) e ¬ (NOT) e le variabili x1, · · · , xn. Indichiamo invece con il termine di letterale levariabili in forma negata e forma non negata. Ad esempio Φ = (((x1∧x2)∨(x1∧¬x3))∧(x1∨x4)) e unaformula booleana sulle variabili (x1, · · · , x4). Un assegnamento di verita t assegna ad ogni variabiledella formula Φ un valore booleano ed induce naturalmente un valore booleano t(Φ) della formula Φ.Ad esempio, l’assegnamento t tale che t(x1) = 0, t(x2) = 1, t(x3) = 1 e t(x4) = 0 rende la formulaformula Φ falsa (cioe t(Φ) = 0). Una formula Φ si dice soddisfacibile se esiste un assegnamento diverita t tale che t(Φ) = 1; in questo caso diciamo che t rende Φ vera. Definiamo il linguaggio SATcome il linguaggio che consiste delle formule booleane Φ che sono soddifacibili. Indichiamo invece conCNF-SAT il linguaggio delle formule booleane in forma congiuntiva normale (AND di OR) che sonosoddifacibili. Ad esempio la formula Φ = (x1∨x2∨x3)∧(¬x1∨x2∨x4)∧(x2∨¬x4)∧(x2∨x3∨¬x4∨x5)e in formula congiuntiva normale e consiste di 4 clausole. La prima e la seconda clausola contengono3 letterali, la terza clausola contiene 2 letterali mentre la quarta clausola contiene 4 letterali.

Teorema 1.15. [Cook-Levin] Il linguaggio CNF-SAT e NP-completo.

Dimostrazione. Riduciamo CircuitSata CNF-SAT nel modo seguente. Sia C il circuito ininput e costruiamo la formula Φ in forma CNF nel modo seguente. Φ ha, per ogni filo del circuito,una variabile y e le seguenti clausole.

(1) Se y e un filo di input che corrisponde all’input xi Φ contiene le clausole equivalenti a (y ⇔ xi).Usando semplice algebra booleana otteniamo che le clausole da aggiungere sono

(y ∨ xi) ∧ (y ∨ xi).

(2) Se y e un filo output di una porta NOT che prende come input il filo yk allora aggiungiamole clausole

(y ∨ yk) ∧ (y ∨ yk)

che sono equivalenti a (y ⇔ yk).(3) Se y e il filo di output di una porta AND che prende come input i file yk e yj aggiungiamo a

Φ le clausole

(y ∨ yk ∨ yj) ∧ (y ∨ yk ∨ yj) ∧ (y ∨ yk ∨ yj) ∧ (y ∨ yk ∨ yj)

che sono equivalenti a (y ⇔ (yk ∧ yj)).(4) Se y e il filo di output di una porta OR che prende come input i file yk e yj aggiungiamo a Φ

le clausole

(y ∨ yk ∨ yj) ∧ (y ∨ yk ∨ yj) ∧ (y ∨ yk ∨ yj) ∧ (y ∨ yk ∨ yj)

che sono equivalenti a (y ⇔ (yk ∨ yj)).(5) Se y e il file dell’output allora Φ contiene la clausola y.

Vediamo facilmente che la riduzione puo essere eseguita in tempo polinomiale e che se esiste un inputy per cui C(y) = 1 allora esiste un assegnamento di verita che soddisfa Φ.

7. IL LINGUAGGIO 2SAT 11

Come conseguenza del teorema precedente abbiamo che, se P 6= NP, non esiste alcun algoritmoche in tempo polinomiale possa decidere se una qualsiasi formula booleana Φ in forma congiuntivanormale data in input e soddisfacibile.

6. Il linguaggio 3SAT

In questa sezione proviamo che il linguaggio 3SAT consistente di tutte le formule in forma con-giuntiva normale ove ogni clausola contiene esattamente 3 letterali e NP-completo.

Teorema 1.16. 3SAT∈ NP-complete.

Dimostrazione. Riduciamo CNF-SAT a 3SAT e quindi, grazie al Teorema 1.12, otteniamo ilteorema.

Sia Φ una formula in forma CNF. Costruiamo in tempo polinomiale una formula Φ′ in forma 3CNF(cioe in forma CNF ove ogni clausola contiene esattamente 3 letterali) tale che Φ′ e soddisfacibile se esolo se Φ e soddisfacibile. La costruzione considera ogni clausola C di Φ separatamente e per ognunadi esse costruisce una sequenza S di clausole. La sequenza S di clausole ha la proprieta che unassegnamento di verita soddisfa C se e solo soddisfa S. La formula Φ′ e ottenuta legando insiemecon l’operatore ∧ tutte le clausole ottenute. Pertanto abbiamo che Φ′ e soddisfacibile se e solo se Φ esoddisfacibile. La costruzione distingue i seguenti casi.

(1) La clausola C contiene un solo letterale a.In questo caso l’insieme S consiste delle seguenti clausole (a ∨ y1 ∨ y2) (a ∨ ¬y1 ∨ y2)

(a ∨ y1 ∨ ¬y2) (a ∨ y¬1 ∨ ¬y2).(2) La clausola C contiene due letterali (a1 ∨ a2).

In questo caso l’insieme S consiste delle seguenti clausole (a1 ∨ a2 ∨ y1) (a1 ∨ a2 ∨ ¬y1)(3) La clausola C contiene tre letterali (a1 ∨ a2 ∨ a3). In questo caso l’insieme S consiste della

sola clausola C.(4) La clausola C contiene k > 3 letterali (a1 ∨ a2 ∨ a3 ∨ · · · ∨ ak).

In questo caso l’insieme S consiste delle clausole(a1 ∨ a2 ∨ y1), (¬y1 ∨ a3 ∨ y2), . . . , (¬yk−3 ∨ ak−1 ∨ ak).

Consideriamo per esempio la formula

Φ = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x4) ∧ (x2 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4 ∨ x5).

La formula Φ′ ottenuta e la seguente

Φ′ = (x1∨x2∨x3)∧(¬x1∨x2∨x4)∧(x2∨¬x4∨y1)∧(x2∨¬x4∨¬y1)∧(x2∨x3∨y2)∧(¬y2∨¬x4∨x5).

7. Il linguaggio 2SAT

In questa sezione proviamo che il linguaggio 2SAT consistente di tutte le formule in forma con-giuntiva normale ove ogni clausola contiene al piu 2 letterali puo essere deciso in tempo polinomiale.

Si consideri una formula Φ in forma 2-congiuntiva normale sulle variabili (x1, · · · , xn). Assumiamosenza perdita di generalita che le clausole di Φ contengano esattamente due letterali. Clausole con unsolo letterale sono eliminate nel modo seguente. Se Φ contiene sia la clausola (xi) e la clausola (¬xi)allora Φ non e soddisfacibile e non necessario procedere oltre. Se Φ contiene la clausola xi allora ogniassegnamento di verita che soddisfa Φ assegna valore vero a xi. Quindi, tutte le clausole che contengonoxi possono essere eliminate. Inoltre ogni occorrenza di ¬xi e eliminata. Se Φ contiene la clausola ¬xi siprocede in maniera analoga. Il processo di eliminazione termina quando 1) tutte le clausole sono stateeliminate (e quindi la formula e soddisfacibile); 2) otteniamo due clausole ciascuna con un letterale


che contengono una variabile e la sua negazione (e quindi la formula non e soddisfacibile); 3) abbiamosolo clausole con esattamente due letterali e quindi procediamo con la costruzione del grafo diretto G.

Il grafo diretto G ha un vertice per ogni letterale e G contiene l’arco diretto (a, b) se e solo se Φcontiene la clausola (¬a ∨ b). L’arco (a, b) codifica il fatto che se a e vero (e quindi ¬a e falso) laclausola (¬a ∨ b) puo essere soddisfatta solo se b e vero. Quindi l’arco (a, b) codifica l’implicazionea→ b che e logicamente equivalente alla clausola (¬a∨b). Poiche l’implicazione e transitiva, l’esistenzadi archi (a, b) e (b, c) in G implica che se a e vera allora anche c deve essere vera. Possiamo quindidire che se esiste un cammino dal letterale x al letterale ¬x in G (quindi se x e vero allora ¬x e vero)allora nessun assegnamento che assegna a x il valore vero puo soddisfare la formula Φ da cui derivache se esistono cammini da x a ¬x e da ¬x a x allora la formula e non soddisfacibile.

Supponiamo invece che nessuna componente fortemente connessa di G contiene un letterale ed ilsuo negato. Allora e possibile calcolare un assegnamento di verita che soddisfa Φ nel modo seguente.

Diciamo che una variabile xi e problematica per il letterale xj se l’insieme Succ(xj) di verticiraggiungibili da xj contiene sia xi e ¬xi. Osserviamo che una variabile puo essere problematica perse stessa. Diciamo che un letterale xj e sicuro se non ha variabili problematiche. Se abbiamo unletterale con m > 0 variabili problematiche, possiamo trovare un letterale con m′ < m variabiliproblematiche. Iterando il procedimento otteniamo un letterale sicuro. Sia xj un letterale con mvariabili problematiche e sia xi una di esse. Per ipotesi abbiamo che xi ∈ Succ(¬xi) se e solo se¬xi 6∈ Succ(xi). Supponiamo senza perdita di generalita che xi ∈ Succ(¬xi). Allora xi ha meno dim variabili problematiche. Infatti abbiamo che Succ(xi) ⊆ Succ(xj) e xi e problematica per xj manon per se stessa (ricorda che ¬xi 6∈ Succ(xi)).

Una volta che abbiamo selezionato un vertice sicuro xj possiamo assegnare il valore vero ad essoe a tutti i letterali di Succ(xj). Rimuoviamo tutte le clausole soddisfatte dall’assegnamento (pos-sibilmente parziale) ottenuto da Φ ottenendo una nuova formula Φ′ e ripetiamo il procedimento seΦ′ 6= ∅.

8. Il linguaggio Clique

In questa sezione mostriamo che il linguaggio Clique e NP-completo mostrando una riduzione da3SAT.

Teorema 1.17. Clique∈ NP-complete.

Dimostrazione. Sia Φ una formula in forma CNF ove ogni clausola contiene esattamente 3letterali. Sia inoltre k il numero di clausole di Φ. La riduzione restituisce la coppia (G, k) ove il grafoG e costruito nel modo seguente. Il grafo G ha un vertice per ogni occorrenza di un letterale: Se illetterale xi appartiene alla j-esima clausola di Φ, il grafo G conterra il vertice v(i, j); diremo in questocaso che il vertice v(i, j) appartiene alla j-esima clausola. Se il letterale ¬xi appartiene alla j-esimaclausola di φ allora il grafo G conterra il vertice n(i, j); diremo in questo caso che il vertice n(i, j)appartiene alla j-esima clausola di φ. Ogni vertice di G ha un arco verso ogni altro vertice di G conle seguenti eccezioni:

(1) non ci sono archi tra vertici della stessa clausola;(2) non ci sono archi tra vertici corrispondenti ad un letterale ed al suo negato, anche se appar-

tengono a clausole differenti.Dimostriamo che Φ ∈ 3SAT se e solo se (G, k) ∈ Clique.(1) Supponiamo che Φ ∈ 3SAT.

Allora esiste un assegnamento di verita t tale che per ogni clausola esiste almeno unletterale vero. Consideriamo quindi k vertici (uno per clausola) di G corrispondenti a letteralidi Φ veri per l’assegnamento t e mostriamo che constituiscono una clique in G. Infatti, questik vertici appartengono a clausole differenti e non abbiamo tra questi vertici v(i, j) e n(i, j′)

9. DECISIONE E RICERCA 13

cossipondenti ad una variabile xi ed al suo negato ¬xi (altrimenti t non sarebbe un buonassegnamento di verita). Pertanto i k vertici costituiscono un sottografo completo di taglia ke quindi (G, k) ∈ Clique.

(2) Supponiamo che (G, k) ∈ Clique.Allora esiste un sottografo completo C di k vertici in G. Per costruzione di G abbiamo

che(a) ogni vertice di C appartiene ad una differente clausola di Φ ed ogni clausola di Φ contiene

un vertice di C;(b) se v(i, j) appartiene a C allora certamente n(i, j′) non appartiene a C.Consideriamo quindi l’assegnamento di verita t che pone a vero tutti letterali corrispon-denti a vertici di C. L’assegnamento t e certamente legale per la proprieta (2b) e, per laproprieta (2a), soddisfa tutte le clausole di Φ. Quindi Φ ∈ 3SAT.

9. Decisione e ricerca

Nella nostra discussione sull’apparente difficolta computazionale di alcuni problemi ci siamo con-centrati sul problema di decisione: decidere se una tale istanza gode o no di una certa proprieta. Adesempio, il problema decisionale associato al linguaggio CNF-SAT consiste nel decidere se una dataformula Φ ammette un assegnamento di verita che la soddisfa. Altrettanto interessante e il problemadi ricerca associato a CNF-SAT: data una formula Φ soddisfacibile trovare un assegnamento di veritache la soddisfa. Ovviamente, se abbiamo un algoritmo polinomiale che risolve il problema di ricercaallora anche il problema decisionale puo essere risolto in tempo polinomiale. Proviamo ora che seabbiamo un oracle O che decide appartenenza a CNF-SAT allora possiamo costruire un algoritmo Ache, ricevuto in input una formula in CNF Φ, da in output un assegnamento di verita che soddisfa Φse un tale assegnamento esiste. Il tempo di esecuzione di A e polinomiale e A interroga O un numeropolinomiale di volte. Cio implica che se il problema decisionale associato a CNF-SAT ha un algoritmopolinomiale anche il problema di ricerca puo essere risolto in tempo polinomiale.

La seguente notazione risulta utile nella prova di questo risultato. Se Φ e una formula in CNF sullevariabili x1, . . . , xn allora la formula Φ(xi = bi), per bi ∈ 0, 1, si ottiene sostituendo le occorrenzedi xi con bi e le occorrenze di ¬xi con 1− bi. Ad esempio se

Φ = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x4) ∧ (x2 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4 ∨ x5).

La formula Φ(x1 = 0) e la seguente

Φ(x1 = 0) = (x2 ∨ x3) ∧ (1 ∨ x2 ∨ x4) ∧ (x2 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4 ∨ x5)

che e equivalente a

Φ(x1 = 0) = (x2 ∨ x3) ∧ (x2 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4 ∨ x5).

Osserviamo che Φ(xi = bi) e soddisfacibile se e solo se esiste un assegnamento di verita che soddisfa Φe che pone xi = bi. Ragioniamo quindi nel modo seguente. Sia Φ soddisfacibile e sia t un assegnamentodi verita che la soddisfa. Due casi sono possibili:

(1) t(x1) = 0; in questo caso abbiamo per l’osservazione precedente che Φ(x1 = 0) e soddisfacibile;(2) t(x1) = 1; in questo caso abbiamo che Φ(x1 = 1) e soddisfacibile.

L’oracoloO puo essere usato per decidere quale dei due casi vale. Abbiamo quindi il seguente algoritmo.

A(Φ)01. poni Ψ← Φ;02. for i = 1 to n;


03. if O(Ψ(xi = 0)) then04. t(xi) = 0;05. Ψ← Ψ(xi = 0);06. else07. t(xi) = 1;08. Ψ← Ψ(xi = 1);09. return t;

9.1. Approccio generale. Il risultato ottenuto per il caso speciale di CNF-SAT puo essereottenuto anche per altri specifici linguaggi in NP (vedi ad esempio l’Esercizio 7 in cui si chiede diottenere l’equivalenza per il problema della Clique) e puo essere generalizzato a tutti i linguaggiNP-completi.

Sia L un linguaggio in NP, A il suo algoritmo di verifica e c una costante tale che esiste uncertificato per x ∈ L che ha lunghezza esattamente1 |x|c. Il problema di ricerca associato ad L consistenel trovare per x ∈ L un certificato y tale che A(x, y) = 1.

Supponiamo che esista un oracolo O per decidere il linguaggio NP-completo L. Allora esiste unalgoritmo polinomiale che usa O come oracolo, effettua un numero polinomiale di chiamate ad O erisolve il problema di ricerca associato ad L. La prova di questo asserto e lasciata come esercizio.

10. Esercizi

Esercizio 1. Se L e un linguaggio, definiamo L (il complemento di L) come la differenza sim-metrica

L = Σ∗ \ L.

Provare che se L ∈ P allora L ∈ P .

Esercizio 2. Denotiamo con co-NP la classe dei linguaggi L tali che L ∈ NP. Provare che seNP 6= co-NP allora P 6= NP.

Esercizio 3. Sia L1, L2 ∈ NP. Provare che L1 ∪ L2 e L1 ∩ L2 sono entrambi in NP.

Esercizio 4. Sia L un linguaggio. Definiamo il linguaggio L? come il linguaggio di tutte le stringhew tali che esistono w1, · · · , wk per cui

(1) w = w1 · · · wk (“” denota la concatenazione di stringhe);(2) w1, · · · , wk ∈ L;

Provare che se L ∈ NP allora L? ∈ NP.

Esercizio 5. Usando la notazione dell’esercizio precedente, provare che se L ∈ P allora L? ∈ P .

Esercizio 6. Si consideri il linguaggio Hamilton dei grafi hamiltoniani. Un grafo e detto ha-miltoniano se esiste un cammino che visita tutti i vertici una sola volta. Provare che Hamilton∈NP.

Esercizio 7. Provare l’equivalenza tra il problema decisionale e il problema di ricerca per illinguaggio Clique.

Esercizio 8. Supponiamo che esista un oracolo O per decidere il linguaggio NP-completo L.Provare che esiste un algoritmo polinomiale che usa O come oracolo, effettua un numero polinomialedi chiamate ad O e risolve il problema di ricerca associato ad L.

1La definizione di NP richiede che lunghezza di un certificato per x sia al piu |x|c. E facile comunque convincersiche imporre al certificato di avere lunghezza esattamente |x|c non comporta nessuna perdita di generalita.

NOTE BIBLIOGRAFICHE 15

Esercizio 9. Abbiamo un trasmettitore che vuole inviare un messaggio ad un insieme D =d1, · · · , dm di m destinazioni. Il trasmettitore e collegato ad n coppie di ripetitori (ai, bi), i = 1, · · · , ned ogni ripetitore ai (rispettivamente bi) e collegato ad un sottoinsieme Ai (rispettivamente Bi) di de-stinazioni. Per evitare interferenze per ogni coppia di ripetitori (ai, bi) possiamo avere esattamente unsolo ripetitore attivo. Diciamo che e possibile trasmettere il messaggio se esiste un modo di attivare iripetitori in modo tale che per ogni coppia solo un ripetitore e attivo ed ogni destinazione e adiacentead almeno un ripetitore attivo.

Provare che decidere se una trasmisisone e possibile e NP-completo.

Esercizio 10. Provare che il problema di determinare se una formula Φ in forma congiuntivanormale con esattamente 3 letterali per clausola ammette un assegnamento di verita tale che per ogniclausola esistono almeno due letterali veri e decidibile in tempo polinomiale.

Note bibliografiche

La teoria dell’NP-completezza e stata introdotta da S. Cook in [2] che ha dato la prima prova diNP-completezza (per 3-SAT) e da L. Levin in [10]. La prova dell’NP-completezza di Clique e dei Grafidi Hamilton e stata data da Karp [9]. Il libro di Garey e Johnson [5] e un’ottima guida alla teoriadell’NP-completezza.

Versione: 1.22 del 4 novembre 2004.

CAPITOLO 2

Introduzione agli algoritmi probabilistici

1. Ripasso di probabilita discreta

Nello studio della probabilita consideriamo tipicamente un esperimento cui e naturalmente asso-ciato lo spazio S dei possibili risultati dell’esperimento. Ad ogni possibile risultato r e associata laprobabilita P (r) del risultato r. Ad esempio, l’esperimento puo essere il lancio di un dado a 6 facciecui e associato lo spazio S = 1, 2, 3, 4, 5, 6 dei possibili risultati ciascuno con probabilita 1/6.

Un evento D ⊆ S e un sottoinsieme dello spazio dei risultati. Ad esempio, l’evento “il risultatodel lancio e maggiore di 4” corrisponde all’insieme 5, 6.

La probabilita di un evento puo essere calcolata a partire dalla probabilita dei singoli risultatiusando la seguente relazione e ponendo P (∅) = 0 e P (S) = 1.

Teorema 2.1. Per tutti gli eventi A e B vale che

P (A ∪B) = P (A) + P (B)− P (A ∩B).

Ad esempio sia A l’evento che il lancio del dado dia come risultato un numero pari e B l’evento che ilrisultato sia un numero maggiore di 3. Allora la formula ci dice che P (A∪B) = P (A)+P (B)−P (A∩B).Siccome P (A) = P (2, 4, 6) = 1/2 e P (B) = P (4, 5, 6) = 1/2 e P (A ∩ B) = P (4, 6) = 1/3abbiamo che

P (A ∪B) = 1/2 + 1/2− 1/3 = 2/3.

Una variabile casuale X e una funzione X : S → R. Ad esempio, possiamo definire la variabilecasuale X nel modo seguente: X = 1 se il risultato del dado e pari. In seguito, per una variabilecasuale X ed un valore x, considereremo l’evento “X = x” come l’evento corrispondente all’insieme dirisultati r tali che X(r) = x.

La media E[X] di una variabile casuale X e definita come

E[X] =∑

x

x · P [X = x].

Esempio 2.2. Consideriamo l’esperimento consistente nel lancio di un dado e consideriamo lavariabile casuale definita come X = r mod 3. Abbiamo quindi che P (X = 0) = P (3, 6) = 1/3,P (X = 1) = P (1, 4) = 1/3 e P (X = 2) = P (2, 5) = 1/3. La media della variabile casuale X e

E[X] = 0 · P (X = 0) + 1 · P (X = 1) + 2 · P (X = 2)0 · 1/3 + 1 · 1/3 + 2 · 1/3 = 1.

La media gode di due importanti proprieta. La prima proprieta semplifica notevolmente il calcolodelle media di variabili causali con spazi dei risultati di grosse dimensioni.

Teorema 2.3. Siano X1 e X2 due variabili casuali. Allora la media della somma di X1 e X2 euguale alla somma delle medie di X1 e X2. In simboli,

E[X1 + X2] = E[X1] + E[X2].

17

18 2. INTRODUZIONE AGLI ALGORITMI PROBABILISTICI

1.1. Balls and Bins. Applichiamo il teorema precedente al seguente esempio. Si consideri l’e-sperimento del lancio di m palline (balls) in n urne (bins) e vogliamo calcolare il numero medio diurne vuote. Cioe, definita la variabile causale X che associa ad ogni risultato il numero di urne vuote,vogliamo calcolare E[X]. Lo spazio dei risultati contiene nm punti e quindi, anche per valori piccolidi n e m, l’enumerazione di tutti i possibili risultati e praticamente impossibile. Definiamo quindi leseguenti n variabili casuali.

Xi =

1, se l’i-esima urna vuota;0, altrimenti.

E facile vedere che X =∑n

i=1 Xi. Siccome

E[Xi] = 0 · P (X = 0) + 1 · P (X = 1)

= P (X = 1) =(n− 1)m

nm=

(1− 1

n

)m

abbiamo che

E[X] = n

(1− 1

n

)m

.

Alcuni casi speciali. Quando m = n abbiamo che

E[X] = n

(1− 1

n

)n

∼ n

e

per n→∞.Se invece m = n lnn, abbiamo che

E[X] = n

(1− 1

n

)n ln n

∼ ne−n ln n = 1

e quindi in media restera vuota una sola urna.

1.2. Permutazioni casuali. In questa sezione studiamo le proprieta di una permutazione ca-suale. Iniziamo col calcolare il numero atteso di punti fissi di una permutazione casuale π su n interi1, 2, · · · , n. Un punto fisso e un intero i tale che π(i) = i. Definiamo la variabile casuale Xi come

Xi =

1, se π(i) = i;0, altrimenti

per cui abbiamo che la variabile casuale X =∑n

i=1 Xi conta il numero di punti fissi. Ora osserviamoche E[Xi] = P (Xi = i) = P (π(i) = i) = 1/n e pertanto il numero medio, E[X], di punti fissi di unapermutazione casuale e 1 (indipendentemente dal valore di n!!!).

Un punto fisso e un ciclo di lunghezza 1. In generale una permutazione puo avere piu cicli dilunghezze diverse. Calcoliamo la media della variabile casuale Y che conta il numero di cicli di unapermutazione. Definiamo, per 1 ≤ i ≤ n, la variabile casuale Yi come l’inverso della lunghezza del ciclocui appartiene l’intero i. Abbiamo che Y =

∑ni=1 Yi. Calcoliamo quindi E[Yi e, per fare cio, otteniamo

un’espressione per pk,i

=def P (Yi = 1/k). In altre parole pk,i e la probabilita che i appartenga ad un

ciclo di lunghezza k. Questa probabilita puo essere scritta come la probabilita che esistano i1, · · · , ik−1

(numero di scelte: (n− 1) · (n− 2) · · · · · (n− k + 1)) e permutazione π tale che(1) π(i) = i1;(2) π(ij) = π(ij+1), per j = 2, · · · , k − 2;(3) π(ik−1) = i;

2. EVENTI INDIPENDENTI 19

(numero di scelte (n− k)!) e

(n− 1) · (n− 2) · · · · · (n− k + 1) · (n− k)!1n!

=1n

.

Quindi abbiamo che

E[Yi] =n∑

k=1

1kP (Yi =

1l)

=1n

n∑k=1

1k

∼ 1n

(lnn + γ)

dove γ = 0.5772.... e la costante di Eulero. Pertanto possiamo dire che, quando n cresce, il numero dicicli di una permutazione casuale tende a lnn + γ.

1.3. Grafi casuali. In questa sezione ci chiediamo quanti archi sono necessari per rendere ungrafo casuale connesso.

Consideriamo il seguente esperimento probabilistico. Partiamo dal grafo G con n vertici e nessunarco (cioe E = ∅). Ad ogni passo scegliamo a caso un arco (i, j) 6∈ E e lo aggiungiamo ad E finche ilgrafo G e connesso. Ci chiediamo quanti archi in media devono essere aggiunti.

Sia Xk il numeor di archi che dobbiamo aggiungere al grafo per passare da k a k − 1 componenticonnesse. Allora X =

∑nk=2 Xk conta il numero di archi da aggiungere. Notiamo che Xn = 1 e

Xn−1 = 1 con probabilita 1. In generale ottenere un’espressione per Xk e abbastanza difficile. Ilprossimo lemma ci fornisce un limite superiore a E[Xk].

Lemma 2.4. E[Xk] ≤ n−1k−1 .

Dimostrazione. Supponiamo che G abbia esattamente k componenti connesse. Per un vertice vdi G abbiamo che:

(1) esistono al piu n− 1 archi che sono adiacenti a v e che non appartengono ad E;(2) esistono almeno k−1 archi che connettono v ad una componente connessa differente da quella

cui appartiene v.Pertanto la probabilita che, scegliendo un arco non in E a caso, il numero di componenti connesse siriduca e almeno k−1

n−1 . Quindi il numero medio di tentativi fino a che una tale arco venga scelto e alpiu n−1

k−1 .

Quindi abbiamo che

E[X] =n∑

k=2

E[Xk] ≤ (n− 1)(

1 +12

+13

+ · · ·+ 1n− 1

)= (n− 1)(ln(n− 1) + γ).

2. Eventi indipendenti

Due eventi E1 e E2 sono indipendenti se vale Pr[E1 ∩E2] = Pr[E1] · Pr[E2]. In generale, quandoi due eventi non sono necessariamente indipendenti, abbiamo Pr[E1 ∩ E2] = Pr[E1] · Pr[E2|E1] =Pr[E2] · Pr[E1|E2].

La formula precedente e generalizzata al caso di n eventi nel modo seguente

Pr[∩ni=1Ei] = Pr[E1] · Pr[E2|E1] · Pr[E3|E1 ∩ E2] · · ·Pr[En| ∩n−1

i=1 Ei].


2.1. Un semplice algoritmo probabilistico per min cut. Un cut (taglio) di un grafo G =(V,E) e un sottoinsieme C di archi la cui rimozione disconnette il grafo. Il taglio di cardinalitaminima puo essere calcolato in tempo polinomiale usando la ben nota relazione con il massimo flusso.Presentiamo un semplice algoritmo probabilistico per il calcolo del minimo taglio (vedi [8]).

L’algoritmo consiste di n− 2 fasi (n e il numero di vertici del grafo). In ciascuna fase l’algoritmosceglie a caso una coppia (u, v) di vertici del grafo che sono connessi da almeno un arco. I vertici u ev sono rimossi dal grafo e sostituiti da un nuovo vertice w. Gli archi tra u e v sono rimossi dal grafoe gli archi tra u o v ed altri vertici avranno come estremo w. Piu precisamente, se u e v avevano,rispettivamente, nu ed nv archi con il vertice x, il vertice w avra nu + nv archi che raggiungono ilvertice x. Alla fine di n− 2 passi, il grafo consiste di due soli vertici, chiamiamoli s e t, e di un certonumero di archi paralleli tra s e t. Questi archi costituiscono un taglio che sconnette i vertici che sonostati fusi in s dai vertici che sono stati fusi in t.

Osserviamo che l’algoritmo descritto costruisce un taglio di cardinalita minima solo se ad ognipasso non sceglie nessun arco del taglio e calcoliamo quindi questa probabilita. Denotiamo con Ei

l’evento che al passo i-esimo dell’algoritmo viene scelto un arco non appartenente al taglio minimo.Allora la probabilita che l’algoritmo calcoli Calcoliamo ora, per ogni i, la probabilita

pi = Pr[Ei| ∩i−1j=1 Ej ].

La probabilita che l’algoritmo calcoli un taglio di cardinalita minima e Πni=1pi.

Se k e la cardinalita del taglio minimo di G allora ogni vertice di G ha grado almeno k e quindi ilgrafo ha almeno kn/2 archi.

Per i = 1, abbiamo che p1 = 1− (numero archi nel taglio)/(numero archi nel grafo)≥ 1− 2/n.Osserviamo che se gli eventi E1, · · · , Ei−1 si sono verificati (cioe nessun arco del taglio minimo

e stato selezionato) il grafo Gi−1 ottenuto alla fine del passo (i− 1)-esimo, ha n − i + 1 vertici,taglio minimo di cardinalita k e pertanto almeno k(n − i + 1)/2 archi. Pertanto abbiamo che pi =Pr[Ei| ∩i−1

j=1 Ej ] ≥ 1− 2n−i+1 . Abbiamo quindi

Pr[∩n−2i=1 Ei] ≥ Πn−2

i=1

(1− 2

n− i + 1

)= Πn−2

i=1

(n− i− 1n− i + 1

)=

2n(n− 1)

≥ 2n2

.

Quindi la probabilita che l’algoritmo dia in output il taglio minimo e almeno 2n2 . Questa probabilita

puo essere migliorata ripetendo l’algoritmo piu volte. Se eseguiamo l’algoritmo ` volte la probabilitache l’algoritmo non dia in output il taglio di cardinalita minima e al piu (1− 2/n2)`. Ad esempio, laprobabilita di errore puo essere ridotta a 1/e ripetendo l’algoritmo n2/2 volte.

3. Approssimazione per MaxSat

In questo sezione discutiamo algoritmi di approssimazione per MaxSat. L’esposizione e basata su[6]. Useremo la seguente proprieta della media di una variabile casuale

(1) Se E[X] ≥ x allora esiste almeno un risultato ri tale che X(ri) ≥ x.

3.1. Il problema MAXSAT. Il problema MAXSAT consiste nel calcolare, avendo in input unaformula in forma congiuntiva normale Φ = C1 ∧ · · · ∧Cm sulle variabili x1, · · · , xn, il numero massimodi clausole che possono essere simultaneamente soddisfatte da un assegnamento di verita. Indichiamocon I+

j l’insieme delle variabili che compaiono in forma non negata nella clausola Cj e con I−j levariabili che compaiono in forma negata. Assumiamo inoltre che ogni clausola contenga almeno dueletterali. Ovviamente il problema e NP-Hard.

3. APPROSSIMAZIONE PER MAXSAT 21

3.2. Esiste sempre un assegnamento buono. Supponiamo di scegliere un assegnamento ca-suale assegnando alla variabile xi il valore VERO con probabilita 1/2. E facile vedere che la probabilitache una clausola con k letterali sia soddisfatta e 1 − 2−k. Definiamo quindi la variabile casuale Xi,i = 1, · · · ,m, nel modo seguente

Xi =

1, seCi soddisfatta;0, altrimenti;

ed abbiamo che E[Xi] = (1 − 2−k). Quindi il numero medio E(Φ) di clausole di Φ soddisfatte da unassegnamento casuale e dato da

E

[m∑

i=1

Xi

]=

∑l

ml(1− 2−l)

ove ml denota il numero di clausole con l letterali. Poiche per ipotesi l ≥ 2, abbiamo 1− 2−l ≥ 3/4 epossiamo quindi concludere che esiste sempre un assegnamento che soddisfa almeno 3/4 delle clausole.

3.3. Cerchiamo un assegnamento buono. In questa sezione mostriamo come riusciamo atrovare un assegnamento che soddisfi almeno 3/4m delle m clausole della formula Φ. Poiche l’asse-gnamento che soddisfa il maggior numero di clausole non ne soddisfa piu di m, abbiamo un algoritmoche 3/4-approssima il problema MAXSAT.

Calcoliamo un assegnamento una variabile per volta partendo da x1. Consideriamo le formuleΦ(x1 = 1) e Φ(x1 = 0) ottenendo ponendo x1 = 1 e x1 = 0 nella formula Φ. Assegnamo quindi allavariabile x1 il valore b che massimizza E(Φ(x1 = b)). Osserviamo che siccome E(Φ) = 1

2(E(Φ(x1 =1)) + E(Φ(x1 = 0)) e poiche E(Φ) ≥ 3/4 abbiamo che E(Φ(x1 = b)) ≥ 3/4. Il valore di x2 edeterminato allo stesso modo considerando la formula Φ(x1 = b) invece che la formula Φ e cosı via.

3.4. Programmazione lineare. Il problema MAXSAT puo essere formulato come il seguenteproblema di programmazione lineare intera.

max W =∑m

j=1 zj

con vincoli∑i∈I+

jyi +

∑i∈I−j

(1− yi) ≥ zj j = 1, · · · ,myi ∈ 0, 1 i = 1, · · · , n0 ≤ zj ≤ 1 j = 1, · · · ,m

Per ogni assegnamento di verita (x1, · · · , xn) alle variabili della formula Φ il problema ha come valoremassimo il numero delle clausole soddisfatte. Infatti la soluzione che assegna a yi il valore di veritadella varibaile xi e a zj assegna 1 se la j-esima clausola e soddisfatta e 0 altrimenti e ammissibile edottima.

Denotiamo con Z∗I il valore del problema intero e con Z∗

L il valore del problema che si ottienerilassando il vincolo di interezza sulle variabili yi. Ovviamente, Z∗

L ≥ Z∗I . Consideriamo quindi il

seguente semplice algoritmoPasso 1.: Risolvere il problema rilassato ottendo soluzione (y∗, z∗).Passo 2.: Applicare il metodo della sezione precedente usando y∗i come probabilita di porre a

VERO la variabile xi.

Lemma 2.5. Se per una la soluzione ottima (y∗, z∗) al problema lineare rilassato vale che

1−Πi∈I+j(1− yi) ·Πi∈I−j

yi ≥ αzj


alloraE[W ] ≥ αZ∗

I .

Dimostrazione. Abbiamo che E[W ] =∑m

j=1 P (zj = 1). La variabile zj ha valore 0 se e solo setutte le varibaili che compaiono nella j-esima clausola in forma non negata hanno valore falso (eventocon probabilita Πi∈I+

j(1 − pi)) e tutti le variabile che compaiono in forma negata hanno valore vero

(evento con probabilita Πi∈I−jpi). Pertanto abbiamo che

E[W ] = Πi∈I+j(1− pi) ·Πi∈I−j

pi = Πi∈I+j(1− y∗i ) ·Πi∈I−j

y∗i ≥m∑

j−1

z∗ = αZ∗L = αZi∗ .

Quindi se l’ipotesi del teorema sono soddisfatte l’algoritmo descritto garantisce una α-approssimazione.Per il prossimo lemma usiamo la seguente ben nota diseguaglianza tra la media geometrica e la mediaaritmentica di una sequenza (a1, · · · , ak) di numeri non negativi

a1 + a2 + · · ·+ ak

k≥ k√

a1 · · · ak.

Lemma 2.6. Per ogni soluzione ammissibile (y, z) dle problema lineare rilassato e per ogni clausolaCj con k letterali abbiamo

1−Πi∈I+j(1− yi) ·Πi∈I−j

yi ≥ βkzj

con

βk = 1−(

1− 1k

)k

/

Dimostrazione. Supponiamo che la clausola Cj contenga solo letterali in forma nonnegata. Sexi appare in forma negata in Cj allora basta sosituire xi con xi e viceversa in tutte le clausole dellaformula e yi con 1− yi ed ottenere una formula ed un problema lineare equivalenti. Inoltre possiamoassumere che la clausola Cj contenga le variabile x1, · · · , xk.

Se (y, z) e una soluzione ammissibile allora il problema lineare comprende il vincolo y1 +y2 + · · ·+yk ≥ zj dobbiamo provare

1−Πki=1(1− yi) ≥ βkzk.

Applicando la relazione tra la media aritmentica e geometrica otteniamo che

1−Πki=1(1− yi) ≥ 1−

(1− zj

k

)k.

Osserviamo ora che la funzione

f(zj) = 1−(1− zj

k

)k

e concava e poiche f(0) = 0 e f(1) = βk abbiamo che, per ogni 0 ≤ zj ≤ 1, f(zj) ≥ βkzj .

Poiche per ogni k abbiamo che 1 − (1 − 1k )k < 1 − 1

e l’algoritmo descritto e un algoritmo (1 − 1e )

approssimante. Inoltre se ogni clausola contiene al piu due variabili l’algoritmo e un algoritmo 3/4-approssimante. Notiamo invece che l’algoritmo della sezione precedente era 3/4-approssimante se ogniclausola conteneva almeno due variabili. E possibile combinare i due algoritmi ed avere un algoritmoche 3/4-approssima ogni istanza.

4. CHERNOFF BOUND 23

4. Chernoff bound

Siano X1, · · · , Xn n variabili casuali indipendenti tali che Pr[Xi = 1] = pi e Pr[Xi = 0] = 1 − pi

con 0 < pi < 1 e con media E[Xi] = pi.Consideriamo la variabile causale X

def=∑n

i=1 Xi e poniamo µ = E[X] =∑n

i=1 pi. Il prossimoteorema ci da una stima, per δ > 0, della probabilita che X assuma un valore che sia (1 + δ) volte lasua media µ.

Teorema 2.7 (Chernoff Bound). Siano X1, · · · , Xn variabili causali indipendenti tali che Pr[Xi =1] = pi e Pr[Xi = 0] = 1 − pi con 0 < pi < 1 e sia X la variabile casuale X =

∑ni=1 Xi. Allora,

ponendo µ = E[X], abbiamo per δ > 0

Pr[X > (1 + δ)µ] <

[eδ

(1 + δ)1+δ

]µ

e

Pr[X < (1− δ)µ] < e−µδ2

2 .

Definiamo le seguenti quantita che risulteranno utili di seguito.

(1) F+(µ, δ) =[

eδ

(1+δ)1+δ

]µ.

(2) ∆+(µ, ε) e il valore di δ tale che F+(µ,∆+(µ, ε)) = ε. Quindi abbiamo che

Pr[X > (1 + ∆+(µ, ε))µ] < ε.

(3) F−(µ, δ) = e−µδ2

2 .(4) ∆−(µ, ε) e il valore di δ tale che F−(µ,∆−(µ, ε)) = ε. Quindi abbiamo che

Pr[X < (1−∆−(µ, ε))µ] < ε.

4.1. Esempi. Supponiamo di lanciare una moneta per 100 volte e definiamo, per i = 1, · · · , 100,la variabile casuale

Xi =

1, i−esimo lancio testa;0, i−esimo lancio croce.

Abbiamo ovviamente che Pr[Xi = 1] = 1/2 e E[Xi] = 1/2 per tutte le i. La variabile casualeX =

∑100i=1 Xi conta il numero di teste in 100 lanci e abbiamo che µ = E[X] = 50. Usando il Chernoff

bound possiamo calcolare un upper bound alla probabilita che in 100 lanci esca testa per piu di undato numero x di volte.

x = 60: Per calcolare Pr[X > 60] poniamo δ = .2 e applicando il Chernoff bound abbiamo

Pr[X > 60] <

[e.2

1.21.2

]50

≈[1.2211.244

]50

≈ 0.393.


Pr[X > 70] <

[e.4

1.41.4

]50

≈[1.4911.601

]50

≈ 0.028.


Pr[X > 80] <

[e.6

1.61.6

]50

≈[1.8222.121

]50

≈ 0.0005.


4.2. Permutation Routing in un Ipercubo. In questa sezione discutiamo un problema percui esiste un algoritmo probabilistico che e provatamente migliore di ogni algoritmo deterministico.L’analisi dell’algoritmo utilizza i Chernoff Bound.

Consideriamo una rete di comunicazione modellato mediante un grafo con N nodi. Ogni nodo icontiene inizialmente un pacchetto vi che deve essere recapitato alla destinazione di. Ad ogni passoun nodo puo inviare un pacchetto a ciascuno dei suoi vicini. Consideriamo il caso, denominato permu-tation routing, in cui ogni nodo deve inviare un pacchetto ed ogni nodo e destinatario di esattamenteun pacchetto e ci restringiamo ad una classe di algoritmi particolarmente semplici da implementaredenominati algoritmi oblivious. Un algoritmo per il permutation routing consiste nell’assegnamentodi una rotta (sequenza di archi) che il pacchetto deve seguire dall’origine alla destinazione. In unalgoritmo oblivious la rotta seguito da un pacchetto dipende solo dalla sua origine e dall asua desti-nazione. E possibile che ad un certo punto, diversi pacchetti desiderano attraversare uno stesso arco.In questo caso uno solo dei pacchetti sara instradato e gli altri pacchetti saranno memorizzati in unacoda e considerati al prossimo passo. Per l’analisi dell’algoritmo che presenteremo e ininfluente qualepacchetto e scelto ad ogni passo ma e importante che, se esistono pacchetti pronti per un arco, nevenga spedito alemo uno.

Il seguente teorema prova un limite all’efficienza di un algoritmo oblivious deterministico.

Teorema 2.8. Per ogni algoritmo deterministico oblivious su un grafo con N nodi e grado massimod, esiste un’istanza del problema del permutation routing che richiede Ω(

√N/d) passi.

Consideriamo come grafo l’ipercubo. L’ipercubo di dimensione n contiene N = 2n nodi ciascunoidentificato da una diversa sequenza di n bit. I nodi (a1, · · · , an) e (b1, · · · , bn) sono adiacenti sedifferiscono in esattamente una posizione. Quindi ogni nodo dell’ipercubo ha grado n = log2 N . Comeconsequenza del Teorema 2.8, ogni algoritmo deterministico per permutation routing sull’ipercuboprende tempo Ω(

√N/n) passi.

Esempio 2.9. Consideriamo il seguente semplice algoritmo oblivious denominato bit fixing. Larotta seguita da un pacchetto che deve andare da a = (a1, · · · , an) a b = (b1, · · · , bn) e calcolata con-siderando i bit di a da sinistra a destra e consiste dei seguenti nodi a = (a1, · · · , an), (b1, a2, · · · , an),(b1, b2, · · · , an), · · · (b1, b2, · · · , bn). Ovviamente, ogni rotta consiste di al piu n archi. Osserviamo chese per qualche i abbiamo ai = bi allora i vertici (b1, b2, · · · , bi−1, ai, · · · , an) e (b1, b2, · · · , bi−1, bi, · · · , an)coincidono.

4.3. Routing probabilistico. In questa sezione consideriamo il seguente algoritmo obliviousprobabilistico.

Fase I: Ogni nodo i sceglie un destinazione intermedia a caso si e il paccheto vi e instradatoda i a si usando l’algoritmo bit-fixing.

Fase II: Il pacchetto vi e instradato da si alla sua destinazione finale di.

Lemma 2.10. Due rotte possono condividere degli archi. Una volta che le rotte si separano nonavranno altri archi in comune.

Lemma 2.11. Sia ρi = (e1, · · · , ek) la rotta seguita dal pacchetto vi sia S l’insieme di pacchettidifferenti da vi le cui rotte attraversano almeno un arco di ρi. Allora il ritardo accumulato da vi e alpiu |S|.

Dimostrazione. Mostreremo che per ogni passo in cui vi viene ritardato, esiste un pacchetto diS che e inviato per l’ultima volta lungo un arco di ρi. Cio prova immediatamente che il ritardo di vi

e al piu |S|.Se un pacchetto e pronto al passo t ad essere instradato lungo ej allora diciamo che il suo ritardo

e t− j. Inizialmente il ritardo di vi e 0.

5. VERIFICA PROBABILISTICA 25

Osserviamo che quando il ritardo di vi passa da ` a ` = 1, deve esistere almeno un pacchetto vj ∈ Sdesidera attraversare lo stesso arco di vi allo stesso istante. Il pacchetto vj ha quindi ritardo `.

Sia ora t′ l’ultimo istante in cui esiste un pacchetto v di S con ritardo `. Per definizione di ritardov e pronto ad attraversare l’arco ej′ con t′− j′ = `. Poiche v e pronto ad attraversare ej′ , deve esistereun pacchetto w (possibilmente v stesso) che attraversa ej′ al tempo t′ e la cui rotta non include ej′+1.Se cosı non fosse al passo t′ + 1 avremmo un pacchetto pronto ad attraversare l’arco j′ + 1 e il suoritardo sarebbe t′ + 1− (j′ + 1) = ` contraddicendo la massimalita di t′.

Definiamo la variabile casuale Hij essere 1 se le rotte di vi e vj condividono almeno un arco e 0altrimenti. Per il teorema precedente il ritardo accumulato da vi e al piu Hi =

∑nj=1 Hij . Osserviamo

ora che le variabili casuali Hij sono indipendenti possiamo applicare il Chenoff bound. Calcoliamoquindi un bound su E[H].

Consideriamo la variabile casuale T (e) che conta il numero di rotte che utilizzano l’arco e. Peruna rotta ρi abbiamo che

(1) Hi ≤∑e∈ρi

T (e).

Ovviamente, per ragioni di simmetria dell’ipercubo, abbiamo che, per ogni coppia di archi e ed e′,E[T (e)] = E[T (e′)]. Inoltre la lunghezza media di una rotta e n/2 e quindi la lunghezza media ditutte le rotte e Nn/2. Poiche l’ipercubo ha Nn archi, abbiamo che E[T (e)] = 1/2. Sostituendo in 1ed osservando che una rotta comprende al piu n archi, abbiamo

E[Hi] ≤ n/2.

Applicando il Chernoff bound otteniamo che la probabilita che Hi sia maggiore di 6n e al piu 2−6n.Poiche il numero di pacchetti e N = 2n, la probabilita che esista un pacchetto vi che impieghi piu di6n passi per raggiungere la sua destinazione intermedia e al piu 2−5n. Gli stessi argomenti possonoessere usati per provare che anche la seconda fase impiega tempo al piu 2−5n e quindi possiamo direche con probabilita almeno 1− 1/N l’algoritmo termina in 12n passi.

Abbiamo in definitiva il seguente teorema.

Teorema 2.12. Esiste un algoritmo deterministico oblivious di routing su un ipercubo con N nodiche impiega non piu di 12 log2 N passi con probabilita almeno 1− 1/N .

4.4. Nota bibliografica. Queste note seguono l’esposizione data in [11]. L’algoritmo probabi-listico per il routing su ipercubo e stato proposto da Valiant in [13]. Il lower bound enunciato dalTeorema 2.8 appare in [7] e migliora un precedente bound di [1].

5. Verifica probabilistica

In questo capitolo discutiamo algoritmi probabilistici per la verifica. L’esposizione segue [11].La tecnica esposta nella prima sezione per verificare il prodotto di due matrici e da attribuirsi aFreivalds [4].

5.1. Verifica di prodotto di matrici. Supponiamo di avere due matrici A e B di dimensionin × n le cui entry sono prese da un campo finito F . Esistono diversi algoritmi per il calcolo delprodotto di A e B: l’algoritmo che deriva direttamente dalla definizione impiega tempo O(n3) mentrel’algoritmo piu veloce asintoticamente noto impiega tempo O(n2.376) (vedi [3]) ed e estremamentedifficile da implementare. Supponiamo di voler verificare che una data implementazione dell’algoritmoveloce ha calcolato correttamente il prodotto di A e B. Ovviamente potremo calcolare il prodotto di Ae B usando l’algoritmo naive che prende tempo O(n3) ma in questo caso perdiamo i benefici dell’averusato l’algoritmo veloce. Vogliamo quindi un algoritmo che riceve in input A, B e C (il prodottocalcolato dall’algoritmo veloce) e in tempo o(n2.376) ci dice se e stato commesso un errore.


Mostriamo quindi un algoritmo probabilistico R che ha la seguente proprieta:1. se C = A ·B, allora R su input A,B e C da in output 1 (ad indicare che nessun errore e stato

commesso);2. se C 6= A ·B, allora R su input A,B e C da in output 1 con probabilita al piu 1/2.

Algorithm R(A,B, C)01. Scegli a caso r ← 0, 1n;02. Calcola x = Br;03. Calcola y = Ax;04. Calcola z = Cr;05. if y = z then return 1;06. return 0;

Il prodotto di un vettore di n elementi per una matrice n × n (passi 2,3, e 4) puo essere calcolato intempo O(n2) e l’uguaglianza di due vettori (passo 5) puo essere verificata in tempo O(n). Pertantol’algortimo R prende tempo O(n2). Proviamo ora che l’algoritmo R gode delle proprieta 1 e 2.

Prova Prop. 1. Se C = A ·B allora y = Ax = ABr = Cr = z e quindi l’algoritmo R da sempre inoutput 1.

Prova Prop. 2. Supponiamo che C 6= A ·B e sia D = AB − C. L’algoritmo R da in output 1 se esolo se y = z o, equivalentemente, se Dr = 0.

Vogliamo quindi dare un limite superiore alla probabilita che per una matrice non nulla D e perun vettore casuale r si abbia che Dr = 0.

Supponiamo senza perdita di generalita che le prime k > 0 entry della prima riga di D siano nonnulle. Se Dr = 0 necessariamente il prodotto dT r tra la prima riga d di D ed il vettore r deve esserenullo. D’altro canto abbiamo che

dT r =k∑

i=1

diri

quindi dT r = 0 se e solo se

r1 = −∑k

i=2 diri

d1

che, poiche r1 e scelto a caso, ha probabilita al piu 1/2.Quindi se C 6= A ·B, la probabilita che l’algoritmo dia 1 come output e al piu 1/2.

5.2. Verifica di identita tra polinomi.

Teorema 2.13 (Schwartz [12]). Sia Q(x1, · · · , xn) ∈ F [x1, · · · , xn] un polinomio in n variabilicon coefficienti in F di grado d. Si fissi un insieme S ⊆ F e siano r1, · · · , rn scelti indipendentementeed uniformemente a caso da S. Allora abbiamo che

Pr[Q(r1, · · · , rn) = 0|Q(x1, · · · , xn) 6≡ 0] ≤ d

|S|.

Per provare il teorema abbiamo bisogno del seguente lemma di probabilita.

Lemma 2.14. Sia A e B due eventi. Allora

Pr[A] ≤ Pr[A|B] + Pr[B].

Dimostrazione. DaPr[A ∪ B] = Pr[A] + Pr[B]− Pr[A ∩ B]

6. ESERCIZI 27

otteniamo

Pr[A] = Pr[A ∪ B] + Pr[A ∩ B]− 1 + Pr[B]≤ Pr[A ∩ B] + Pr[B]

(in quanto Pr[A ∪ B] ≤ 1)≤ Pr[A|B] · Pr[B] + Pr[B]≤ Pr[A|B] + Pr[B].

Dimostrazione. (del Teorema 2.13.)La prova procede per induzione sul numero n di variabili.

Se n = 1, abbiamo un polinomio in una variabile di grado d. Se Q non e identicamente nullo,sappiamo che Q ha al piu d zeri. Quindi se r e scelto dall’insieme S, la probabilita che Q(r) = 0 e alpiu d/|S|.

Consideriamo ora il polinomio Q(x1, · · · , xn) di grado d. Mettendo in evidenza la variabile x1

possiamo scrivere

Q(x1, · · · , xn) =k∑

i=0

xi1Qi(x2, · · · , xn)

ove k e il massimo esponente di x1. Quindi il coefficiente Qk(x2, · · · , xn) non e identicamente nulloed ha grado al piu d− k. Quindi, per ipotesi induttiva, la probabilita che Qk(r2, · · · , rn) = 0 e al piu(d− k)/|S|.

Supponiamo ora che Qk(r2, · · · , rn) 6= 0 e consideriamo il seguente polinomio ad una variabile

q(x1) = Q(x1, r2, · · · , rn) =k∑

i=0

xi1Qi(r2, · · · , rn).

Il polinomio q non e identicamente nullo e quindi la probabilita che q(r1) = Q(r1, · · · , rn) = 0 e al piuk/|S|. Abbiamo quindi le seguente due relazioni:

Pr[Qk(r2, · · · , rn) = 0] ≤ d− k

|S|,

P r[Q(r1, · · · , rn) = 0|Qk(r2, · · · , rn) 6= 0] ≤ k

|S|,

ed usando il Lemma 2.14 abbiamo il teorema.

6. Esercizi

Esercizio 11. Calcolare la probabilita che l’algoritmo per il calcolo del min cut di Sezione 2.1 diain output un min cut nel caso in cui l’input e

(1) un ciclo di n nodi;(2) il grafo completo con n nodi.

Versione: 1.11 del 9 novembre 2004.

Bibliografia

[1] A. Borodin and J. E. Hopcroft. Routing, merging, and sorting on parallel models of computation. J. Comput. Syst.Sci., 30(1):130–145, 1985.

[2] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposiumon Theory of computing, pages 151–158. ACM Press, 1971.

[3] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progression. Journal of SymbolicComputation, 9:251–280, 1990.

[4] R. Freivalds. Probabilistic machines can use less running time. In B. Gilchrist, editor, Information Processing 77,Proceedings of IFIP Congress 77, pages 839–842. North-Holland, 1997.

[5] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, 1979.[6] Michel X. Goemans and David Williamson. New 3

4-approximation algorithms for MAX SAT. SIAM Journal on

Discrete Mathematics, 7:656–666, 1994.[7] C. Kaklamanis, D. Krizanc, and T. Tsantilas. Tight bounds for oblivious routing in the hypercube. In Proceedings

of the second annual ACM symposium on Parallel algorithms and architectures, pages 31–36. ACM Press, 1990.[8] D. Karger. Global mincut in RNC and other ramifications of a simple min-cut algorithm. In Proceedings of the 4th

Annual ACM-SIAM Symposium on Discrete Algortihms, pages 21–30, 1993.[9] R. M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85–103,

1972.[10] L. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):265–266, 1973.[11] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.[12] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–

717, October 1980.[13] L. G. Valiant. A scheme for fast parallel communication. SIAM J. Comput., 11(2):350–361, 1982.

29

Date post:	17-Feb-2019
Category:	Documents
Upload:	phungkhuong
View:	212 times
Download:	0 times

Algoritmi e Strutture Dati--Lecture Noteslibeccio.di.unisa.it/ASDII/2004/Appunti/ParteA2004.pdf4...

Documents