Algoritmi e Complessita’
computazionale
materiale di riferimento per lo studio
appendice App_Complessita’.pdf
Problemi decidibili :-\
Non tutti i problemi formulati
matematicamente in modo rigoroso sono
decidibili
Halting problem: dato un programma e un
input decidere se termina o va in loop
Siamo interessati ai soli problemi decidibili,
tali per cui esiste almeno un algoritmo
che ne risolva ogni istanza.
Complessita’ di un algoritmo A
• f(n) = Numero di operazioni elementari
necessarie all’esecuzione di A in funzione della
dimensione dell’input
• Complessita’ in tempo e non in memoria
• Modello di calcolo: macchina di turing
• Per quali istanze?
– Caso medio (difficile da valutare)
– Caso pessimo (garantisce la prestazione)
Valutazione asintotica
• Non siamo interessati alla valutazione
esatta della funzione f(n) ma al suo
andamento asintotico, al crescere della
dimensione (n) delle istanze.
• Il tipo di andamento si puo’ descrivere
attraverso una funzione g(n) che limita
superiormente e inferiormente f(n)
f(n) si dice
O(g(n)) 
Omicron di g
 c,d 0 : f(n)  c + d g(n) n>n’
W(g(n)) 
Omega di g
 a,b 0 : a + b g(n)  f(n) n>n’
Q(g(n)) 
Teta di g
 a,b,c,d 0 : a + b g(n)  f(n)  c + d g(n) n>n’
Q induce delle classi di equivalenza
(stesso tasso di crescita)
esempi
• Ricerca binaria per individuare un elemento e in una lista
ordinata di n elementi: (si confronta e con l’elemento l
situato alla meta’ della sottolista corrente,
– se l<e si itera rispetto alla meta’ superiore della sottolista
corrrente,
– se l>e si itera rispetto alla meta’ inferiore,
– se l=e stop)
– complessita’ Q(lg n)
• Enumerazione di tutte le permutazioni di n nodi per
trovare il ciclo di costo minimo che passa per tutti gli n
nodi una e una sola volta (ciclo hamiltoniano):
– complessita’ Q(n!)
funzioni polinomiali vs esponenziali
f(n)
Valori approssimati per
n= 10
100
1000
n logn
33
664
9966
n3
1000
106
109
106n8
1014
1022
1030
2n
1024
1.27 1030 1.05 10301
nlogn
2099
1.93 1013 7.89 1029
n!
3628800
10158
4 102567
•
Pseudopolinomiale:
quando A e’ polinomiale anche in funzione di un
dato numerico dell’istanza e non solo nella sua dimensione.
Ad esempio, sia A un algoritmo su grafi pesati, e la complessita’ di A
dipenda anche dal valore del costo dell’arco di costo massimo del grafo
nella specifica istanza di input.
Polinomiale ≡ pratico
mentre
esponenziale ≡ inapplicabile?
NON sempre!
(paradosso del simplesso)
Uno degli algoritmi + utilizzati in OR (simplesso)
e’ esponenziale nel caso pessimo
ma molto efficiente nel caso medio….
La programmazione lineare PL
(il problema risolto dal simplesso)
e’ un problema polinomiale.
Il fatto e’ dimostrabile grazie al metodo dell’elissoide,
un algoritmo polinomiale,
dalle prestazioni medie attualmente inferiori a quelle del simplesso!
Classi di Complessita’ dei problemi
• Problema di ottimizzazione p = (F,c,min)
La terna e’ costituita da F la regione ammissibile,
c(x) la funzione obiettivo da minimizzare su F.
• Versione decisionale dp = (F,c,min,k)
 {xF : c(x)k?}
