Algoritmi e Strutture Dati--Lecture...

Note per Algoritmi e Strutture Dati

Argomenti Avanzati

Anno Accademico 2006-2007

Giuseppe Persiano

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

Universita di Salerno

Indice

Capitolo 1. NP-completezza 71. La classe P 72. La classe NP 83. La classe NP− COMPLETE 104. Un primo linguaggio NP-completo 125. Il linguaggio CNFSAT 136. Il linguaggio 3SAT 147. Il linguaggio 2SAT 148. Algoritmo deterministico per 3SAT 179. Il linguaggio LinIntProg 1810. Il linguaggio Clique 1911. Il linguaggio 3Col 1912. Decisione e ricerca 2013. Esercizi 22Note bibliografiche 23

Capitolo 2. Introduzione agli algoritmi probabilistici 251. Ripasso di probabilita discreta 252. Eventi indipendenti 283. Algoritmo probabilistico per 2SAT 294. Approssimazione per MaxSAT 305. Chernoff bound 316. Verifica probabilistica 347. Esercizi 36

Capitolo 3. Algoritmi di Approssimazione 391. Problemi di Ottimizzazione 392. Vertex cover 403. MaxCut 424. Set cover 435. TSP 436. MaxSAT 437. Vertex Cover pesato 468. Zaino 0/1 479. Minimo makespan 4910. Primale Duale 5211. Esercizi 52

3

4 INDICE

Capitolo 4. Algoritmi On-Line 551. Il problema dello sciatore 552. Ritrovare l’auto 563. Gestione online di liste 56

Bibliografia 61

INDICE 5

SommarioQuesto documento contiene note per il secondo corso di Algoritmi e Strutture Dati che

l’autore ha tenuto presso la Facolta di Scienze dell’Universita di Salerno nell’anno accademico2006/2007.

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

http://libeccio.dia.unisa.it/ASDII/2006/Appunti/2006.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 dellestringhe di lunghezza finita su Σ).

Tipicamente, l’alfabeto Σ coincide con l’insieme 0, 1. La teoria dell’NP-completezza ele definizioni delle classi P e NP sono invarianti rispetto alla scelta dell’alfabeto purche questicontenga almeno due 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 unalgoritmo A tale che

(1) A decide L;(2) esistono una costante n0 ed una una costante c tali che per ogni x ∈ 0, 1∗ di

lunghezza almeno n0, A si ferma dopo al piu |x|c passi.

Notiamo che nella definizione precedente l’ordine dei quantificatori e essenziale. Suppo-niamo di invertire l’ordine del quantificatore sulla costante c e il quantificatore sulla stringa xottenendo la seguente condizione:esiste una costante n0 tale che per ogni x ∈ 0, 1∗ di lunghezza almeno n0 esiste una costantec tale che A si ferma dopo al piu |x|c passi.Notiamo che la nuova condizione permettere di scegliere una costante c per ogni possibile inputx. La definizione originale invece impone che l’esistenza di una sola costante che vale per tuttigli input.

1.1. Esempi. 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 diun grafo). Per comodita, e con un piccolo abuso di notazione, indicheremo conG sia il grafo che la sua rappresentazione.• u e v sono due vertici di G che si trovano a distanza al piu k.

7

8 1. NP-COMPLETEZZA

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

Definizione 1.4. Un grafo G = (V, E) si dice euleriano se esiste una permutazione degliarchi e0, · · · , 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 archiuna ed una sola volta.

Teorema 1.5. Un grafo G e euleriano se e solo se G e connesso e tutti i vertici di Ghanno grado pari.

Dimostrazione. La condizione e ovviamente necessaria.Proviamo ora che 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. Setutti i vertici di un grafo hanno grado pari allora certamente il grafo contiene un ciclo (anchese non necessariamente questo ciclo include tutti i vertici del grafo).

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 connesso ei cicli C1, · · · , Ck contengono tutti gli archi di G, certamente esisteranno due cicli, siano essisenza perdita di generalita C1 e C2, che hanno un vertice in comune. Piu precisamente siaC1 = 〈a0, · · · , al−1〉 e sia C2 = 〈b0, · · · , br−1〉 e supponiamo che ai e bj siano lo stesso vertice(non stiamo considerando il caso in cui C1 e C2 hanno piu di un vertice in comune; questocaso e lasciato al lettore). 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’algoritmo 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 lestringhe che 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 Lappartiene alla classe NP, se e possibile verificare in tempo polinomiale l’appartenenza di unastringa x ad L. Formalmente abbiamo la seguente definizione.

2. LA CLASSE NP 9

Definizione 1.6. Un linguaggio L appartiene alla classe NP se esiste un algoritmo A(·, ·)tale che

(1) esistono costanti n0 e c tale che per ogni x, y ∈ 0, 1∗ con |x| ≥ n0, A(x, y) si fermain al piu |x|c passi;

(2) per ogni stringa x ∈ L esiste una stringa y ∈ 0, 1? tale che A(x, y) = 1;(3) 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 lunghezzapolinomiale nella lunghezza di x che e “verificato” da A in tempo polinomiale e se x 6∈ L nonesiste alcun certificato y. L’algoritmo A e anche chiamato algoritmo polinomiale di verifica.Nota che, poiche il tempo di esecuzione di A e polinomiale nella lunghezza del primo input, yha 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 laDefinizione 1.6.

Consideriamo il seguente algoritmo.

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)al linguaggio Clique. L’algoritmo A verifica che il certificato consiste di k vertici (righe 01-02), che tutti i k vertici del certificato sono differenti (righe 03-06) e che i vertici del certificatocostituiscono un sottografo completo di G (righe 07-10). Se tutte le verifiche hanno successol’algoritmo restituisce 1; altrimenti l’algoritmo restituisce 0. Osserviamo che se G ha un sot-tografo completo di taglia k costituito dai vertici (v1, · · · , vk) allora l’algoritmo A con input(G, k) e (v1, · · · , vk) restituisce 1. Quindi la condizione 2 della Definizione 1.6 e soddisfatta.

Se invece G non ha nessun sottografo completo di taglia k allora per ogni sequenza divertici (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;

10 1. NP-COMPLETEZZA

(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 valore1. La condizione 3 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∈ Lallora per 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 nonabbiamo ancora una prova. La Teoria dell’NP-completezza (che verra discussa nella prossi-ma sezione) identifica i linguaggi piu difficili di NP. Se almeno uno di essi ha un algoritmopolinomiale che lo decide allora P = NP.

3. La classe NP− COMPLETE

Abbiamo le seguenti definizioni.

Definizione 1.8 (Riduzione). Sia L1 e L2 due linguaggi. Diciamo che L1 si riduce a L2

(in simboli 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 mas-simo di un insieme I definito come quell’elemento x ∈ I tale che, per ogni y ∈ I, vale y ≤ x.La nozione di linguaggio NP-completo esprime formalmente il concetto di linguaggio piu dif-ficile di NP. Il seguente teorema rafforza la nostra intuizione dicendoci che se un linguaggioNP-completo appartiene a P allora tutti i linguaggi in NP possono essere decisi in tempopolinomiale.

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′ chedecide L′.

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. Consideriamoora il seguente algoritmo A′

3. LA CLASSE NP − COMPLETE 11

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

Chiaramente l’algoritmo A′ e polinomiale. Supponiamo che x ∈ L′. Allora, per le proprietadella riduzione R, y ∈ L e quindi A(y) = 1. Supponiamo ora che x 6∈ L′. Allora y 6∈ L e quindiA(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-completoallora L e da considerarsi “difficile”. Infatti se P 6= NP, allora non esiste alcuna algoritmopolinomiale che decide 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 dobbiamoprovare che ogni linguaggio in NP si riduce ad esso il che puo essere particolarmente difficile.Invece grazie al prossimo teorema bastera mostrare che un linguaggio NP-completo si riduce aL. Iniziamo con il provare il seguente lemma.

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

L1 e L1 ≤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);

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

Abbiamo quindi il seguente teorema.

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

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

Grazie al Teorema 1.12, per provare che un linguaggio e NP-completo basta provare cheun altro linguaggio (che gia sappiamo essere NP-completo) si riduce ad esso. Abbiamo perobisogno di un primo 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 laproprieta di 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 fissato linguaggio di programmazione (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 seguentealgoritmo polinomiale 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 eseguiti da B su input (A, x, 1k) e O(k) 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) siferma 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 dain output 0.

Mostriamo ora che ogni linguaggio L ∈ NP si riduce a S. Sia AL l’algoritmo di verificaassociato al linguaggio L e supponiamo che su un input di lunghezza n, AL impiega al piu nc

passi per una costante c. Consideriamo la seguente riduzione R. Su input x, R da in outputla tripla (AL, x, 1|x|

c). Ora dovremo dimostrare che se x ∈ L allora l’output (AL, x, 1|x|

c) della

riduzione R appartiene a S ed inoltre che se x 6∈ L allora (AL, x, 1|x|c) 6∈ S. Questa ultima

parte della dimostrazione e lasciata per esercizio.

A partire dal linguaggio S, ed usando il Teorema 1.12, possiamo provare la completezzadi altri linguaggi. Argomentiamo ora che il linguaggio CircuitSat e NP-completo mostrandoche S si riduce ad esso. Il linguaggio CircuitSat consiste di tutti i circuiti booleani C percui esiste un input y tale che C(y) = 1. Ovviamente CircuitSat ∈ NP. Mostriamo orainformalmente che S ≤p CircuitSat. La riduzione, su input (A, x, 1k) restituisce un circuitoC che prende come input y e “simula” il comportamento di k passi di un algoritmo A su input

5. IL LINGUAGGIO CNFSAT 13

(x, y). Ovviamente, per ogni (A, x, 1k) ∈ S esiste y tale che C(y) = 1 e viceversa. Abbiamoquindi il seguente teorema.

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

5. Il linguaggio CNFSAT

Una formula booleana Φ sulle variabili (x1, · · · , xn) e una formula che contiene i connettivilogici ∧ (AND), ∨ (OR) e ¬ (NOT) e le variabili x1, · · · , xn. Indichiamo invece con il terminedi letterale le variabili in forma negata e forma non negata. Ad esempio Φ = (((x1∧x2)∨ (x1∧¬x3)) ∧ (x1 ∨ x4)) e una formula booleana sulle variabili (x1, · · · , x4). Un assegnamento diverita t assegna ad ogni variabile della formula Φ un valore booleano ed induce naturalmenteun 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 formula formula Φ falsa (cioe t(Φ) = 0). Una formulaΦ si dice soddisfattibile se esiste un assegnamento di verita t tale che t(Φ) = 1; in questocaso diciamo che t rende Φ vera. Definiamo il linguaggio SAT come il linguaggio che consistedelle formule booleane Φ che sono soddifacibili. Indichiamo invece con CNFSAT il linguaggiodelle formule booleane in forma congiuntiva normale (AND di OR) che sono soddifacibili. Adesempio 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 clausolacontengono 3 letterali, la terza clausola contiene 2 letterali mentre la quarta clausola contiene4 letterali.

Teorema 1.15. [Cook-Levin] Il linguaggio CNFSATe NP-completo.

Dimostrazione. Riduciamo CircuitSat a CNFSAT nel modo seguente. Sia C il cir-cuito in input e costruiamo la formula Φ in forma CNF nel modo seguente. Φ ha, per ogni filodel circuito, una variabile y e le seguenti clausole.

(1) Se y e un filo di input che corrisponde all’input xi Φ contiene le clausole equivalentia (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 alloraaggiungiamo le 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 esisteun input y per cui C(y) = 1 allora esiste un assegnamento di verita che soddisfa Φ.

Come conseguenza del teorema precedente abbiamo che, se P 6= NP, non esiste alcunalgoritmo che in tempo polinomiale possa decidere se una qualsiasi formula booleana Φ informa congiuntiva normale data in input e soddisfattibile.

6. Il linguaggio 3SAT

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

Teorema 1.16. 3SAT∈ NP− COMPLETE.

Dimostrazione. Riduciamo CNFSAT a 3SAT e quindi, grazie al Teorema 1.12, ottenia-mo il teorema.

Sia Φ una formula in forma CNF. Costruiamo in tempo polinomiale una formula Φ′ informa 3CNF (cioe in forma CNF ove ogni clausola contiene esattamente 3 letterali) tale cheΦ′ e soddisfattibile se e solo se Φ e soddisfattibile. La costruzione considera ogni clausola C diΦ separatamente e per ognuna di esse costruisce una sequenza S di clausole. La sequenza Sdi clausole ha la proprieta che un assegnamento di verita soddisfa C se e solo soddisfa S. Laformula Φ′ e ottenuta legando insieme con l’operatore ∧ tutte le clausole ottenute. Pertantoabbiamo che Φ′ e soddisfattibile se e solo se Φ e soddisfattibile. La costruzione distingue iseguenti 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 chesono soddsfattibili, in forma congiuntiva normale e tali che ove ogni clausola contiene al piu 2letterali) puo essere deciso in tempo polinomiale.

7. IL LINGUAGGIO 2SAT 15

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp pppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp pppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp pppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp



pppppppppppppppppppppppppppppppppppppppppppppppppppppppp








x3 ¬x1 x2

¬x2 x4 ¬x3

x1 ¬x4

Figura 1. Il grafo corrispondente alla formula (x1 ∨ x2) ∧ (x1 ∨ ¬x3) ∧ (x2 ∨x4) ∧ (x3 ∨ ¬x4).

Si consideri una formula Φ in forma 2-congiuntiva normale sulle variabili (x1, · · · , xn). As-sumiamo senza perdita di generalita che le clausole di Φ contengano esattamente due letterali.Clausole con un solo letterale sono eliminate nel modo seguente. Se Φ contiene sia la clausola(xi) che la clausola (¬xi) allora Φ non e soddisfattibile e non necessario procedere oltre. SeΦ contiene la clausola xi allora ogni assegnamento di verita che soddisfa Φ assegna valorevero a xi. Quindi, tutte le clausole che contengono xi possono essere eliminate. Inoltre ognioccorrenza di ¬xi e eliminata. Se Φ contiene la clausola ¬xi si procede in maniera analoga. Ilprocesso di eliminazione termina quando 1) tutte le clausole sono state eliminate (e quindi laformula e soddisfattibile); 2) otteniamo due clausole ciascuna con un letterale che contengonouna variabile e la sua negazione (e quindi la formula non e soddisfattibile); 3) abbiamo soloclausole con esattamente due letterali e quindi procediamo con la costruzione del grafo direttoG.