FATTI: p e’ non meno difficile di dp
p  dp se valutare c(x) e’ polinomiale
• Problema di certificato pc = (xF?) e’ il test di
ammissibilita’ di una potenziale soluzione
Classi P e NP
• Un problema p=(F,c,min) si dice nella classe NP se
esiste un algoritmo polinomiale che risolve il
problema di certificato associato pc=(xF ?)
• Un problema p=(F,c,min) si dice nella classe P se
esiste un algoritmo polinomiale che ne risolve in
modo esatto la versione decisionale
Requisito Minimale dei problemi allo studio:
p e’ DECIDIBILE & p NP
P = NP ?
• Th: PNP
• Congettura: PNP
NP
??
P
I problemi “difficili”
Un problema dp = (F,c,min,k) si dice NP-Completo
(e la versione di ottimizzazione p = (F,c,min) si dice NP-Hard)
SE
• pNP
•  un algoritmo polinomiale che riduce a dp tutti gli altri
problemi NP (algoritmo di riduzione)

Un problema dp NP-Completo e’ almeno tanto
difficile quanto ogni altro problema in NP.
Per nessun problema NP-Completo e’
noto un algoritmo (esatto) polinomiale

Se esistesse un algoritmo polinomiale per
un problema dp NP-Completo allora ne
esisterebbe uno anche per tutti gli altri
problemi in NP,
e di conseguenza varrebbe che P=NP.
Le principali classi di complessita’
NP
P
NP-Completi
Quali sono i problemi difficili?
• Il principale: SATisfiability Problem da cui la comnplessita’ della PLI
TH Cook: SAT e’ NP-Completo
• La piu’ parte dei problemi di Ottimizzazione Combinatoria
sono NP-Completi: es.
– Vertex cover (minimo insieme di vertici per cui ogni arco del
grafo ha almeno un vertice selezionato)
– Independent Set (massimo insieme di vertici non adiacente) e
complementare del Vertex cover
– Max Clique (individuare il sottografo completo col maggior
numero di vertici)
– Knapsack (dato un insieme di oggetti ciascuno di peso wi e
valore pi selezionare il sottoinsieme di valore massimo con peso
totale  Q)
– ILP (da SAT)
The SATISFIABILITY problem
• xi {F,T} variabile booleana (letterale)
• Operatori: And , Or , Not ! , ¬
• Clausola: Or di variabili boleane (negate): es. C=(xi  xj  !xh)
• Formula in FormaNormaleCongiuntiva: And di Clausole: F=C1C2
• Assegnazione di verita’ v: X → {F,T}
• Una formula F si dice soddisfattibile se assume valore T per almeno un
assegnamento delle sue variabili (quindi tutte le sue clausole devono
essere T poiche’ la formula F e’ un And di clausole).
SAT:  v tale che F sia soddisfattibile ?
esempio
F = (x1  x2  !x3)  (x1  !x2  x4)  (!x1  x3  !x4)  (!x1  x4)
F e’ vera per x1=1 x2=0 x3=1 x4=1 e per x1=0 x2=0 x3=0 x4=0
mentre l’assegnamento di verita’ x1=1 x2=0/1 x3=0/1 x4=0
rende la formula F falsa.
Interpretando
gli operatori  come prodotto,  come somma, ! come 1-x,
i simboli F come 0, T come 1,
risolvere SAT (soddisfare F) equivale a
cercare una soluzione ammissibile al sistema di PLI {Cj 1,  j}
x1 + x2 + (1-x3) 1
x1 + (1-x2) + x4 1
xi {0,1} i
(1-x1) + x3 + (1-x4) 1
(1-x1) + x4 1
• 2-SAT e’ un problema SAT con al + 2 letterali xi
per ciascuna clausola
• Ogni altra forma di SAT si puo’ riscrivere in
modo equivalente in modo che ogni clausola
abbia esattamente 3 letterali (3-SAT)
• Quindi parlare della complessita’ di SAT si riduce
a parlare della complessita’ di 2-SAT e di 3-SAT.
Si puo’ dimostrare che
• 2-SAT e’ polinomiale
• 3-SAT e’ NP-Hard
2-SAT
Costruiamo un grafo diretto G=(N,A) dove
N = {xi, !xi  letterale nella formula F}
L’insieme dei nodi e’ costituito da tutti i letterali che compaiono
nella formula e la loro negazione
A = {(xi,xh)  clausola C=(!xi  xh)}
L’insieme degli archi e’ costituito da tutte le implicazioni che
sono presenti nella formula F, due per ogni clausola
G contiene un arco orientato (i,h) se e solo se esiste in F una
clausola C=(!xi  xh) e ha il significato di “i implica j” (ij).
l’implicazione ij e’ equivalente alla contronominale !j  !i
Equivalenza logica
Le formule ¬ab, a→b, ¬b→ ¬a, sono logicamente equivalenti, i.e., hanno
lo stesso valore di verita’ in funzione di a, b. Ricordando che a→b non e’
verificata (vale 0) solo per a=1 e b=0 (ipotesi verificate ma tesi non
verificata), costruisco la tabella di verita’:
a
b
¬a
¬b
¬ab a→b ¬b→¬a
0
0
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
0
1
1
0
0
1
1
1
contronominale

Di conseguenza, sul grafo G=(N,A) associato alla formula F,
la singola clausola C =(!xi  xh) genera 2 archi nel grafo:
l’arco (i,h) ma anche l’arco (!h,!i)
data l'equivalenza di xh e !!xh
e quindi l'equivalenza della clausola (!xi  xh) con la clausola (!xi  !!xh)
il grafo G possiede una simmetria:
se (i,h) è un arco di G,
allora in F c’e’ la clausola (!xi  xh)
che e’ equivalente alla clausola (!xi  !!xh)  (!!xh !xi)
che genera l’arco (!h, !i)
allora anche (!h,!i) è un arco di G
Infatti, dati due letterali a, b, affermare
“a oppure b” equivale ad affermare sia che
“se non a allora b”, che “se non b allora a”
(proprieta’ contronominale)
Ogni arco (i,j) in G rappresenta un’ implicazione logica xi →xj
in base all’equivalenza logica tra (!xi  xj) e (xi →xj)
Osservazione: l’implicazione e’ transitiva:
(a→b) e (b →c) e (c→d) implica (a→d)
Un cammino orientato su G e’ una sequenza di implicazioni tale che
la tesi di una implicazione coincide con l’ipotesi della successiva.
TH:
F e’ insoddisfattibile 
 un indice i tale per cui sul grafo G posso andare