Il grafo diretto G ha un vertice per ogni letterale e G contiene l’arco diretto (a, b) se esolo se Φ contiene la clausola (¬a ∨ b) (vedi esempio in Fig. 1). In altre parole, la clausola(x ∨ y) aggiunge al grafo gli archi diretti (¬x, y) e (¬y, x). Notiamo che se (a, b) e un arco diG allora anche (¬b,¬a) e un arco di G. L’arco (a, b) codifica il fatto che se un assegnamentodi verita assegna al letterale a il valore di vero (e quindi ¬a e falso) la clausola (¬a ∨ b) puoessere soddisfatta solo se b e vero.

Lemma 1.17. La formula Φ e soddisfattibile se e solo se per ogni variabile x il grafo G noncontiene sia il cammino da x a ¬x che il il cammino da ¬x a x.

Dimostrazione. Supponiamo che esista una variabile x per cui, in G, esiste sia il camminoda x a ¬x che il cammino da ¬x a x e sia, per contraddizione, t un assegnamento di veritache soddisfa Φ. Supponiamo che t(x) =vero. Poiche t(x) =vero e t(¬x) =falso allora deveesistere un arco (a, b) lungo il cammino da x a ¬x tale che t(a) =vero e t(b)=falso. Ma allorala formula Φ contiene la clausola (¬a ∨ b) che non e soddisfatta da t. Un simile ragionamentopuo essere usato nel caso in cui t(x)=falso.


Supponiamo invece che nessuna componente fortemente connessa di G contiene un letteraleed il suo negato. Allora e possibile calcolare un assegnamento di verita che soddisfa Φ ripetendoil seguente passo fino a quando tutti i nodi hanno un valore di verita.

Scegliamo un nodo x di G tale che non esiste un cammino da x a ¬x.Il nodo x e posto a vero e il nodo ¬x e posto a falso. Inoltre tutti i nodiraggiungibili da x sono posti a vero e le loro negazioni (cioe tutti i nodidai quali ¬x puo essere raggiunto) sono posti a falso.

Questo passo e consistente. Infatti non puo esistere una variabile y tale che sia y che¬y sono raggiungibili da x. Se cosı fosse allora, per la simmetria di G, esisterebbero anche icammini da y e ¬y a ¬x e quindi un cammino da x a ¬x. Inoltre partendo da x non possiamoraggiungere un nodo y a cui in un’iterazione precedente e stato assegnato il valore falso. Infattise cosı fosse da x si puo raggiungere y e quindi quando a y e stato attribuito il valore falso xsarebbe stato posto anche esso a falso. Analogamente ¬x non puo essere raggiunto da un nodoy cui in una precedente iterazione e stato assegnato il valore vero.

Notiamo infine che quando tutti i nodi hanno avuto un valore, siccome ogni volta che diamoil valore vero a un nodo tutti i suoi discendenti ottengono il valore vero e viceversa quando unnodo ottiene il valore falso, tutti i nodi adiacenti hanno lo stesso valore di verita e quindi tuttele clausole sono soddisfatte.


Teorema 1.18. 2SAT ∈ P.

7.1. Il linguaggio Max2SAT. Supponiamo di avere una formula Φ in 2CNF e suppo-niamo di aver deciso, usando l’algoritmo della sezione precedente, che Φ non e soddisfattibile.Vogliamo quindi calcolare il numero massimo di clausole di Φ che possono essere soddisfatteda un assegnamento di verita. A prima vista puo (erroneamente) sembrare che questo pro-blema sia computazionalmente semplice. Invece mostreremo che il problema e completo. Piuprecisamente definiamo il linguaggio Max2SAT come il linguaggio di tutte le coppie (k, Φ)tali che Φ e una formula in 2CNF per cui esiste un assegnamento di verita che soddisfa almenok clausole di Φ. Ovviamente Max2SAT ∈ NP. Mostriamo ora che 3SAT ≤p Max2SAT.

Consideriamo le seguenti 10 clausole

(x)(y)(z)(w)

(¬x ∨ ¬y)(¬y ∨ ¬z)(¬z ∨ ¬x)

(x ∨ ¬w)(y ∨ ¬w)(z ∨ ¬w)

Quale e il massimo numero di clausole che puo essere soddisfatto? E facile convincersi che leclausole non possono essere tutte soddisfatte: se x, y, z sono poste a vero allora le clausole dellaseconda riga non sono soddisfatte. Infatti, in questo caso possiamo soddisfare al piu 7 clausoleponendo w a vero.

Se invece solo due tra x, y e z sono poste a vero allora perdiamo una clausola dalla primariga e una dalla seconda. Se poniamo w uguale a vero perdiamo una clausola dalla terza rigamentre se poniamo w uguale a falso perdiamo una clausola dalla prima riga. In entrambi i casipossiamo soddisfare 7 clausole.

Consideriamo ora il caso in cui una sola tra x, y e z e vera. In questo caso perdiamo dueclausole dalla prima riga e tutte le clausole della seconda riga sono soddifatte. Se poniamo

8. ALGORITMO DETERMINISTICO PER 3SAT 17

w uguale a falso perdiamo una clausola dalla prima riga ma soddisfaciamo tutte le clausoledella terza riga (per un totale di 7 clausole soddisfatte). Se invece poniamo w uguale a falsopossiamo soddisfare al massimo 6 clausole.

Infine consideriamo il caso in cui x, y e z sono false. In questo caso tutte le clausole dellaseconda riga sono soddisfatte e possiamo ottenere tutte le causole della terza riga ponendo wuguale a falso. Quindi al piu 6 clausole possono essere soddisfatte.

Riassumendo abbiamo che un qualsiasi assegnamento di verita che soddisfa almeno una trax, y e z puo essere esteso a soddisfare 7 delle 10 clausole. Mentre un assegnamento di veritache non soddisfa nessuna tra x, y e z puo essere esteso a soddisfare al piu 6 clausole.

Quindi abbiamo la seguente riduzione. Per ogni formula Φ in 3CNF con m clausole co-struiamo una formula in 2CNF Ψ con 10m clausole nel modo seguente: per ogni clausolaCi = (a ∨ b ∨ c) di Φ introduciamo le 10 clausole R(Ci) sostituendo (x, y, z) con (a, b, c) edusando la variabile wi al posto di w. Abbiamo due casi:

(1) Φ e soddisfattibile e sia t un assegnamento che la soddisfa.Allora t rende vera almeno una variabile per ogni clausola Ci di Φ. Pertanto t puoessere esteso scegliendo il valore di wi in modo da soddisfare 7 delle clausole di R(Ci).Possiamo concludere che esiste un assegnamento di verita che soddisfa almeno 7mclausole di Ψ.

(2) Φ non e soddisfattibile.Allora per ogni assegnamento t esiste almeno una clausola Ci che non e soddisfatta.Quindi ogni estensione di t soddisfa al piu 6 clausole di R(Ci). Abbiamo pertanto cheogni assegnamento di verita soddisfa al piu 7m − 1 clausole di Ψ e quindi (Ψ, 7m) 6∈Max2SAT.

Abbiamo quindi provato che Φ ∈ 3SAT se e solo se (7m, Ψ) ∈ Max2SAT e siccome Ψ ecostruita in tempo polinomiale a partire da Φ abbiamo il seguente teorema.

Teorema 1.19. Max2SAT ∈ NP− COMPLETE.

8. Algoritmo deterministico per 3SAT

In questa sezione discutiamo un semplice algoritmo esponenziale per decidere 3SAT. Os-serviamo che una formula Φ con n variabili ammette O(2n) assegnamenti di verita e che pertestare ciascuno di essi prendiamo tempo O(n3) (nota che una formula in 3CNF con n variabiliha O(n3) clausole). Quindi, l’algoritmo banale che prova tutti gli assegnamenti prende tempoO(2npoly(n)). Nota che un bound piu preciso sul tempo di esecuzione e O(2nn3) ma i terminipolinomiali sono trascurabili in presenza di un esponenziale e quindi scriviamo semplicementeO(2npoly(n)). Inoltre, nota anche che per ogni ε > 0 abbiamo O(2npoly(n)) = O((2 + ε)n).

Consideriamo ora una formula Φ e, isolando la prima clausola, possiamo scrivere

Φ = (x1 ∨ x2 ∨ x3) ∧Ψ.

Usando la proprieta distributiva di ∨ rispetto a ∧ possiamo scrivere

Φ = (x1 ∧Ψ(x1 = 1)) ∨ (x2 ∧Ψ(x2 = 1)) ∨ (x3 ∧Ψ(x3 = 1)).

Notiamo che Ψ(x1 = 1) e la formula che si ottiene da Ψ sostituendo il valore booleano VERO ad

x1 ed quindi ha n−1 variabili. Un simile ragionamento vale per Ψ(x2 = 1) e Ψ(x3 = 1). E facileconvincersi che Φ e soddisfacibile se e solo almeno una tra Ψ(x1 = 1), Ψ(x2 = 1) e Ψ(x3 = 1)


e soddisfacibile e possiamo ricorsivamente decidere la soddisfattibilita delle 3 formule. Quindidenotando con T (n) il tempo impiegato per decidere la soddisfattibilita di una formula conn variabili abbiamo che T (n) = 3T (n − 1) + poly(n) la cui soluzione e O(3npoly(n)). Nonabbiamo fatto molto progresso rispetto all’algoritmo banale (anzi....).

Osserviamo pero che se Ψ(x = 1) non e soddisfattibile allora x deve essere falso in ogni(eventuale) assegnamento che soddisfa Φ. Quindi invece di controllare se Ψ(x2 = 1) e sod-disfattibile possiamo controllare se Ψ(x1 = 0, x2 = 1) (questa formula ha n − 2 variabili!)e soddisfattibile. Se neanche questa formula e soddisfatta allora in ogni (eventuale) asse-gnamento che soddisfa Φ sia x1 che x2 devono essere falsi. A questo punto controlliamo seΨ(x1 = 0, x2 = 0, x3 = 1) (questa formula ha n− 3 variabili) e soddisfattibile. Il tempo T (n)di esecuzione dell’algoritmo per una formula con n variabili soddisfa l’equazione di ricorrenza

T (n) = T (n− 1) + T (n− 2) + T (n− 3) + poly(n)

che ha come soluzione T (n) = O(1.8392npoly(n) = O(1.8393n).

9. Il linguaggio LinIntProg

In questa sezione dimostriamo che il linguaggio LinIntProg (Linear Integer Program-ming) e NP-completo mostrando una riduzione da 3SAT.

Iniziamo con il definire LinIntProg.

Definizione 1.20. Il linguaggio LinIntProg consiste di tutte le matrici m× n intere Ae di tutti i vettori n× 1 interi D per cui esiste un vettore Y di 0 e 1 tale che A · Y ≥ D.

Teorema 1.21. LinIntProg∈ NP− COMPLETE.

Dimostrazione. La prova che LinIntProg ∈ NP e lasciata al lettore.Proviamo che 3SAT ≤p LinIntProg. Sia Φ una formula in 3CNF con m clausole

C1, · · · , Cm ed n variabili. Costruiamo la matrice A ponendo

cij =

1, if xj ∈ Ci;

−1, if xj ∈ Ci;

0, altrimenti.

Poniamo inoltre di = 1 − ni dove ni e il numero di variabili che compaiono in Ci in formacomplementata. Il sistema di disequazioni ottenuto contiene una disequazione per ogni clausoladi Φ ed una variabile yi per ogni variabile booleana xi che compare in Φ. Ad esempio, allaclausola C = (x1 ∨ x2 ∨ x3) corrisponde la disequazione

y1 + y2 − y3 ≥ 0

che e equivalente a

y1 + y2 + (1− y3) ≥ 1.

Quindi se assegnamo 1 ad ogni variabile del sistema che corrisponde ad una variabile vera, ilsistema e soddisfatto se e solo se per ogni clausola esiste almeno un letterale vero.

11. IL LINGUAGGIO 3Col 19

10. Il linguaggio Clique

In questa sezione mostriamo che il linguaggio Clique e NP-completo mostrando unariduzione da 3SAT.

Teorema 1.22. Clique∈ NP− COMPLETE.

Dimostrazione. Sia Φ una formula in forma CNF ove ogni clausola contiene esattamente3 letterali. Sia inoltre k il numero di clausole di Φ. La riduzione restituisce la coppia (G, k)ove il grafo G e costruito nel modo seguente. Il grafo G ha un vertice per ogni occorrenzadi un letterale: Se il letterale xi appartiene alla j-esima clausola di Φ, il grafo G conterra ilvertice v(i, j); diremo in questo caso che il vertice v(i, j) appartiene alla j-esima clausola. Seil letterale ¬xi appartiene alla j-esima clausola 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 verticedi G ha un arco verso ogni altro vertice di G con le 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

appartengono 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

un letterale vero. Consideriamo quindi k vertici (uno per clausola) di G corrispondentia letterali di Φ veri per l’assegnamento t e mostriamo che constituiscono una cliquein G. Infatti, questi k vertici appartengono a clausole differenti e non abbiamo traquesti vertici v(i, j) e n(i, j ′) cossipondenti ad una variabile xi ed al suo negato ¬xi

(altrimenti t non sarebbe un buon assegnamento di verita). Pertanto i k verticicostituiscono un sottografo completo di taglia k e 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 corri-spondenti a vertici di C. L’assegnamento t e certamente legale per la proprieta (2b)e, per la proprieta (2a), soddisfa tutte le clausole di Φ. Quindi Φ ∈ 3SAT.

11. Il linguaggio 3Col

Il linguaggio 3Col consiste di tutti i grafi i cui vertici possono essere colorati usando 3colori in modo tale che due vertici adiacenti sono colorati con colori diversi. E facile verificareche 3Col ∈ NP.

Riduciamo 3SAT a 3Col usando i tre gadget descritti dalla Figura 2. In particolare lariduzione per la formula Φ sulle variabile x1, · · · , xn costruisce un grafo che contiene:

(1) un gadget per il vero e falso;


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................ ..

..............................................................................................................................................................................................................................................................

Il gadget per la clausola (a ∨ b ∨ c)

Il gadget per il vero ed il falso Il gadget per la variable a

~

~

~

~

~

~ ~ ~

~

~

~ ~

~

~~

V

X

F a ¬a

X

V

ba c

Figura 2. I tre gadget per la riduzione di 3SAT a 3Col.

(2) un gadget per ciascuno delle variabile; nota che i gadget delle variabili condividono ilvertice X con il gadget per il vero e il falso;

(3) un gadget per ogni clausola; nota che il gadget per la clausola (a ∨ b ∨ c) condivide ilvertice a con il gadget della variabile a, il vertice b con il gadget della variabile b, ilvertice c con il gadget della variabile c ed il vertice V con il gadget per il vero e falso.

Notiamo che il gadget per le variabili impone che i vertici a e ¬a devono essere colorati uno conV ed uno con F. Possiamo inoltre verificare che se i tre vertici dei letterali di una clausola Csono colorati con F allora non e possibile colorare i restanti vertici del gadget di C. Se invecealmeno uno di essi e colorato con V allora e possibile completare la colorazione del gadget diC. Abbiamo quindi il seguente

Teorema 1.23. 3Col ∈ NP− COMPLETE.

12. Decisione e ricerca

Nella nostra discussione sull’apparente difficolta computazionale di alcuni problemi ci sia-mo concentrati sul problema di decisione: decidere se una tale istanza gode o no di una certaproprieta. Ad esempio, il problema decisionale associato al linguaggio CNF-SAT consiste neldecidere se una data formula Φ ammette un assegnamento di verita che la soddisfa. Altrettantointeressante e il problema di ricerca associato a CNF-SAT: data una formula Φ soddisfattibile

12. DECISIONE E RICERCA 21

trovare un assegnamento di verita che la soddisfa. Ovviamente, se abbiamo un algoritmo poli-nomiale che risolve il problema di ricerca allora anche il problema decisionale puo essere risoltoin tempo polinomiale. Proviamo ora che se abbiamo un oracle O che decide appartenenza aCNF-SAT allora possiamo costruire un algoritmo A che, ricevuto in input una formula in CNFΦ, da in output un assegnamento di verita che soddisfa Φ se un tale assegnamento esiste. Iltempo di esecuzione di A e polinomiale e A interroga O un numero polinomiale di volte. Cioimplica che se il problema decisionale associato a CNF-SAT ha un algoritmo polinomiale ancheil problema di ricerca puo essere risolto in tempo polinomiale.

La seguente notazione risulta utile nella prova di questo risultato. Se Φ e una formulain CNF sulle variabili x1, . . . , xn allora la formula Φ(xi = bi), per bi ∈ 0, 1, si ottienesostituendo le occorrenze di 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 soddisfattibile se e solo se esiste un assegnamento di verita chesoddisfa Φ e che pone xi = bi. Ragioniamo quindi nel modo seguente. Sia Φ soddisfattibile esia t un assegnamento di verita che la soddisfa. Due casi sono possibili:

(1) t(x1) = 0; in questo caso abbiamo per l’osservazione precedente che Φ(x1 = 0) esoddisfattibile;

(2) t(x1) = 1; in questo caso abbiamo che Φ(x1 = 1) e soddisfattibile.

L’oracolo O puo essere usato per decidere quale dei due casi vale. Abbiamo quindi il seguentealgoritmo.

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;

12.1. Approccio generale. Il risultato ottenuto per il caso speciale di CNF-SAT puoessere ottenuto anche per altri specifici linguaggi in NP (vedi ad esempio l’Esercizio 1.7 in cuisi chiede di ottenere l’equivalenza per il problema della Clique) e puo essere generalizzato atutti i linguaggi NP-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 Lconsiste nel 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. Alloraesiste un algoritmo polinomiale che usa O come oracolo, effettua un numero polinomiale dichiamate ad O e risolve il problema di ricerca associato ad L. La prova di questo asserto elasciata come esercizio.

13. Esercizi

Esercizio 1.1. Se L e un linguaggio, definiamo L (il complemento di L) come la differenzasimmetrica

L = Σ∗ \ L.

Provare che se L ∈ P allora L ∈ P .

Esercizio 1.2. Denotiamo con co-NP la classe dei linguaggi L tali che L ∈ NP. Provareche se NP 6= co-NP allora P 6= NP.

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

Esercizio 1.4. Sia L un linguaggio. Definiamo il linguaggio L? come il linguaggio di tuttele stringhe w 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 1.5. Usando la notazione dell’esercizio precedente, provare che se L ∈ P alloraL? ∈ P .

Esercizio 1.6. Si consideri il linguaggio Hamilton dei grafi hamiltoniani. Un grafo edetto hamiltoniano se esiste un cammino che visita tutti i vertici una sola volta. Provare cheHamilton∈ NP.

Esercizio 1.7. Provare l’equivalenza tra il problema decisionale e il problema di ricercaper il linguaggio Clique.

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

Esercizio 1.9. Abbiamo un trasmettitore che vuole inviare un messaggio ad un insiemeD = d1, · · · , dm di m destinazioni. Il trasmettitore e collegato ad n coppie di ripetitori(ai, bi), i = 1, · · · , n ed ogni ripetitore ai (rispettivamente bi) e collegato ad un sottoinsiemeAi (rispettivamente Bi) di destinazioni. Per evitare interferenze per ogni coppia di ripetitori(ai, bi) possiamo avere esattamente un solo ripetitore attivo. Diciamo che e possibile trasmet-tere il messaggio se esiste un modo di attivare i ripetitori in modo tale che per ogni coppia soloun ripetitore e attivo ed ogni destinazione e adiacente ad almeno un ripetitore attivo.

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

NOTE BIBLIOGRAFICHE 23

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

Esercizio 1.10. Provare che il problema di determinare se una formula Φ in forma con-giuntiva normale con esattamente 3 letterali per clausola ammette un assegnamento di veritatale che per ogni clausola esistono almeno due letterali veri e decidibile in tempo polinomiale.

Esercizio 1.11. Provare che il problema di determinare se una formula Φ in forma con-giuntiva normale con esattamente 3 letterali per clausola e dove ogni letterale compare esat-tamente 3 volte ammette un assegnamento di verita che la soddisfa e decidibile in tempopolinomiale.

Esercizio 1.12. Abbiamo provato che Max2SAT e completo. Questo non significa cheMax2SAT e difficile per tutte le classi di input.

Provare che e possibile decidere in tempo polinomiale se (Φ, m− 1) ∈Max2SAT, dove me il numero di clausole di Φ. Estendere questo risultato al caso (Φ, m − c) per ogni costantec > 0.

Esercizio 1.13. Un monomio e un AND di letterali. Una formula e in forma disgiuntivanormale (DNF in breve) se e un OR di monomi. Ad esempio la seguente formula e in formaDNF Φ = (x1 ∧ x2 ∧ x3) ∨ (¬x1 ∧ ¬x2 ∧ x4).

Definiamo il linguaggio DNFSAT come il linguaggio delle formule in DNF che sonosoddisfattibili. Provare che DNFSAT ∈ P.

Esercizio 1.14. Data una formula in 3CNF possiamo usare la legge distributiva perconstruire una formula equivalente in DNF. Ad esempio abbiamo che

(x1∨x2∨¬x3)∧ (¬x1∨¬x2) ≡ (x1∧¬x1)∨ (x1∧¬x2)∨ (x2∧¬x1)∨ (¬x3∧¬x1)∨ (¬x3∧¬x2).

Poiche abbiamo visto che DNFSAT∈ P (Esercizio 1.13) abbiamo che P = NP. Dove e l’errore?

Esercizio 1.15. Set Covering. Dimostrare che il linguaggio delle coppie (S, k) costituiteda una famiglia di sottoinsiemi S = S1, · · · , Sm di 1, · · · , n e da un intero k tali che Scontiene k sottoinsiemi disgiunti e NP-completo.

(Suggerimento: ridurre da Clique.)

Esercizio 1.16. Node Cover. Dimostrare che il linguaggio delle coppie (H, `) costituiteda un grafo H e da un intero ` tali che esiste un sottoinsieme R dei vertici di H di cardinalita≤ ` e tale che ogni arco di H tocca almeno un vertice di R e NP-completo.

(Suggerimento: ridurre da Clique.)

Note bibliografiche

La teoria dell’NP-completezza e stata introdotta da S. Cook in [3] (che ha provato che illinguaggio delle formule in forma disgiuntiva normale che non sono una tautologia e completo)e da L. Levin in [16] (che ha provato la completezza di diversi linguaggi). La prova dell’NP-completezza di Clique, dei Grafi di Hamilton, della Programmazione Lineare Intera e di moltialtri e stata data da Karp [15]. Il libro di Garey e Johnson [8] e un’ottima guida alla teoriadell’NP-completezza.

Il risultato di NP-completezza di Max2SAT e apparso in [7].L’approccio a 3SAT presentato nella Sezione 8 puo essere esteso ed attualmente il migliore

algoritmo deterministico per 3SAT ha un tempo di esecuzione O(1.473n) (vedi [2]).Versione: 1.42 del 4 dicembre 2006.

CAPITOLO 2

Introduzione agli algoritmi probabilistici

1. Ripasso di probabilita discreta

Nello studio della probabilita consideriamo tipicamente un esperimento cui e naturalmenteassociato lo spazio S dei possibili risultati dell’esperimento. Ad ogni possibile risultato r eassociata la probabilita P (r) del risultato r. Ad esempio, l’esperimento puo essere il lancio diun dado a 6 faccie cui e associato lo spazio S = 1, 2, 3, 4, 5, 6 dei possibili risultati ciascunocon probabilita 1/6.

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

La probabilita di un evento puo essere calcolata a partire dalla probabilita dei singolirisultati usando 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 Bl’evento che il risultato 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 eP (A ∩B) = P (4, 6) = 1/3 abbiamo 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 lavariabile casuale X nel modo seguente: X = 1 se il risultato del dado e pari. In seguito,per una variabile casuale X ed un valore x, considereremo l’evento “X = x” come l’eventocorrispondente all’insieme di risultati 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 consideriamola variabile 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 variabilecasuale 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 ilcalcolo delle media di variabili causali con spazi dei risultati di grosse dimensioni.

25

26 2. INTRODUZIONE AGLI ALGORITMI PROBABILISTICI

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

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

La seconda proprieta invece da una stima della probabilita che una variabile casuale sidiscosti dalla sua media (vedi anche i Chernoff Bound in Sezione 5).

Teorema 2.4 (Diseguaglianza di Markov). Se X e una variabile casuale che assume valoriinteri non negativi allora per ogni t > 0

P (X ≥ t · E[X]) ≤ 1/t.

1.1. Balls and Bins. Applichiamo il Teorema 2.3, al seguente esempio. Si consideril’esperimento del lancio di m palline (balls) in n urne (bins) e vogliamo calcolare il numeromedio di urne vuote. Cioe, definita la variabile causale X che associa ad ogni risultato il numerodi urne vuote, vogliamo calcolare E[X]. Lo spazio dei risultati contiene nm punti e quindi,anche per valori piccoli di n e m, l’enumerazione di tutti i possibili risultati e praticamenteimpossibile. Definiamo quindi le seguenti n variabili casuali.

Xi =

1, se l’i-esima urna vuota;

0, altrimenti.

Notiamo un piccolo abuso di notazione commesso nel definire la variabile casuale Xi. Nellaprecedente sezione abbiamo definito una variabile casuale come una funzione che associa adogni possibile risultato una valore reale. Relativamente all’esperimento che stiamo studiandoun risultato e una funzione a che associa all’urna i l’insieme delle palline che sono state lanciatenell’i-esima urna. Quindi una definizione formalmente corretta sarebbe stata

Xi(a) =

1, se a(i) = ∅;0, altrimenti.

E facile vedere che X =∑n

i=1 Xi. Siccome

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

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

nm=

(

1− 1

n

)m

abbiamo che

E[Xi] = n

(

1− 1

n

)m

.

Alcuni casi speciali. Quando m = n abbiamo che

E[X] = n

(

1− 1

n

)n

∼ n

eper n→∞.

Se invece m = n lnn, abbiamo che

E[X] = n

(

1− 1

n

)n ln n

∼ ne− ln n = 1

e quindi in media restera vuota una sola urna.

1. RIPASSO DI PROBABILITA DISCRETA 27

1.2. Permutazioni casuali. In questa sezione studiamo le proprieta di una permutazionecasuale. Iniziamo col calcolare il numero atteso di punti fissi di una permutazione casuale πsu n interi 1, 2, · · · , n. Un punto fisso e un intero i tale che π(i) = i. Definiamo la variabilecasuale 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. Oraosserviamo che E[Xi] = P (Xi = 1) = P (π(i) = i) = 1/n e pertanto il numero medio, E[X], dipunti fissi di una permutazione casuale e 1 (indipendentemente dal valore di n!!!).

Un punto fisso e un ciclo di lunghezza 1. In generale una permutazione puo avere piu ciclidi lunghezze diverse. Calcoliamo la media della variabile casuale Y che conta il numero dicicli di una permutazione; precisamente, Y (π) e definito essere il numero di punti fissi dellapermutazione π. Definiamo, per 1 ≤ i ≤ n, la variabile casuale Yi(π) come l’inverso dellalunghezza del ciclo di π cui appartiene l’intero i. Ad esempio se

π =

(

1 2 3 4 5 6 72 1 7 3 4 5 6

)

abbiamo che Y1(π) = 1/2 e Y3(π) = 1/5. E facile verificare che Y (π) =∑n

i=1 Yi(π). Calcoliamo

quindi E[Yi] e, per fare cio, ricaviamo un’espressione per pk,idef= P (Yi = 1/k). In altre parole

pk,i e la probabilita che i appartenga ad un ciclo di lunghezza k. Questa probabilita puo esserescritta contando il numero di permutazioni π in cui i e in un ciclo di lunghezza k e dividendoquesto numero per n!. Se i appartiene ad un ciclo di lunghezza k di π allora esistono i1, · · · , ik−1

che sono distinti a coppie e distinti da i (numero di scelte: (n− 1) · (n− 2) · · · · · (n− k + 1))tali che

(1) π(i) = i1;(2) π(ij) = ij+1, per j = 2, · · · , k − 2;(3) π(ik−1) = i.

Poiche abbiamo fissato k degli n punti della permutazione abbiamo (n−k)! modi di permutarei restanti n− k elementi. Riassumendo abbiamo che

pk,i =(n− 1) · (n− 2) · · · · · (n− k + 1) · (n− k)!

n!=

1

n.

Quindi abbiamo che

E[Yi] =n∑

k=1

1

kP

(

Yi =1

k

)

=1

n

n∑

k=1

1

k

∼ 1

n(ln n + γ)

dove γ = 0.5772.... e la costante di Eulero. Pertanto possiamo dire che, quando n cresce, ilnumero di cicli di una permutazione casuale tende a ln n + γ.


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

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

Sia Xk il numero di archi che dobbiamo aggiungere al grafo per passare da k a k − 1componenti connesse. 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 eabbastanza difficile. Il prossimo lemma ci fornisce un limite superiore a E[Xk].

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

Dimostrazione. Supponiamo che G abbia esattamente k componenti connesse. Per unvertice v di G abbiamo che:

(1) esistono al piu n − 1 archi che sono adiacenti a v e che non sono stati scelti ancora;infatti il numero di archi adiacenti a v e n− 1 solo se v ha grado 0;

(2) esistono almeno k−1 archi che connettono v ad una componente connessa differente daquella cui appartiene v; infatti il numero di archi che connettono v ad una componentediversa e esattamente k− 1 solo se ogni componente (tranne quella cui appartiene v)ha esattamente un vertice.

Pertanto la probabilita che, scegliendo un arco non in E a caso, il numero di componenticonnesse si riduca e almeno k−1

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

venga scelto e al piu n−1k−1 .

Quindi abbiamo che

E[X] =n∑

k=2

E[Xk] ≤ (n− 1)

(

1 +1

2+

1

3+ · · ·+ 1

n− 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,quando i 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 grafoG = (V, E) e un sottoinsieme C di archi la cui rimozione disconnette il grafo. Il taglio dicardinalita minima puo essere calcolato in tempo polinomiale usando la ben nota relazione conil massimo flusso. Presentiamo un semplice algoritmo probabilistico per il calcolo del minimotaglio (vedi [14]).

L’algoritmo consiste di n − 2 fasi (n e il numero di vertici del grafo). In ciascuna fasel’algoritmo sceglie a caso una coppia (u, v) di vertici del grafo che sono connessi da almeno unarco. I vertici u e v sono rimossi dal grafo e sostituiti da un nuovo vertice w. Gli archi tra ue v sono rimossi dal grafo e gli archi tra u o v ed altri vertici avranno come estremo w. Piuprecisamente, se u e v avevano, rispettivamente, nu ed nv archi con il vertice x, il vertice w

3. ALGORITMO PROBABILISTICO PER 2SAT 29

avra nu +nv archi che raggiungono il vertice x. Alla fine di n− 2 passi, il grafo consiste di duesoli vertici, chiamiamoli s e t, e di un certo numero di archi paralleli tra s e t. Questi archicostituiscono un taglio che sconnette i vertici che sono stati fusi in s dai vertici che sono statifusi in t.

Osserviamo che l’algoritmo descritto costruisce un taglio di cardinalita minima solo se adogni passo non sceglie nessun arco del taglio e calcoliamo quindi questa probabilita. Denotiamocon Ei l’evento che al passo i-esimo dell’algoritmo viene scelto un arco non appartenente altaglio minimo. 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 equindi il grafo 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 tagliominimo e stato selezionato) il grafo Gi−1 ottenuto alla fine del passo (i− 1)-esimo, ha n− i+1vertici, taglio minimo di cardinalita k e pertanto almeno k(n−i+1)/2 archi. Pertanto abbiamoche 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−2i=1

(

n− i− 1

n− i + 1

)

=2

n(n− 1)≥ 2

n2.

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 probabilita che l’algoritmo non dia in output il taglio di cardinalita minima e al piu(1−2/n2)`. Ad esempio, la probabilita di errore puo essere ridotta a 1/e ripetendo l’algoritmon2/2 volte.

3. Algoritmo probabilistico per 2SAT

In questa sezione discutiamo un semplice algoritmo probabilistico per decidere se unaformula Φ in forma 2CNF e soddisfattibile. Ovviamente, sappiamo gia che 2SAT∈ P mal’algoritmo che presentiamo ora e molto semplice ed illustra la tecnica della costruzione dialgoritmi basati su cammini casuali. L’algoritmo e stato presentato in [18].

Consideriamo quindi l’algoritmo

Algoritmo RandomWalk(Φ)1. sia n il numero di variabili di Φ;2. sia t l’assegnamento che pone tutte le variabili uguale a vero;3. ripeti 2n2 volte4. se tutte le clausole sono soddisfatte da t5. dai in output “1” e termina;6. altrimenti scegli una qualsiasi clausola C non soddisfatta7. scegli uno dei letterali u di C a caso e modifica t in modo da rendere u vero;8. dai in output “0”;


Teorema 2.6. Se Φ non e soddisfattibile allora RandomWalk da sempre in output 0. SeΦ e soddisfattibile allora RandomWalk da in output 1 con probabilita almeno 1/2.

Dimostrazione. La prima parte del teorema e ovvia. Supponiamo ora che Φ sia soddi-sfattibile. Sia t un assegnamento di verita che soddisfa Φ calcoliamo `(i) il numero atteso diiterazione del ciclo 3 − 7 nel caso in cui t differisca per i variabili dall’assegnamento inizialet del passo 2. Ovviamente abbiamo che `(0) = 0. Supponiamo ora che t e t differiscono nelvalore di i > 0 variabili. Qualsiasi clausola C scegliamo al passo 6, t deve soddisfare almenouno dei due letterali di C. Pertanto con probabilita almeno 1/2 al passo 7 scegliamo il letteralegiusto (e quindi decrementiamo il numero di variabili in cui t e t differiscono) e con probabilitaal piu 1/2 scegliamo il letterale sbagliato (e quindi incrementiamo il numero di variabili in cuit e t differiscono). Possiamo quindi scrivere

`(i) ≤ 1

2(`(i− 1) + `(i + 1)) + 1.

Se invece t e t differiscono per tutte le variabili allora al passo 7 il numero di variabili per cuidifferiscono certamente diminuisce e quindi abbiamo

`(n) ≤ `(n− 1) + 1.

Definendo la funzione ˜(i) come

˜(i) =

0, if i = 0;12

(

˜(i− 1) + ˜(i + 1))

+ 1, if 0 < i < n;

˜(n− 1) + 1, if i = n.

abbiamo che ˜(i) ≥ `(i). Da queste equazioni abbiamo ˜(i) = 2in − i2 e quindi possiamoconcludere che per ogni i

`(i) ≤ ˜(i) ≤ ˜(n) = n2.

Quindi per la diseguaglianza di Markov la probabilita che dopo 2n2 iterazioni l’algoritmoRandomWalk non da in output un assegnamento che soddisfa Φ e al piu 1/2.

Estendere l’algoritmo RandomWalk al caso di 3SAT non sembra essere facile. Vediinfatti l’esempio dell’Esercizio 2.1.

4. Approssimazione per MaxSAT

In questo sezione discutiamo algoritmi di approssimazione per MaxSAT. L’esposizione ebasata su [9]. 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.

4.1. Il problema MaxSAT. Il problema MaxSAT consiste nel calcolare, avendo in inputuna formula in forma congiuntiva normale Φ = C1∧· · ·∧Cm sulle variabili x1, · · · , xn, il numeromassimo di clausole che possono essere simultaneamente soddisfatte da un assegnamento diverita. Indichiamo con I+

j l’insieme delle variabili che compaiono in forma non negata nella

clausola Cj e con I−j le variabili che compaiono in forma negata. Assumiamo inoltre che ogniclausola contenga almeno due letterali. Ovviamente il problema e NP-Hard.

5. CHERNOFF BOUND 31

4.2. Esiste sempre un assegnamento buono. Supponiamo di scegliere un assegna-mento casuale assegnando alla variabile xi il valore VERO con probabilita 1/2. E facile vedereche la probabilita che una clausola con k letterali sia soddisfatta e 1− 2−k. Definiamo quindila 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 Φ soddisfatteda un assegnamento 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 e possiamo quindi concludere che esiste sempre un assegnamento che soddisfa almeno 3/4delle clausole.

4.3. Cerchiamo un assegnamento buono. In questa sezione mostriamo come riuscia-mo a trovare un assegnamento che soddisfi almeno 3/4m delle m clausole della formula Φ.Poiche l’assegnamento che soddisfa il maggior numero di clausole non ne soddisfa piu di m,abbiamo un algoritmo che 3/4-approssima il problema MaxSAT.

Calcoliamo un assegnamento una variabile per volta partendo da x1. Consideriamo leformule Φ(x1 = 1) e Φ(x1 = 0) ottenendo ponendo x1 = 1 e x1 = 0 nella formula Φ. Assegnamoquindi alla variabile x1 il valore b che massimizza E(Φ(x1 = b)). Osserviamo che siccomeE(Φ) = 1

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

5. 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 Xdef=∑n

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

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

Teorema 2.7 (Chernoff Bound). Siano X1, · · · , Xn variabili causali indipendenti tali chePr[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−∆−(µ, ε))µ] < ε.

5.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 casuale

X =∑100

i=1 Xi conta il numero di teste in 100 lanci e abbiamo che µ = E[X] = 50. Usando ilChernoff bound possiamo calcolare un upper bound alla probabilita che in 100 lanci esca testaper piu di un dato numero x di volte.

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

Pr[X > 60] <

[

e.2

1.21.2

]50

≈[

1.221

1.244

]50

≈ 0.393.


Pr[X > 70] <

[

e.4

1.41.4

]50

≈[

1.491

1.601

]50

≈ 0.028.


Pr[X > 80] <

[

e.6

1.61.6

]50

≈[

1.822

2.121

]50

≈ 0.0005.

5.2. Permutation Routing in un Ipercubo. In questa sezione discutiamo un proble-ma per cui esiste un algoritmo probabilistico che e provatamente migliore di ogni algoritmodeterministico. L’analisi dell’algoritmo utilizza i Chernoff Bound.

Consideriamo una rete di comunicazione modellato mediante un grafo con N nodi. Ogninodo i contiene inizialmente un pacchetto vi che deve essere recapitato alla destinazione di.Ad ogni passo un nodo puo inviare un pacchetto a ciascuno dei suoi vicini. Consideriamoil caso, denominato permutation routing, in cui ogni nodo deve inviare un pacchetto ed ogninodo e destinatario di esattamente un pacchetto e ci restringiamo ad una classe di algoritmiparticolarmente semplici da implementare denominati algoritmi oblivious. Un algoritmo per ilpermutation routing consiste nell’assegnamento di una rotta (sequenza di archi) che il pacchettodeve seguire dall’origine alla destinazione. In un algoritmo oblivious la rotta seguito da unpacchetto dipende solo dalla sua origine e dall asua destinazione. E possibile che ad un certopunto, diversi pacchetti desiderano attraversare uno stesso arco. In questo caso uno solo deipacchetti sara instradato e gli altri pacchetti saranno memorizzati in una coda e consideratial prossimo passo. Per l’analisi dell’algoritmo che presenteremo e ininfluente quale pacchetto

5. CHERNOFF BOUND 33

e scelto ad ogni passo ma e importante che, se esistono pacchetti pronti per un arco, ne vengaspedito 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 gradomassimo d, 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 nodiciascuno identificato da una diversa sequenza di n bit. I nodi (a1, · · · , an) e (b1, · · · , bn) sonoadiacenti se differiscono in esattamente una posizione. Quindi ogni nodo dell’ipercubo hagrado n = log2 N . Come consequenza del Teorema 2.8, ogni algoritmo deterministico per

permutation routing sull’ipercubo prende tempo Ω(√

N/n) passi.

Esempio 2.9. Consideriamo il seguente semplice algoritmo oblivious denominato bit fi-xing. La rotta seguita da un pacchetto che deve andare da a = (a1, · · · , an) a b = (b1, · · · , bn)e calcolata considerando 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 con-siste di al piu n archi. Osserviamo che se per qualche i abbiamo ai = bi allora i vertici(b1, b2, · · · , bi−1, ai, · · · , an) e (b1, b2, · · · , bi−1, bi, · · · , an) coincidono.

5.3. Routing probabilistico. In questa sezione consideriamo il seguente algoritmo obli-vious probabilistico.

Fase I: Ogni nodo i sceglie un destinazione intermedia a caso si e il paccheto vi einstradato da 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 separanonon avranno altri archi in comune.

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

Dimostrazione. Mostreremo che per ogni passo in cui vi viene ritardato, esiste un pac-chetto di S che e inviato per l’ultima volta lungo un arco di ρi. Cio prova immediatamenteche 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 suoritardo e t− j. Inizialmente il ritardo di vi e 0.

Osserviamo che quando il ritardo di vi passa da ` a `+1, deve esistere almeno un pacchettovj ∈ S desidera attraversare lo stesso arco di vi allo stesso istante. Il pacchetto vj ha quindiritardo `.

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


Definiamo la variabile casuale Hij essere 1 se le rotte di vi e vj condividono almeno un arcoe 0 altrimenti. 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 Chenoffbound. Calcoliamo quindi un bound su E[H].

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

(1) Hi ≤∑

e∈ρi

T (e).

Ovviamente, per ragioni di simmetria dell’ipercubo, abbiamo che, per ogni coppia di archi eed e′, E[T (e)] = E[T (e′)]. Inoltre la lunghezza media di una rotta e n/2 e quindi la lunghezzamedia di tutte le rotte e Nn/2. Poiche l’ipercubo ha Nn archi, abbiamo che E[T (e)] = 1/2.Sostituendo in 1 ed 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 piu2−6n. Poiche il numero di pacchetti e N = 2n, la probabilita che esista un pacchetto vi cheimpieghi piu di 6n passi per raggiungere la sua destinazione intermedia e al piu 2−5n. Glistessi argomenti possono essere usati per provare che anche la seconda fase impiega tempo alpiu 2−5n e quindi possiamo dire che con probabilita almeno 1 − 1/N l’algoritmo termina in12n passi.

Abbiamo in definitiva il seguente teorema.

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

5.4. Nota bibliografica. Queste note seguono l’esposizione data in [17]. L’algoritmoprobabilistico per il routing su ipercubo e stato proposto da Valiant in [20]. Il lower boundenunciato dal Teorema 2.8 appare in [13] e migliora un precedente bound di [1].

6. Verifica probabilistica

In questo capitolo discutiamo algoritmi probabilistici per la verifica. L’esposizione segue[17]. La tecnica esposta nella prima sezione per verificare il prodotto di due matrici e daattribuirsi a Freivalds [6].

6.1. Verifica di prodotto di matrici. Supponiamo di avere due matrici A e B di di-mensioni n × n le cui entry sono prese da un campo finito F . Esistono diversi algoritmi peril calcolo del prodotto di A e B: l’algoritmo che deriva direttamente dalla definizione impie-ga tempo O(n3) mentre l’algoritmo piu veloce asintoticamente noto impiega tempo O(n2.376)(vedi [4]) ed e estremamente difficile da implementare. Supponiamo di voler verificare che unadata implementazione dell’algoritmo veloce ha calcolato correttamente il prodotto di A e B.Ovviamente potremo calcolare il prodotto di A e B usando l’algoritmo naive che prende tem-po O(n3) ma in questo caso perdiamo i benefici dell’aver usato l’algoritmo veloce. Vogliamoquindi un algoritmo che riceve in input A, B e C (il prodotto calcolato 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:

6. VERIFICA PROBABILISTICA 35

1. se C = A ·B, allora R su input A, B e C da in output 1 (ad indicare che nessun erroree 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 esserecalcolato in tempo O(n2) e l’uguaglianza di due vettori (passo 5) puo essere verificata intempo O(n). Pertanto l’algortimo R prende tempo O(n2). Proviamo ora che l’algoritmo Rgode delle proprieta 1 e 2.

Prova Prop. 1. Se C = A · B allora y = Ax = ABr = Cr = z e quindi l’algoritmo R dasempre in output 1.

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

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

Supponiamo senza perdita di generalita che le prime k > 0 entry della prima riga di Dsiano non nulle. Se Dr = 0 necessariamente il prodotto dT r tra la prima riga d di D ed ilvettore r deve essere nullo. 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.

6.2. Verifica di identita tra polinomi.

Teorema 2.13 (Schwartz [19]). Sia Q(x1, · · · , xn) ∈ F [x1, · · · , xn] un polinomio in nvariabili con coefficienti in F di grado d. Si fissi un insieme S ⊆ F e siano r1, · · · , rn sceltiindipendentemente ed 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. Da

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

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 identicamentenullo, sappiamo che Q ha al piu d zeri. Quindi se r e scelto dall’insieme S, la probabilita cheQ(r) = 0 e al piu d/|S|.

Consideriamo ora il polinomio Q(x1, · · · , xn) di grado d. Mettendo in evidenza la variabilex1 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 identicamentenullo ed 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 unavariabile

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) = 0e al piu k/|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.

7. Esercizi

Esercizio 2.1. Consideriamo la formula Φ che contiene le clausole (¬xi) per i = 1, · · · , ne le clausole (¬xi ∨ xj ∨ xk) per tutte le triple di 1 ≤ i, j, k ≤ n. La formula Φ e ovviamentesoddisfatta dall’assegnamento che pone tutte le variabili a falso (e questo e anche l’unico as-segnamento che soddisfa Φ). Riesci a dare un limite superiore al numero di volte che bisognaiterare il passo dell’algoritmo RandomWalk per avere una buona probabilita di successo?

7. ESERCIZI 37

Esercizio 2.2. Calcolare la probabilita che l’algoritmo per il calcolo del min cut di Sezio-ne 2.1 dia in output un min cut nel caso in cui l’input e

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

Esercizio 2.3. Consideriamo l’algoritmo R per la verifica del prodotto di due matrici.Cosa possiamo dire se al passo 01 scegliamo r come r ← 0, 1, 2n?

Versione: 1.21 del 9 dicembre 2006.

CAPITOLO 3

Algoritmi di Approssimazione

1. Problemi di Ottimizzazione

Iniziamo con il definire un problema di approssimazione.

Definizione 3.1. Un problema di ottimizzazione Π e una quadrupla Π = (I,S, µ, Goal)where

(1) I e un insieme di istanze;(2) per ogni istanza I, S(I) e l’insieme delle soluzioni ammissibili per I;(3) per ogni soluzione ammissibile S dell’istanza I, µ(I, S) e la misura della soluzione S.(4) Goal∈ min,MAX.

Definiamo inoltre, per un’istanza I, Opt(I) nel modo seguente

Opt(I) = GoalS∈S(I)µ(I, S).

Se Goal=min diciamo che Π e un problema di minimizzazione e la misura µ di una soluzioneammissible S e anche chiamata costo di S ed indicato con cost(I, S). Se invece Goal=MAX

diciamo che Π e un problema di massimizzazione e la misura µ di una soluzione ammissible Se anche chiamata valore di S ed e indicato con val(I, S).

Diciamo che un algoritmo A risolve un problema di ottimizzazione Π se, per ogni istanzaI di Π, A(I) e una soluzione ammissibile per I ed inoltre

µ(I, A(I)) = Opt(I).

In queste note studieremo algoritmi che approssimano problemi di ottimizzazione nel senso chedanno in output soluzioni ammissibili la cui misura non si discosta troppo da Opt.

Definizione 3.2 (Min). Sia Π un problema di minimizazzione. L’algoritmo A k-approssimaΠ se per ogni istanza I di Π

(1) A(I) ∈ S(I);(2) cost(I, A(I)) ≤ k ·Opt(I).

Definizione 3.3 (Max). Sia Π un problema di massimizazzione. L’algoritmo A k-approssimaΠ se per ogni istanza I di Π

(1) A(I) ∈ S(I);

(2) val(I, A(I)) ≥ Opt(I)k

.

1.1. Problemi di decisione e di ottimizzazione. Nella prima parte abbiamo studiatola complessita computazionale id problemi di decisione in cui il compito dell’algoritmo e di deci-dere se l’input x appartiene al linguaggio L. Un problema di minimizzazione Π = (I,S, µ, min)

39

40 3. ALGORITMI DI APPROSSIMAZIONE

puo essere naturalmente associato ad un problema di decisione LΠ definito nel modo seguente

LΠ = (I, k) : ∃S ∈ S(I) tale che µ(S) ≤ k.Una simile definizione puo essere data per problemi di massimizzazione. Il seguente teorema eimmediato.

Teorema 3.4. Sia Π un problema di ottimizzazione per cui e possibile decidere in tempopolinomiale se una soluzione S e ammissibile per un’istanza I e la funzione µ e calcolabile intempo polinomiale. Allora LΠ ∈ NP.

In queste note studieremo algoritmi di approssimazione per problemi di ottimizzazione Πil cui associato linguaggio LΠ e NP− COMPLETE. Abbiamo il seguente teorema.

Teorema 3.5. Sia Π un problema di ottimizzazione per cui LΠ ∈ NP−COMPLETE e percui esiste un algoritmo polinomiale che risolve Π. Allora P = NP.

2. Vertex cover

In questo capitolo analiziamo la performance di alcuni algoritmi per il problema del vertexcover. Come vedremo nessuno di questi algoritmi riesce ad approssimare il problema del vertexcover a meno di 2. Un algoritmo che ottiene esattamente 2 puo essere trovato in [5].

2.1. Definizione del problema. Il problema di ottimizzazione Vertex Cover e cosi defi-nito.

Istanze: Un’istanza del problema del vertex cover e costituita da un grafo non direttoG = (V, E).

Soluzioni Ammissibili: Un soluzione ammissibile per G = (V, E) e un sottoinsiemeC ⊆ V dei vertici tali che per ogni arco (u, v) ∈ E abbiamo che u ∈ C oppure v ∈ C.

Misura di una soluzione ammissibile.: La misura di una soluzione ammissibile C ela sua cardinalita |C|.

Goal: Minimizzare.

In altre parole il problema di ottimizzazione del vertex cover consiste nel coprire tutti gli archidi G usando il minor numero possibile di vertici.

2.2. Un algoritmo 2 approssimato. Vedi [5].

2.3. Algoritmo greedy. Consideriamo il seguente algoritmo.

Greedy(G)01. A← ∅;02. while E 6= ∅ do03. Scegli arbitrariamente un vertice v di G che ha almeno un arco;04. A← A ∪ v;05. E ← E \ e ∈ E|e = (u, v) per qualche vertice u;06. end ;07. return A;

2. VERTEX COVER 41

E facile convincersi che l’algortimo Greedy restituisce sempre un vertex cover di G.Mostriamo ora che esiste un grafo di n vertici ed una scelta dei vertici al passo 03. per cui

l’algoritmo Greedy calcola un vertex cover di cardinalita Ω(n) volte il vertex cover ottimo.Consideriamo il grafo stella Sn con n vertici; l’insieme di vertici di Sn consiste dei vertici(v, u1, · · · , un−1) e Sn contiene gli archi (v, ui) per i = 1, · · · , n− 1. Se al passo 03 sono scelti ivertici u1, · · · , un−1, l’algoritmo Greedy restituisce un vertex cover di cardinalita n−1 mentreil vertice v da solo costituisce un vertex cover.

2.4. Analisi dell’euristica del prof. Nixon. Questa sezione presenta una differenteeuristica per il calcolo del vertex cover. L’euristica e attribuita (scherzosamente) a tale professorNixon da [5]. Risponderemo ad un quesito di [5] che chiede un esempio in cui l’euristicadi Nixon costruisce un vertex cover di taglia maggiore del doppio del vertex cover ottimo.Mostreremo poi un altro esempio in cui l’euristica del professor Nixon restituisce un vertexcover di taglia Ω(log n) volte il vertex cover ottimo.

Il professor Nixon propone la seguente euristica per approssimare il problem del vertexcover su un grafo G = (V, E).

Nixon(G = (V, E))1. A = ∅;2. while E 6= ∅3. sia u vertice di grado massimo in (V, E);4. E ← E \ archi incidenti a u;5. V = V \ u;6. A = A ∪ u;7. endwhile;8. return A;

Primo controesempio. Mostreremo ora un grafo G su cui l’algoritmo Nixon restituisceun vertex cover di taglia maggiore del doppio dell’ottimo. Quindi l’algoritmo Nixon ha unagaranzia di approssimazione peggiore dell’algoritmo presentato a lezione.

Il grafo G = (V1 ∪ V2, E) e un grafo bipartito. L’insieme V1 consiste di 8 vertici v1, · · · , v8

di grado 6. L’insieme V2 e l’unione (disgiunta) di 4 insiemi: A, B, C e D. L’insieme A consistedi 3 vertici a1, a2, a3 di grado 8, l’insieme B consiste di 2 vertici b1, b2 di grado 4, l’insieme Cconsiste di 4 vertici c1, c2, c3, c4 di grado 2, l’insieme D consiste di 8 vertici d1, · · · , d8 di grado1.

Gli archi di G sono come segue:

(1) ogni vertice di V1 ha un arco ad ogni vertice di A;(2) vertici v1, · · · , v4 hanno ciascuno un arco incidente a b1; vertici v5, · · · , v8 invece hanno

ciascuno un arco incidente a b2;(3) vertici v1 e v2 hanno un arco a c1; vertici v3 e v4 hanno un arco a c2; vertici v5 e v6

hanno un arco a c3; vertici v7 e v8 hanno un arco a c4.(4) per i = 1, · · · , 8 il vertice vi ha una arco a di.

L’algoritmo Nixon sceglie i vertici nel modo seguente.

(1) i 3 vertici di A che hanno grado 8 mentre gli atri vertici hanno tutti grado al piu 6.Dopo l’eliminazione dei vertici di A, i vertici di V1 hanno grado 6− 3 = 3;


(2) i 2 vertici di B che hanno grado 4 mentre tutti gli altri hanno grado al piu 3. Dopol’eliminazione dei vertici di B, i vertici di V1 hanno grado 2;

(3) i 4 vertici di C che hanno grado 2. Tutti gli altri vertici ancora presenti nel grafohanno o grado 2 (i vertici di V1) o grado 1 (i vertici di D);

(4) a questo punto il grafo consiste di 8 coppie di vertici di grado 1; l’algoritmo perterminare ne sceglie 8;

Quindi l’algoritmo Nixon restituisce un vertex cover di cardinalita 17. E facile convincersi chegli 8 vertici di V1 costituiscono un vertex cover.

Secondo controesempio. Consideriamo il grafo bipartito B(L, R, E). L’insieme L consistedi r vertici. L’insieme R e suddiviso in r insiemi R1, · · · , Rr. Ogni vertice in Ri ha un arcoverso i vertici di L e due vertici di Ri non hanno archi verso lo stesso vertice di L. Pertantol’insieme Ri contiene br/ic vertici. L’insieme R ha quindi

r∑

i=1

br/ic = Θ(r log r)

vertici. Il numero di vertice n e Θ(r log r).Se l’algoritmo Greedy considera i vertici di R a partire dai vertici di Rr fino a i vertici di

R1, il cover calcolato coincide con R ed ha cardinalita Θ(r log r). Osserviamo invece che L eun cover ed ha cardinalita r. Quindi |R|/|L| = Ω(log r) = Ω(log n).

3. MaxCut

Il problema MaxCut e definito come segue.

Istanze: Un’istanza del problema MaxCut e costituita da un grafo non diretto G =(V, E).

Soluzioni Ammissibili: Un soluzione ammissibile per G = (V, E) e una partizione diV in due sottoinsiemi S1 e S2 tali che S1 ∪ S2 = V e S1 ∩ S2 = ∅.

Misura di una soluzione ammissibile: La misura di una soluzione ammissibile c(S1, S2)e il numero di archi che hanno un estremo in S1 e l’altro in S2.

Goal: Massimizzare.

Osserviamo che il problema di minimizzazione e risolvibile in tempo polinomiale.L’algoritmo che presentiamo consiste nel partire da una qualsiasi partizione S1 ed S2 e

controllare se esiste un vertice x ∈ S1 tale che c(S1 \ x, S2 ∪ x) > c(S1, S2) nel qual casosi aggiorna la soluzione corrente a (S1 \ x, S2 ∪ x) oppure se esiste un vertice x ∈ S2

tale che c(S1 ∪ x, S2 \ x) > c(S1, S2). nel qual caso si aggiorna la soluzione corrente a(S1 ∪ x, S2 \ x). Se invece nessun vertice esiste x l’algoritmo si ferma e da in output lasoluzione corrente (S1, S2).

Abbiamo il seguente teorema.

Teorema 3.6. Esiste un algoritmo polinomiale che 2-approssima MaxCut.

Dimostrazione. Osserviamo che per ogni (S1, S2) abbiamo che c(S1, S2) ≤ |E| e poichead ogni iterazione il valore di c(S1, S2) e incrementato di almeno 1 l’algoritmo effettua al piu|E| iterazioni ed e pertanto polinomiale.

6. MaxSAT 43

Osserviamo che nella soluzione data in output dall’algoritmo per ogni vertice x almenometa dei suoi vicini appartengono all’altro sottoinsieme. Pertanto, se denotiamo con dx ilgrado del vertice x, abbiamo che

2 · c(S1, S2) ≥∑

x

dx

2

= |E|Il teorema segue dall’osservazione che Opt ≤ |E|.

4. Set cover

Vedi [5].

5. TSP

5.1. Definizione. Vedi [5].

5.2. Approssimabilita del caso generale. Vedi [5].

5.3. Algoritmo 2 approssimato per il caso euclideo. Vedi [5].

5.4. Algoritmo 3/2 approssimato per il caso euclideo.

6. MaxSAT

In questo capitolo discutiamo algoritmi di approssimazione per MaxSat. L’esposizione ebasata su [9].

6.1. Ripasso di calcolo delle probabilita. Useremo la seguente proprieta della mediadi una variabile casuale

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

6.2. Definizione. Il problema MaxSAT consiste nel calcolare, avendo in input una for-mula Φ in forma congiuntiva normale Φ = C1 ∧ · · · ∧ Cm sulle variabili x1, · · · , xn, il numeromassimo di clausole che possono essere simultaneamente soddisfatte da un assegnamento diverita. Ovviamente se esiste un algoritmo che risolve MaxSAT allora P=NP.

6.3. Esiste sempre un assegnamento buono. Supponiamo di scegliere un assegna-mento casuale assegnando alla variabile xi il valore VERO con probabilita 1/2. E facile vedere

che la probabilita che una clausola con k letterali sia soddisfatta e αkdef=1 − 2−k. Definiamo

quindi la variabile casuale XΦ come la variabile casuale che conta il numero di clausole di Φ sod-disfatte da un assegnamento casuale. Definiamo inoltre la variabile casuale XΦ

i , i = 1, · · · , m,nel modo seguente

XΦi =

1, se Ci soddisfatta;

0, altrimenti;


ed abbiamo che E[XΦi ] = αk. Quindi il numero medio E(XΦ) di clausole di Φ soddisfatte da

un assegnamento casuale e dato da

E

[

m∑

i=1

XΦi

]

=∑

l

αlml

ove ml denota il numero di clausole con l letterali. Poiche αl ≥ 1/2 possiamo concludere che ilnumero medio di clausole soddisfatte e almeno m/2 e quindi, per la proprieta della media nelParagrafo 6.1, esiste sempre un assegnamento di verita che soddisfa almeno meta delle clausole.

Notiamo che la qualita dell’approssimazione cresce con il numero di letterali che compaionoin una clausola. Se ogni clausola ha almeno due letterali abbiamo che per l ≥ 2, αl ≥ 3/4 epossiamo quindi concludere che esiste sempre un assegnamento che soddisfa almeno 3/4 delleclausole. Se tutte le clausole invece hanno almeno 3 letterali allora possiamo concludere cheesiste almemo un assegnamento che soddisfa almeno 7/8 delle clausole.

6.4. Cerchiamo un assegnamento buono. In questa sezione mostriamo come riuscia-mo a trovare un assegnamento che soddisfi almeno 1/2m delle m clausole della formula Φ.Poiche l’assegnamento che soddisfa il maggior numero di clausole non ne soddisfa piu di m,abbiamo un algoritmo che 1/2-approssima MaxSAT.

Calcoliamo un assegnamento una variabile per volta partendo da x1 usando il metododelle medie condizionate. Consideriamo le formule Φ(x1 = 1) e Φ(x1 = 0) ottenendo ponendox1 = 1 e x1 = 0 nella formula Φ. Assegnamo quindi alla variabile x1 il valore b che massimizzaE(XΦ|x1 = b). Osserviamo che siccome E(XΦ) = 1

2(E(XΦ|x1 = 1) + E(XΦ|x1 = 0) e poiche

E(XΦ) ≥ 1/2 abbiamo che E(XΦ|x1 = b) ≥ 1/2. Il valore di x2 e determinato allo stessomodo considerando la formula Φ(x1 = b) invece che la formula Φ e cosı via.


Teorema 3.7. Esiste un algoritmo polinomiale che 1/2 approssima MaxSAT.

6.5. Programmazione lineare. MaxSAT puo essere formulato come il seguente pro-blema di programmazione lineare intera.

max W =∑m

j=1 zj

con vincoli∑

i∈I+j

yi +∑

i∈I−j(1− yi) ≥ zj j = 1, · · · , m

yi ∈ 0, 1 i = 1, · · · , n0 ≤ zj ≤ 1 j = 1, · · · , m

dove abbiamo indicato con I+j l’insieme delle variabili che compaiono in forma non negata nella

clausola Cj e con I−j le variabili che compaiono in forma negata. Per ogni assegnamento di

verita (x1, · · · , xn) alle variabili della formula Φ il problema ha come valore massimo il numerodelle clausole soddisfatte. Infatti la soluzione che assegna a yi il valore di verita della varibailexi e a zj assegna 1 se la j-esima clausola e soddisfatta e 0 altrimenti e ammissibile ed ottima.

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

L il valore del problema che siottiene rilassando il vincolo di interezza sulle variabili yi. Ovviamente, Z?

L ≥ Z?I = Opt.

Consideriamo quindi il seguente semplice algoritmo

Passo 1.: Risolvere il problema rilassato ottendo soluzione (y?, z?).

6. MaxSAT 45

Passo 2.: Applicare il metodo della sezione precedente usando y∗i come probabilita di

porre a VERO la variabile xi.

Lemma 3.8. Se per una la soluzione ottima (y∗, z∗) al problema lineare rilassato vale cheper ogni clausola Cj

1−Πi∈I+j(1− y?

i ) ·Πi∈I−jy?

i ≥ αz?j

alloraE[XΦ] ≥ αZ?

I .

Dimostrazione. Abbiamo che E[XΦ] =∑m

j=1 Pr(zj = 1). La variabile zj ha valore 0 see solo se tutte le varibaili che compaiono nella j-esima clausola in forma non negata hannovalore falso (evento con probabilita Πi∈I+

j(1− y?

i )) e tutti le variabile che compaiono in forma

negata hanno valore vero (evento con probabilita Πi∈I−jy?

i ). Pertanto abbiamo che

E[XΦ] =m∑

j=1

(

Πi∈I+j(1− y?

i ) ·Πi∈I−jy?

i

)

≥m∑

j=1

αz∗j = αZ?L ≥ αZ?

I .

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

a1 + a2 + · · ·+ ak

k≥ k√

a1 · · · ak.

Lemma 3.9. Per ogni soluzione ammissibile (y, z) del problema lineare rilassato e per ogniclausola Cj con k letterali abbiamo

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

yi ≥ βkzj

con

βk = 1−(

1− 1

k

)k

.

Dimostrazione. Supponiamo che la clausola Cj contenga solo letterali in forma non ne-gata. Se xi appare in forma negata in Cj allora basta sostituire xi con xi e viceversa in tutte leclausole della formula e yi con 1−yi ed ottenere una formula ed un problema lineare equivalenti.Inoltre possiamo assumere che la clausola Cj contenga le variabile x1, · · · , xk.

Se (y, z) e una soluzione ammissibile allora il problema lineare comprende il vincolo∑k

i=1 yi ≥zj . Quindi

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

(

∑ki=1(1− yi)

k

)k

= 1−(

1−∑k

i=1 yi

k

)k

≥ 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 .


Teorema 3.10. Esiste un algoritmo che 1− 1e≈ .63099... approssima MaxSAT.

Dimostrazione. Per il Lemma 3.8 e il Lemma 3.9 abbiamo che se la formula contiene clau-sole ciascuna con almeno k letterali allora esiste un assegnamento che soddisfa almeno βkOpt

clausole. Poiche per ogni k abbiamo che βk < 1− 1e

per ogni formula esiste un assegnamento

che soddisfa almeno (1− 1e)Opt clausole. Usando il metodo delle medie condizionate possiamo

in tempo polinomiale calcolare un assegnamento che soddisfa (1− 1e)Opt clausole.

6.6. Un algoritmo 3/4-approssimato. Combiniamo i due algoritmi nel modo seguente.Scegliamo b ← 0, 1 a caso. Se b = 0 eseguiamo l’algoritmo del Teorema 3.7. Se b = 1eseguiamo l’algoritmo del Teorema 3.10.

Calcoliamo per la clausola Cj che ha kj letterali la probabilita pj che Cj sia soddisfatta.Denotiamo con (y?, z?) la soluzione ottima al problema di programmazione lineare. Sappiamoche se b = 0 allora la probabilita che Cj sia soddisfatta e αkj

≥ αkjz?j (poiche z?

j ≤ 1). Seinvece b = 1 allora la probabilita che Cj sia soddisfatta e βkj

z?j . Quindi

E[XΦ] ≥m∑

j=1

αkj+ βkj

2z?j

e siccome αk + βk ≥ 3/2 per ogni k abbiamo che E[XΦ] ≥ 3/4z?j . Questo dimostra che esiste

un assegnamento che soddisfa almeno 3/4m clausole.Consideriamo quindi il seguente algoritmo: calcoliamo assegnamenti t1 e t2 usando rispet-

tivamente l’algoritmo 1/2 approssimato e l’algoritmo 1 − 1e

approssimato. Diamo in outputl’assegnamento ta con a ∈ 1, 2 che soddisfa il maggior numero di clausole. Siccome sappiamoche se scegliamo uno dei due assegnamenti a caso sono soddisfatte in media 3/4m clausole,allora ta soddisfa almeno 3/4m clausole.

7. Vertex Cover pesato

Il problema del vertex cover pesato e definito nel modo seguente. Un’istanza consiste diun grafo G = (V, E) in cui ad ogni vertice v e associato un peso w(v) > 0. Una soluzioneammissibile e un sottoinsieme S ⊆ V dei vertici tale che per ogni arco (u, v) ∈ E uno tra u ev appartiene ad S. Il costo di una soluzione S e la somma

∑

v∈S w(v) dei pesi dei vertici diS. L’obiettivo e di minimizzare il costo. Questo problema puo essere scritto sotto forma diproblema di programmazione lineare intera nel modo seguente.

min∑

v∈V x(v) · w(v)con vincoli

x(u) + x(v) ≥ 1 ∀(u, v) ∈ Ex(v) ∈ 0, 1 ∀v ∈ V

8. ZAINO 0/1 47

Denotiamo con Opt(G, w) il valore dell’ottimo del problema di programmazione lineare interaper l’istanza (G, w) e con L(G, w) il valore del problema di programmazione lineare ottenutorilassando il vincolo di interezza x(v) ∈ 0, 1 al vincolo 0 ≤ x(v) ≤ 1 e sia x? una soluzioneche ottiene L(G, w). Partendo da x? costruiamo il vettore x nel modo seguente

x(v) =

1, se x?(v) ≥ 1/2;

0, altrimenti;

e sia S l’insieme dei vertici v per cui x(v) = 1. Osserviamo che S e una soluzione ammissibile.Infatti siccome x? e una soluzione ammissibile abbiamo che per ogni arco (u, v) abbiamox?(u) + x?(v) ≥ 1 e quindi o x?(u) ≥ 1/2 (e quindi x(u) = 1) oppure x?(v) ≥ 1/2 (e quindix(v) = 1).

Calcoliamo il peso di S.∑

u∈V

x(u)w(u) ≤∑

u∈V

2x?(u)w(u) = 2L(G, w) ≤ 2Opt(G, w).

Quindi abbiamo il seguente teorema.

Teorema 3.11. Esiste un algoritmo polinomiale 2-approssimante per il problema del vertexcover pesato.

8. Zaino 0/1

Un’istanza I del problema dello zaino 0/1 e costituita da n oggetti e da una capacita mas-sima B. L’i-esimo oggetto ha peso (volume) ci e valore (prezzo) vi. Lo scopo e di individuareil sottoinsieme di prezzo massimo tra quelli che hanno volume complessivo non maggiore di B.

Formalmente, una soluzione ammissibile per un’istanza I = ((v1, · · · , vn), (c1, · · · , cn), B)e costituita da una sequenza S = (b1, · · · , bn) ∈ 0, 1n tale che

n∑

i=1

bi · ci ≤ B.

Il nostro compito e quello di trovare, tra tutte le soluzioni ammissibili per un’istanza I, unasoluzione S∗ = (b∗1, · · · , b∗n) che massimizzi il profitto V al(S∗, I) di S∗ definito come

V al(S∗, I) =

n∑

i=1

b∗i · vi.

8.1. Hardness dell’approssimazione. In questa sezione proviamo che, se P 6= NP, nes-sun algoritmo polinomiale A puo risolvere il problema dello zaino garantendo un’approssima-zione assoluta costante; cioe tale che per una costante k e per ogni istanza I, Opt(I)−A(I) ≤k.

Teorema 3.12. Se P 6= NP allora per ogni costante k, nessun algoritmo polinomiale Apuo risolvere il problema dello zaino garantendo Opt(I)−A(I) ≤ k.

Dimostrazione. Supponiamo per assurdo che l’algoritmo polinomiale A sia tale che, perogni istanza I, Opt(I)− A(I) ≤ k. Costruiamo un altro algoritmo A′ che risolve il problemadello zaino in tempo polinomiale, contradicendo l’ipotesi che P 6= NP.


L’algoritmo A′ riceve in input un istanza I = ((v1, · · · , vn), (c1, · · · , cn), B) e costruiscel’istanza I ′ = (((k + 1)v1, · · · , (k + 1)vn), (c1, · · · , cn), B). Notiamo che, non avendo variatoi pesi ci e la capacita B dello zaino, l’insieme delle soluzioni ammissibili delle due istanzecoincidono. L’algoritmo A′ esegue l’algoritmo A sull’istanza I ′ ottenendo una soluzione S.Notiamo che V al(S, I ′) = (k + 1)V al(S, I) e Opt(I ′) = (k + 1)Opt(I). Inoltre per ipotesi valeche Opt(I ′)− V al(S, I ′) ≤ k. Quindi

Opt(I)− C(S, I) ≤ k

k + 1.

Poiche Opt(I) e V al(S, I) sono interi e poiche kk+1 < 1, abbiamo che

Opt(I)− V al(S, I) = 0

e quindi S e una soluzione ottima per I.

8.2. Algoritmo pseudopolinomiale. Data un’istanza I = ((v1, · · · , vn), (c1, · · · , cn), B)denotiamo con C(j, v) il piu piccolo valore b per cui l’istanza ((v1, · · · , vj), (c1, · · · , cj), b) havalore ottimo almeno v. Abbiamo

C(j, v) = 0, v ≤ 0 e j = 0, 1, · · · , n,

C(0, v) = +∞ per v > 0,

eC(j, v) = minC(j − 1, v − vj) + cj , C(j − 1, v).

La tabella C viene calcolata (ogni entry prende tempo O(1)) per ottenere il massimo v tale

che C(n, v) ≤ B. Poiche vale che Opt(I) ≤ ∑ vi

=def V ?, calcoliamo le entri di C(j, v) con

v = 0, · · · , V ?. L’algoritmo quindi prende tempo O(nV ?). Notiamo che quindi l’algoritmo none polinomiale.

8.3. Uno schema di approssimazione. Data un’istanza I = ((v1, · · · , vn), (c1, · · · , cn), B)ed un intero k consideriamo l’istanza k-scalata I ′(k) = ((v1(k), · · · , vn(k)), (c1, · · · , cn), B) dove

vi(k) =⌊vi

k

⌋

.

Calcoliamo la soluzione ottima S ′(k) dell’istanza I ′(k) usando l’algoritmo della sezione prece-dente.

Il tempo d’esecuzione dell’algoritmo e O(nV ′(k)) ove V ′(k) =∑

i vi(k). D’altro cantoabbiamo V ′(k) ≤ nVmax(k) ≤ nVmax/k, ove Vmax e Vmax(k) sono il valore massimo di unoggetto nell’istanza originale e nell’istanza scalata. Quindi il tempo d’esecuzione dell’algoritmoche risolve ottimamente la versione scalata del problema e O(n2Vmax/k).

Valutiamo ora la bonta della soluzione ottenuta. Sia S ′ l’insieme di oggetti in una soluzioneottima di I. Abbiamo

V al(S′(k), I) =∑

i∈S′(k)

vi ≥ k∑

i∈S′(k)

⌊vi

k

⌋

≥ k∑

i∈S′

⌊vi

k

⌋

≥ k∑

i∈S′

(vi

k−1) ≥

∑

i∈S′

(vi − k) ≥ Opt(I)−k|S ′|.

QuindiV al(S′(k), I)

Opt(I)≥ 1− k|S′|

Opt(I)≥ 1− nk

Vmax

essendo Opt(I) ≥ Vmax e |S∗| ≤ n.

9. MINIMO MAKESPAN 49

In conclusione, se desideriamo che l’algoritmo approssimato restituisca una soluzione chevalga almeno (1− ε) volte l’ottimo scegliamo k nel modo seguente.

Se b εVmax

nc = 0 allora Vmax < n/ε e quindi l’algoritmo della sezione precedente prende

tempo O(n2Vmax) = O(n3/ε) e da la soluzione ottima. Se b εVmax

nc > 0 allora poniamo k =

b εVmax

nc. In questo caso la soluzione ottenuta e (1−ε)-approssimata e l’algoritmo prende tempo

O(n2Vmax/k) = O(n3/ε).

9. Minimo makespan

Un’istanza consiste di un insieme J di n job di lunghezza p1, · · · , pn da eseguire su mmacchine identiche. Una soluzione ammissibile consiste in uno schedule; cioe una partizioneS = 〈S1, · · · , Sm〉 di J in m insiemi. Il costo MS(S) di uno schedule S e il suo makespandefinito come

MS(S) =m

maxi=1

∑

j∈Si

pj .

9.1. Algoritmo List Scheduling. Esiste un algoritmo molto semplice che approssimail problema dello schedule con minimo makespan. L’algoritmo ListScheduling considera ijob uno per volta ed assegna ciascun job alla macchina che ha il minor carico.

ListScheduling(p1, · · · , pn, m)1. l1, · · · , lm ← 0;2. for i = 1 to n3. sia j tale che lj = minhlh;4. S(i) = j;5. lj = lj + pi;6. end;7. output S;

Teorema 3.13. L’algoritmo ListScheduling ottiene un rapporto di approssimazione(

2− 1m

)

, ove m e il numero delle macchine.

Dimostrazione. Sia i l’ultimo job a terminare nello schedule prodotto dall’algoritmoListScheduling. Sia τ l’istante in cui il job i inizia. Abbiamo quindi che lo schedule calcolatoda ListScheduling ha lunghezza τ + pi.

Osserviamo che per il makespan ottimo vale

Opt(p1, · · · , pn, m) ≥ 1

m

n∑

h=1

ph

ed inoltre che

Opt(p1, · · · , pn, m) ≥ pi.

Fino all’istante τ le macchine sono tutte occupate (altrimenti il job i-esimo sarebbe statoschedulato su una macchina non occupata) ad eseguire job diversi da i e quindi abbiamo che

1

m

∑

h6=i

ph ≥ τ.


Possiamo quindi concludere che

τ + pi ≤1

m

∑

h6=i

ph + pi =1

m

n∑

h=1

ph +

(

1− 1

m

)

pi ≤(

2− 1

m

)

Opt(p1, · · · , pn, m).

Mostriamo ora che esiste una sequenza di job per cui l’algoritmo ListScheduling resti-tuisce uno schedule che ha makespan (2− 1

m) volte quello ottimo. Infatti, se abbiamo m(m−1)

job di lunghezza 1 ed 1 di lunghezza m, ListScheduling produce uno schedule con makespan2m− 1 mentre lo schedule ottimo ha makespan m.

9.2. Job ordinati. In questa sezione studiamo l’algoritmo LongestFirst che considerai job in ordine non decrescente di lunghezza e poi applica l’algortimo ListScheduling.

Abbiamo il seguente teorema.

Teorema 3.14. Per ogni istanza I del problema dello scheduling abbiamo che

LongestFirst(I) ≤(

4

3− 1

3m

)

·Opt(I),

ove m e il numero di macchine.

Dimostrazione. Sia (p1, · · · , pn) una sequenza di job con il minimo numero di job percui

(2) LongestFirst(I) >

(

4

3− 1

3m

)

·Opt(I).

Assumiamo che p1 ≥ p2 ≥ · · · ≥ pn.Osserviamo che se lo schedule ottimo assegna al piu due job per macchina (e pertanto

n ≤ 2m) allora LongestFirst calcola una soluzione ottima.Supponiamo che l’ultimo job a terminare sia pk, con k < n, e consideriamo l’istanza Ik che

consiste dei primi k job di I. Allora abbiamo che LongestFirst(Ik) = LongestFirst(I) eOpt(Ik) ≤ Opt(I). Per l’ipotesi fatta abbiamo

LongestFirst(Ik) = LongestFirst(I) >

(

4

3− 1

3m

)

·Opt(I) ≥(

4

3− 1

3m

)

·Opt(Ik)

contraddicendo la minimalita di I. Pertanto abbiamo che l’ultimo job a terminare e pn.Il job pn ha iniziato al tempo LongestFirst(I) − pn e a quell’istante tutte le macchine

sono occupate. Quindi abbiamo che

LongestFirst(I)− pn ≤1

m

n−1∑

i=1

pi

da cui

LongestFirst(I) ≤ pn +1

m

n−1∑

i=1

pi =1

m

n∑

i=1

pi +m− 1

mpn.

Poiche abbiamo che Opt(I) ≥ 1m

∑ni=1 pi possiamo concludere che

(3) LongestFirst(I)−Opt(I) ≤ m− 1

mpn.

9. MINIMO MAKESPAN 51

Per l’Equazione 2 abbiamo

(4) LongestFirst(I)−Opt(I) >m− 1

3mOpt(I).

Usando Eq. 3 ed Eq. 4, otteniamo

Opt(I) <3m

m− 1

m− 1

mpn < 3pn.

Quindi se assumiamo che esiste un’istanza I su cui LongestFirst ha una rapporto diapprossimazione peggiore di 4/3− 1/3m allora possiamo concludere che l’ottimo su I assegnaal piu due job per macchina. Su questa classe di istanze pero LongestFirst produce unoschedule di makespan minimo. Contraddizione.

Il bound ottenuto nel teorema precedente e tight. Per ogni m, consideriamo 2m + 1 jobdi lunghezza pi = 2m − b(i + 1)/2c per i = 1, 2, · · · , 2m e p2m+1 = m. I primi 2m job sonoassegnati da LongestFirst nel modo seguente: la macchina i riceve i job i e 2m− i + 1 perun carico totale di 3m− 1. In piu ad una macchina viene assegnato il job p2m+1 di lunghezzam. Quindi LongestFirst ottiene un makespan 4m− 1.

L’ottimo invece e 3m e si ottiene assegnando alla macchina n i tre job piu corti (di lunghezzam). Ciascuna delle restanti macchine invece riceve due job; piu precisamente la macchina iriceve i job i e 2m− i− 1 per un carico totale di 3m.

9.3. Uno schema di approssimazione polinomiale. Uno schema di approssimazionepolinomiale (PTAS in breve) e una famiglia S = Sε di algoritmi. In questa sezione mostre-remo, che ogni numero m fissato di macchine, un PTAS tale che l’algoritmo Sε ha tempo diesecuzione polinomiale in n (numero di job) e produce uno schedule di makespan al piu (1+ ε)volte l’ottimo.

Consideriamo il seguente algoritmo Ak che riceve in input le lunghezze di n job ordinatein ordine non decrescente (cioe, p1 ≥ p2 ≥ · · · ≥ pn) e il numero m di macchine:

Fase I.: Calcola uno schedule di makespan minimo per i primi k job.Fase II.: Partendo dallo schedule parziale prodotto nella Fase I, utilizza ListSchedu-

ling sui rimanenti n− k job.

Abbiamo il seguente risultato.

Teorema 3.15. L’algoritmo Ak ottiene un rapporto di approssimazione minore o uguale a

1 +m− 1

k

ove m e il numero delle macchine.

Dimostrazione. Lo schedule prodotto alla fine della Fase I ha makespan Opt(p1, · · · , pk, m)e denotiamo, con leggero abuso di notazione, con Ak il makespan prodotto dall’algoritmo Ak.

Se Ak = Opt(p1, · · · , pk, m) allora, poiche Opt(p1, · · · , pk, m) ≤ Opt(p1, · · · , pn, m), loschedule prodotto dall’algoritmo Ak e ottimo e il teorema vale.

Se, invece, Ak > Opt(p1, · · · , pk, m) allora esiste un job i > k che termina al tempo Ak.Sia τ l’istante di inizio del job i e quindi abbiamo che Ak = τ + pi. Per gli stessi argomenti


usati nella prova del Teorema 3.13 abbiamo che

Ak = τ + pi(5)

≤ 1

m

n∑

h=1

ph +

(

1− 1

m

)

pi(6)

≤ 1

m

n∑

h=1

ph +

(

1− 1

m

)

pk,(7)

ove l’ultima diseguaglianza segue dal fatto che i > k e quindi pi ≤ pk. Ora abbiamo cheOpt(p1, · · · , pn, m) ≥ 1

m

∑nh=1 ph. Inoltre, osserviamo che nello schedule ottimo per (p1, · · · , pk, m)

calcolato nella Fase I, esiste almeno una macchina che riceve almeno d kme job ciascuno di

lunghezza almeno pk. Pertanto abbiamo che

Opt(p1, · · · , pn, m) ≥ Opt(p1, · · · , pk, m) ≥⌈

k

m

⌉

pk

da cui abbiamo

pk ≤Opt(p1, · · · , pn, m)

d kme

≤ Opt(p1, · · · , pn, m)km

.

Sostituendo nell’Equazione 7 abbiamo il teorema.

L’algoritmo Sε esegue l’algoritmo Ak con k = dmεe. Per il teorema precedente Ak restituisce

una soluzione (1+ε)-approssimata. Calcoliamo un limite al tempo di esecuzione dell’algoritmo.La Fase I prende tempo O(mk) mentre Fase II prende tempo m · n per cui, essendo m ≤ n, il

tempo di esecuzione dell’algoritmo e O(nmε ) che e polinomiale in n per m fissato.

9.4. Nota bibliografica. Gli algoritmi discussi in questo capitolo sono stati presentatiper la prima volta in [10, 11]. Lo schema presentato nella Sezione 9.3 e polinomiale per unnumero fissato di macchine. In [12] e presentato uno schema che e polinomiale per un qualsiasinumero di macchine.

10. Primale Duale

10.1. Set Cover Pesato. Vedi [21] pag. 15-17.

10.2. Primale e Duale. Vedi [21] pag. 93-97.

10.3. Primale Duale per Set Cover Pesato. Vedi [21] pag. 108-111.

10.4. Primale Duale per MultiCut. Vedi [21] pag. 145-150.

11. Esercizi

Esercizio 3.1. Dimostrare il Teorema 3.4.

Esercizio 3.2. Dimostrare il Teorema 3.5.

Esercizio 3.3. Provare che il seguente algoritmo 1/2-approssima MaxSAT: sia t l’asse-gnamento che pone tutte le variabili a VERO e sia t l’assegnamento che pone tutte le variabilia FALSO. L’algoritmo restituisce l’assegnamento che tra t e t soddisfa il maggior numero diclausole.

11. ESERCIZI 53

~

~

~

~

~

~

~

~

~

~

~

~

~ ~

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp


pp



pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp




ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp


pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp1

e1

v1

v2

v3

t3

t2

1

e2

s3 t1

s1 s2

ε

Figura 1. Un caso in cui l’algoritmo primale-duale per MultiCut su alberi e2−ε-approssimato. L’ottimo consiste nel solo arco di peso ε. L’algoritmo invecerestituisce come soluzione e1, e2 di peso 2.

Esercizio 3.4. Si consideri il seguente algoritmo per MaxCut: ogni vertice e assegnatocon probabilita 1/2 a S1 e con probabilita 1/2 a S2. Dimostrare che il numero medio di archiche hanno un estremo un S1 e l’altro in S2 e almeno Opt/2.

Esercizio 3.5. Argomentare perche l’algoritmo di Sezione 8.2 non e polinomiale.

Versione: 1.11 del 12 febbraio 2007.

CAPITOLO 4

Algoritmi On-Line

In un algoritmo on-line l’input non e mostrato nella sua interezza, bensı ad ogni passoviene svelato una parte dell’input. Un algoritmo on-line ad ogni passo deve compiere unascelta. La bonta di un algoritmo on-line e stimata confrontando la soluzione ottenuta con lasoluzione ottima calcolata dall’algoritmo off-line che conosce l’intero output. Piu precisamentedenotiamo con CostA(σ) il cost della soluzione prodotta dall’algoritmo on-line A per l’istanzaσ e con Opt(σ) il costo della soluzione ottima prodotta dall’algoritmo off-line. Definiamo lacompetitive ratio (rapporto di competivita) ρA di A come

ρA = supσ

CostA(σ)

Opt(σ).

Alternativamente, diciamo che l’algoritmo A ha competitive ratio c se esiste una costante a ≥ 0tale che per ogni istanza σ

CostA(σ) ≤ c ·Opt(σ) + a.

1. Il problema dello sciatore

Uno sciatore deve decidere se comprare o fittare gli sci. Il costo dell’affitto degli sci per ungiorno e 1 mentre comprare gli sci costa B. Ovviamente se lo sciatore conosce il numero T divolte in cui andra a sciare la decisione e semplice. Il primo giorno che andra a sciare lo sciatorecomprera gli sci se B < T ; se invece B ≥ T allo sciatore conviene prendere gli sci in affitto.La versione off-line del problema (quando l’intero input e noto) e quindi di facile soluzione edil costo della soluzione e minT, B.

Consideriamo invece il caso piu realistico in cui lo sciatore non conosce T . Un algoritmo on-line deve decidere ogni volta che lo sciatore va a sciare se comprare gli sci o fittarli. Ovviamenteuna volta comprati il problema non si pone. Consideriamo quindi il seguente algoritmo chedecide se lo sciatore compra o fitta gli sci l’i-esima volta che va a sciare avendo in input i, B eT .

A(i, B, T )if i ≤ B − 1 then affitta;if i = B then compra;if i > B then comprati in precedenza;

end

Calcoliamo ρA. Se T ≤ B − 1 l’algoritmo A spende T in quanto fitta gli sci per T voltecosı come l’algoritmo off-line. Se invece T ≥ B l’algoritmo spende 2B − 1 in quanto fitta glisci per B − 1 volte e poi li compra. In questo caso invece l’algoritmo ottimo compra gli sci il

55

56 4. ALGORITMI ON-LINE

primo giorno per un costo totale di B. Pertanto abbiamo che

ρA ≤2B − 1

B= 2− 1

B.

Mostriamo ora che nessun algoritmo on-line ha un rapporto di competivita migliore di A.Osserviamo che un algoritmo S on-line e determinato univocamente dal numero s di giornidopo i quali decide di comprare gli sci. Abbiamo due casi:

(1) s ≤ B− 1. In questo caso se T = s + 1, l’algoritmo on-line spende s + B e l’algoritmoottimo spende s + 1. Abbiamo quindi

ρS ≥s + B

s + 1≥ 1 +

B − 1

s + 1≥ 2− 1

s + 1≥ 2− 1

B.

(2) s > B− 1. In questo caso se T = s + 1, l’algoritmo on-line spende s + B e l’algoritmoottimo spende B. Abbiamo quindi

ρS ≥s + B

B≥ 2.

2. Ritrovare l’auto

Supponiamo di abitare su una retta. Ogni mattina dobbiamo cercare la nostra auto percheedimentichiamo puntualmente dove l’abbiamo parcheggiata la sera prima. Ovviamente se l’autosi trova a distanza d dalla nostra casa l’algoritmo (off-line) che conosce la posizione impiegatempo d per trovarla. Mostriamo ora un algoritmo (on-line) che non conosce la posizionedell’auto e per trovare l’auto impiega al piu 9d.

TrovaAuto

d = 1;dir=sx;repeat

vai fino a distanza d nella direzione dir;se trovi l’auto, fine;ritorna a casa;d = d ∗ 2;dir=-dir;

Il caso peggiore di questo algoritmo e quando l’auto si trova alla distanza d = 2j + ε eabbiamo cercato su questo lato fino a 2j e poi abbiamo cercato fino a 2j+1 dall’altro lato. Inquesto caso il costo dell’algoritmo e

2(1 + 2 + 4 + · · ·+ 2j+1) + 2j + ε ≤ 9 · 2j .

3. Gestione online di liste

In questa sezione studiamo il seguente problema. Abbiamo un certo numero n di oggettiche sono organizzati in una lista. Ad ogni passo riceviamo una richiesta per uno degli noggetti. Se l’oggetto richiesto si trova nella posizione i, soddisfare la richiesta ci costa i. Unavolta recuperato l’oggetto richiesto possiamo spostarlo in una qualsiasi delle posizioni tra latesta della lista e la sua posizione originale i. Inoltre possiamo scambiare di posto due oggettiadiacenti al costo di 1. Il nostro scopo e progettare un algoritmo on-line (e che quindi nonconosce la sequenza di richieste che dovra soddisfare) che organizza gli elementi nella lista (e

3. GESTIONE ONLINE DI LISTE 57

cioe decide dove spostare un oggetto una volta che e stato richiesto e quali oggetti adiacentiscambiare id posto) in modo da rendere il costo di soddisfare una sequenza di richieste ilpiu piccolo possibile. Osserviamo che in questo caso l’analisi worst-case non ha molto senso:infatti il caso peggiore e ottenuto dalla sequenza che richiede sempre l’ultimo elemento dellalista e nessun algoritmo puo soddisfare una sequenza di m richieste spendendo meno di O(mn).Un’analisi piu interessante si ottiene invece confrontando il costo di un algoritmo con il costodell’algoritmo ottimo che conosce tutte le richieste. Assumiamo che entrambi gli algoritmipartano con la stessa lista.

3.1. Move to Front Heuristics. In questa sezione analiziamo il seguente semplice al-goritmo che chiamiamo MoveToFront: ogni volta che un oggetto e richiesto, viene spostatoall’inizio della lista. Notiamo che MoveToFront e un algoritmo om-line: ogni rischiesta esoddisfatta senza avere alcuna conoscenza delle richieste future.

Consideriamo una sequenza R = r1, · · · , rm di m sequenze ed indichiamo con MTF(t)il costo di MoveToFront per soddisfare rt e con MTF(R) il costo di MoveToFront persoddisfare la sequenza R. Indichiamo con Opt l’algoritmo ottimo che conosce l’intera sequenzaR di richieste e Opt(t) e Opt(R) sono definiti analogamente. Diciamo che una coppia (x, y)di oggetti costituisce un’inversione se si trovano in ordine diverso tra Opt e MoveToFront.Denotiamo inoltre con Φ(t) il numero di inversioni dopo che la richiesta rt e stata soddisfatta.Abbiamo il seguente lemma.

Lemma 4.1. Per ogni t,

MTF(r) + Φ(t)− Φ(t− 1) ≤ 2 ·Opt(t).

Prima di dimostrare Lemma 4.1 mostriamo come esso implichi il seguente teorema.

Teorema 4.2. Per ogni sequenza R di richieste MTF(R) ≤ 2 ·Opt(R).

Dimostrazione.

MTF(R) =m∑

t=1

MTF(t)

≤m∑

t=1

(2Opt(t)− Φ(t) + Φ(t− 1))

= Φ(0)− Φ(m) + 2

m∑

t=1

Opt(t)

= Φ(0)− Φ(m) + 2 ·Opt(R).

La dimostrazione e conclusa dalle osservazioni che Φ(0) = 0 e Φ(m) ≥ 0.

Passiamo ora alla dimostrazione di Lemma 4.1.

Dimostrazione. Consideriamo l’i-esima richiesta ri e denotiamo con ti la posizione del-l’oggetto richiesto nella lista di MoveToFront e con si la posizione dell’oggetto richiesto nellalista di Opt. Abbiamo quindi che MTF(i) = ti e Opt(i) = si + pi, dove pi denota il numerodi scambi effettuati dopo aver soddisfatto ri dall’algoritmo Opt (nota che MoveToFront

non effettua alcuno scambio). Abbiamo due casi.

58 4. ALGORITMI ON-LINE

Caso I: si < ti. Studiamo prima il caso in cui pi = 0. In questo caso osserviamo che ilnumero di inversione che coinvolgono l’oggetto ri prima che la richiesta venga soddisfatta ealmeno ti − si. Mentre invece, siccome ri e spostato in testa alla lista, dopo che ri e statasoddisfatta il numero di inversioni che coinvolgono ri e al piu si − 1. Inoltre in questo casoil numero di inversioni che non coinvolgono ri (essendo questo l’unico elemento spostato siada MoveToFront che da Opt) resta invariato. Quindi denotando con I questo numeroabbiamo che

Φ(i− 1) ≥ ti − si + I

eΦ(i) ≤ si − 1 + I.

Da cui

MTF(i) + Φ(i)− Φ(i− 1) ≤ ti + si − 1 + I − ti + si − I

= 2si − 1

≤ 2Opt(i).

Supponiamo ora che pi > 0. Osserviamo che ciascuno dei pi scambi effettuati da Opt

incrementa Φ(i)− Φ(i− 1) al piu di 1 e quindi

Φ(i)− Φ(i− 1) ≤ (si − 1)− (ti − si) + pi.

Quindi abbiamo

MTF(i) + Φ(i)− Φ(i− 1) ≤ ti + si − 1− ti + si + pi

= 2si − 1 + pi

≤ 2si + 2pi

= 2Opt(i).

Caso II: si ≥ ti. Per ragionamenti simili a quelli usati nel caso precedente, abbiamo cheΦ(i− 1) ≥ si − ti + I e che Φ(i) ≤ si − 1 + I. Quindi abbiamo

MTF(i) + Φ(i)− Φ(i− 1) ≤ ti + si − 1 + ti − si + pi

≤ 2 · ti + pi

≤ 2 · si + 2 · pi

≤ Opt(i)

3.2. Lower bound. In questa sezione mostriamo che l’algoritmo MoveToFront e es-senzialmente ottimo per quel che riguarda il problema di gestione di una lista.

Sia A un algoritmo (deterministico) online per il problema di gestione di una lista; mostre-remo una sequenza R di m richieste su n oggetti (con m = n3) ed un algoritmo offline O taliche A su R spende quasi il doppio di O.

La sequenza di richieste R e la sequenza che chiede sempre l’elemento che si trova in coda(cioe alla posizione m) della lista di A. Pertanto A spende su R mn = n4. L’algoritmooffline O invece ordina gli n elementi della lista per frequenza f1 ≥ · · · ≥ fn. Il costo di Oper la sequenza R e dato dal costo di ordinare mediante scambi di elementi adiacenti gli nelementi in ordine decrescente di frequenza (questo passo costa O(n2)) e il costo di servire le

3. GESTIONE ONLINE DI LISTE 59

m richieste (questo passo costa∑n

i=1 ifi che e massimizzato quando tutte le fi sono uguali am/n). Pertanto O spende m/n ∗∑n

i=1 i + O(n2) = n4/2 + O(n2). Quindi abbiamo che A haun rapporto di competivita almeno 2−O(1/n2).

Versione: 1.7 del 7 gennaio 2007.

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] T. Brueggemann and W. Kern. An improved deterministic local search algorithm for 3-SAT. Theoretical

Computer Science, 329(1-3):303–313, 2004.[3] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM

symposium on Theory of computing, pages 151–158. ACM Press, 1971.[4] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progression. Journal of Symbolic

Computation, 9:251–280, 1990.[5] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.[6] 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.[7] M. R. Garey, D. S. Johnson, and L. J. Stockmeyer. Some simplified NP-complete graph problems.

Theoretical Computer Science, 1:237–267, 1976.[8] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, 1979.[9] Michel X. Goemans and David Williamson. New 3

4-approximation algorithms for MAX SAT. SIAM Journal

on Discrete Mathematics, 7:656–666, 1994.[10] R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45:1563–1581,

1966.[11] R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics,

17:416–429, 1969.[12] D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems:

theoretical and practical results. Journal of the ACM, 34:144–162, 1987.[13] 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.

[14] 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.[15] R. M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages

85–103, 1972.[16] L. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):265–266, 1973.[17] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.[18] C. H. Papadimitriou. On selecting a satisfying truth assignment. In Proceedings of the 32nd IEEE

Symposium on the Foundations of Computer Science, pages 163–169, 1991.[19] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM,

27(4):701–717, October 1980.[20] L. G. Valiant. A scheme for fast parallel communication. SIAM J. Comput., 11(2):350–361, 1982.[21] Vijay V. Vazirani. Approximation Algorithms. Springer, 2003.

61

Algoritmi e Strutture Dati--Lecture...

Documents

Transcript of Algoritmi e Strutture Dati--Lecture...