da xi a !xi e anche da !xi a xi
Dim:
se  un cammino orientato da xi a !xi e uno da !xi a xi 
F induce entrambe le
implicazioni (xi→!xi) e (!xi→xi) per la transitivita’ dell’implicazione.
Se v(xi)=T  (xi →!xi) genera la contraddizione (T→F)
Se v(xi)=F  (!xi→xi) genera la contraddizione (T→F)
.
Nessun assegnamento di valori di verita’
v(xi) puo’ soddisfare F.
Posso usare queste considerazioni operativamente
per costruire un algoritmo che dica se F e’ soddisfattibile?
Ricordiamo che
(a  b) induce gli archi
(!a  b) induce gli archi
(!a  !b) induce gli archi
ESEMPIO
!a→b e !b→a
a→b e !b→!a
a→!b e b→!a
esercizio: applichiamolo alla formula
F = ( x1  x2 )  (x1  !x3)  (!x1 x2 )  (x2  x3)
Esiste (almeno) un cammino da !x2 a x2 ma non viceversa.
Il cammino da !x2 a x2 rende falsa l’assegnazione di verita’ F a x2 poiche’
genera la contraddizione T→F. Devo necessariamente assegnare v(x2)=T
Propago il valore x2=T sul grafo: come? Nell’unico modo che evita T→F
Secondo la regola:
se un nodo e’ F il predecessore deve essere F.
se un nodo e’ T il successore deve essere T.
In questo caso la propagazione non ha effetti poiche’ il nodo x2 non ha archi
uscenti, ne’ !x2 ha archi entranti.
Consideriamo la variabile x1: non ci sono cammini orientati ne da x1 a !x1,
ne viceversa, quindi provo ad assegnare un valore di verita’ (T) ad x1.
Propago in avanti v(x1)=T,
in coerenza con l’attuale valore di x2.
cosi’ come la propagazione all’indietro
di v(!x1)=F lo e’ con l’attuale valore di !x2.
T
Qualsiasi assegnazione a x3 soddisfa F
poiche’ non si crea mai T → F
F = ( x1  x2 )  (x1  !x3) 
(!x1 x2 )  (x2  x3)
F
F
T
Esercizio
F = (¬ab)  (¬bc)  (a¬c)  (cb)
!a
F e’ soddisfattibile ?
Costruisco il grafo,
seleziono una variabile,
le assegno valore di
verita’
e propago
a
c
!b
!c
b
F = (¬ab)  (¬bc)  (a¬c)  (cb)
!a
Costruisco il grafo
a
c
!b
!c
b
F = (¬ab)  (¬bc)  (a¬c)  (cb)
F
Propago v(a)=T
Il suo successore b deve essere T
Anche c, successore di b, deve essere T
!a
T
T
a
c
Assegno valore alle negazioni
dei letterali gia assegnati
!b
Non ci sono contraddizioni, perche’ non
si sono create implicazioni del tipo T→F
F
Infatti da nessun nodo T posso raggiungere,
tramite un cammino orientato, un nodo F:
Ad esempio, da !a raggiungo a, mentre da a non raggiungo !a
!c
F
b
T
Ho trovato una assegnazione dei valori di verita’ che soddisfa F
F = (¬ab)  (¬bc)  (a¬c)  (cb)
Ora propago v(a)= F
Il suo predecessore c deve essere F
!a
T
F
F
a
c
Anche !b, predecessore di c, deve essere F
Assegno valore alle negazioni
!b
!c
F
T
Individuo una contraddizione associata all’arco b → c.
b
T
QUINDI
La formula F NON E’ soddisfattibile per v(a)=F ma LO E’ per v(a)=T
Dagli esempi al metodo
Come opera l’algoritmo? In sintesi,
• Attraverso una visita del grafo per archi uscenti, a partire da un
nodo, certifico la soddisfattibilita’ o meno di F per un dato
assegnamento di verita’ al letterale corrispondente al nodo.
• In caso affermativo, propagando i valori di verita’ possibili, ottengo
una assegnazione di verita’ che soddisfa F.
• L’algoritmo ha complessita’ polinomiale
vediamo in maggior dettaglio a cosa
corrispondono questi passi sulla formula F…
L’algoritmo implementa tramite operazioni di visita
su grafo la seguente procedura sulla formula F:
Seleziona una variabile xi e ponila a T
Modifica la formula F basandosi su xi =T (propagazione)
secondo queste regole
• rimuovi ogni clausola resa vera da xi=T (ogni clausola che
contenga xi)
• assegna valore agli altri letterali della clausola non
assegnati, secondo queste regole, che impediscono di
avere la contraddizione (T implica F):
– per ogni clausola della forma (xi  xk) con xi=T allora xk deve
essere T. Ricorsivamente modifica la fomula basandosi su xk=T.
– per ogni clausola della forma (xi  xk) con xi=F allora xk deve
essere F. Ricorsivamente modifica la fomula basandoti su xk=F.
Si possono avere 3 casi
al termine della procedura di propagazione
• 1) Tutte le variabili hanno un valore  la formula F e’
soddisfattibile perche’ la propagazione e’ fatta in modo da
non ceare contraddizioni.
• 2) Molte clausole, ma non tutte, sono state rimosse,
lasciando un problema di dimensioni ridotte  Seleziona
un’altra variabile e ripeti.
• La scelta xi=T ha portato a una contraddizione.
– Allora riprendi dalla partenza propagando xi=F.
– Se anche questa scelta porta a una contraddizione  la formula e’
insoddisfattibile, altrimenti vai al caso 1 o 2
Individuare la classe di un problema p
NP
P
NP-Hard
???
p
Trasformazioni e riduzioni
Trasformazione polinomiale
E’ un algoritmo R che, data un’istanza I di un problema decisionale
p, produce in tempo polinomiale un’istanza I’ di un problema
decisionale p’ in modo tale che, se la risposta è “SI” per I, allora la
risposta è “SI” anche per I’
Riduzione polinomiale (simbolo p) ( q pp  q si riduce a p)
E’ un algoritmo Rq che, per risolvere un’istanza Iq di un problema
decisionale q, usa al suo interno una subroutine che risolve
un’istanza Ip di un problema decisionale p, in modo tale che
l’algoritmo Rq sarebbe polinomiale SE
- la subroutine fosse di ordine O(1), (cioe’ se fosse
eseguita in un tempo costante indipendente dalla dimensione di Ip),
- i parametri da passare alla subroutine fossero
calcolabili in tempo polinomiale
Individuare la classe di un problema
q  P, p p q (il nostro problema si riduce ad uno polinomiale)
 pP
q  NP-Completi, q p p (un problema Np-Completo si riduce al nostro problema )
 p  NP-Completi
NP
P
q
NP-Hard
q
p
p
p
Come attribuire una classe di
complessita’ a un problema
TEST:
• p  P?
SI se riduco p a un problema
q in P con una riduzione polinomiale
(procedimento contruttivo poiche’ fornisco un
algoritmo polinomiale per p)
• p  NP-Completi? SI se riduco un problema q
NP-Completo a p con una riduzione polinomiale .
Esempio di riduzione a un
problema in P
• 2-SAT si riduce a un problema di connessione su un grafo,
risolvibile con un numero polinomiale (2n) di chiamate a
una procedura di visita per stelle uscenti, che e’ a sua
volta polinomiale nella dimensione del grafo.
INFATTI
• Per ogni letterale i la visita verifica se esiste un cammino
orientato che connette il nodo associato ad xi al nodo
associato a !xi e se esiste anche un cammino orientato
che connette !xi a xi. In tal caso nessuna assegnazione di
verita’ rende la formula soddisfattibile.
Dimostrazione di NP-completezza
di un problema p
• Per RESTRIZIONE: si dimostra che un caso
particolare di p e’ NP-completo (nb non vale
l’inverso, i.e. p caso particolare di un problema
NP-completo)
• Per RIDUZIONE: si determina una riduzione
polinomiale di un problema q in p, essendo noto
che q e’ NP-completo. Infatti se p fosse
polinomiale avrei trovato un algoritmo
polinomiale anche per q → assurdo.
Alcuni problemi NP-Completi
(in forma decisionale)
3SAT : Data una formula di n letterali F(x1, …,xn) in 3-NCF,
i.e. F = C1  …  Cm, dove Ci = (xi1xi2xi3), F e’ soddisfattibile ?
Clique : dato un grafo G, e un numero k>0 ∊ N, G contiene un
sottografo completo di k nodi?
Vertex Cover : dato G=(V,E), e un intero i, esiste un sottoinsieme di
nodi UV s.t. |U|= i e  arco e=(u,v) ∊ E, almeno un suo estremo u
o v sta in U ?
Independent Set: dato G=(V,E), e un intero k>0, esiste un sottoinsieme
U di V s.t. |U|= k e  coppia di nodi in U non esiste l’arco e=(u,v)?
Subset Sum: dati n elementi {w1, …,wn} e un valore B, esiste un
sottoinsieme di elementi la cui somma vale ex B ?
(Noto il caso di B=Σi wi /2)
Alcuni esempi di riduzione
• 3-SAT si riduce a Clique (3-SATpC)
• Clique si riduce a Vertex Cover (CpVC)
3-SAT si riduce a Clique
( Clique e’ NP-Hard)
• Costruisco un grafo G=(V,E) con
– V = { coppie <a,i> | a e’ un letterale della clausola Ci }
– E = { (<a,i>,<b,j>) | i j and a  !b }
i.e. non ci sono archi tra due nodi del tipo <a,i> <!a,j> (stesso
letterale negato e affermato) ne ci sono archi tra due nodi del tipo
<ai> <b,i> (letterali della stessa clausola)
• Su G cerco una clique di dimensione
k = m, numero di clausole
• Hint: i nodi della clique sono i letterali a cui devo
dare valore vero per soddisfare la formula
3-SAT p Clique (esempio)
• F = (x1  x2  !x3)  (x2  !x1  x3)
Nel grafo esiste
(almeno)
una clique di 2
nodi, fatta da x1,1 e x2,2.
Infatti dando valore
True ai due letterali,
verifico entrambe
le clausole C1 e C2,
e dunque la formula F
3-SAT p Clique
(proposta di esercizio)
F = (!ab !c)  (!bc)  (a!c)
Sono cliques di dimensione 3
le seguenti;
!c,3
a,3
{!a1, !b2, !c3} con assegnamento
di verita’ a=b=c=F
!a,1
c,2
b,1
!b,2
!c,1
{!c1, !b2, a3} e assegnamento
di verita’
pari a a=T, b=c=F
Entrambi gli assegnamenti
soddisfano la formula
Perche’ la cliques di dimensione massima
non puo’ avere dimensione > m (numero delle clausole)?
3-SAT p Clique (dim.)
• Supponiamo che F = C1  …  Cm, sia soddisfattibile.
Allora in ogni clausola C almeno un letterale a ha valore
T, e non possono essere contemporaneamente veri a
nella clausola Ci e la sua negazione !a nella clausola Ck.
• Questi nodi formano una Clique di dimensione m=k
perche’ esiste un arco tra ciascuna coppia di siffatti nodi.
• Al contrario, se  una Clique di dimensione m, allora
deve contenere un nodo <ai> per ogni indice i, poiche’ i
letterali della stessa clausola (con lo stesso i) non sono
adiacenti. Inoltre non possono essere nella stessa
Clique sia a che !a, per lo stesso motivo.
• Ponendo a T i letterali corrispondenti ai nodi della clique
si soddisfa la formula F.
Clique si riduce a Vertex Cover (I)
( Vertex Cover e’ NP-Hard)
• Costruisci il grafo complementare GC = (V,EC), dove EC= {(u,v)
| (u, v)  E } sono gli archi non presenti in G=(V,E).
• Sia l = |V |-k = n-k.
Grafo G
Grafo complementare GC
Clique si riduce a Vertex Cover (II)
• Se nel grafo G esiste una clique K  V di dimensione k, allora
in GC nessuna coppia di vertici della clique K e’ adiacente, per
definizione di GC.
• Allora i nodi in V-K sono un vertex cover per GC di dimensioni
l=n-k, poiche’ ogni arco di GC ha almeno un vertice non in K..
• Viceversa, se GC ha un vertex cover U di dimensione n-k,
allora nessuna coppia di vertici s, t in V-U e’ adiacente,
altrimenti il loro arco (s,t) non sarebbe coperto dai soli nodi in
U mentre per hp U e’ un vertex cover.
• Allora i nodi di V-U nel grafo G formano una clique di
dimensione k.
Problemi complementari:
la classe co-NP
• coNP e’ la classe di complessita’ i cui membri sono
problemi complementari di quelli in NP. Cosi’ come NP e’
definita come la classe dei problemi il cui certificato e’
polinomiale (rispondere alla domanda “x appartiene da
F”?), coNP puo’ essere considerata come la classe di
problemi per cui esiste un certificato polinomiale del tipo
“x NON appartiene ad F”?
G
GC
Grafo complementare GC
Grafo G
K7
K7 e’ il grafo completo di ordine 7,
dato dall’unione degli archi
in G e in GC
G
GC
i nodi in verde sono una clique in G,
i nodi fuxia sono un vertex cover in GC
Polinomiale o Esponenziale?
Cambiare un piccolo dettaglio
della definizione di un problema puo’ mutarne
l’appartenenza da una classe all’altra
P
Shortest Path
Eulerian Circuit
Edge Cover
MST
NP-complete
Longest ElementaryPath
Hamiltonian Circuit
Vertex Cover
Steiner Tree
Consiglio: consultare il Garey&Johnson (biblioteca,
emule) e il compendium
http://www.csc.kth.se/~viggo/problemlist/
conclusioni
• Dato un nuovo problema e’ utile determinare se questo e’ in P o e’
NP-Difficile, allo scopo di determinare l’approccio risolutivo + adatto.
• Nel primo caso la dimostrazione ci da un algoritmo di soluzione.
• Nel secondo, sappiamo che per ottenere una soluzione ottima
pagheremo nel caso pessimo un tempo esponenziale. Se
l’applicazione reale non lo consente opteremo per un approccio di
tipo euristico.
• L’analisi puo’ mettere in luce dei sottoproblemi facili del nsotro
problema (prese alcune decisioni il problema restante e’ in P) che
possono suggerire degli approcci risolutivi che sfruttano questa
proprieta’.