Teoria della Complessità
Concetti fondamentali

L’oggetto della teoria della complessità è stabilire se
un problema sia facile o difficile

La difficoltà di un problema è una caratteristica
generale e non associata a particolari istanze del
problema stesso
Definizione
Un problema è la richiesta a rispondere ad una
domanda circa le proprietà di una struttura
matematica in funzione di parametri costanti e dei
valori non fissati di variabili
1
Esempio
Dato un grafo G=(V,E), esiste un percorso
hamiltoniano di lunghezza <K?



Struttura del problema = grafo G
Struttura della soluzione = percorso hamiltoniano
Parametri = i particolari nodi, archi ed i pesi degli
archi
2
Definizioni fondamentali
Istanza di un problema
Un particolare caso del problema per cui sono stati
specificati i valori assunti dai parametri.
Un problema è l’insieme delle sue infinite istanze.
Problemi di decisione
Risposta SI/NO
(es., $ un ciclo hamiltoniano di lunghezza <K?)
3
Definizioni fondamentali
Problemi di ricerca
Trovare una soluzione (una prova della risposta “SI”)
(es., trovare un ciclo hamiltoniano di lunghezza <K)
Problemi di enumerazione
Trovare tutte le soluzioni
(es., trovare tutti i cicli hamiltoniani di lunghezza <K)
Algoritmo
Metodo per passi successivi per risolvere un
problema
4
Facilità di un
problema
Difficoltà di un
problema
Esiste un algoritmo
di soluzione
efficiente
Non esiste un
algoritmo
di soluzione efficiente

Stabilire la difficoltà di un problema
 misurare l’efficienza del (migliore) algoritmo
risolutore

Misurare l’efficienza di un algoritmo
 determinare la complessità computazionale
dell’algoritmo
5
Efficienza di un algoritmo
Tempo
richiesto per
trovare la
soluzione

Quantità di
memoria richiesta
per i dati del
problema
Dimensione dell’istanza del problema
(Numero di variabili, vincoli, grandezza dei dati)
Quantità di informazioni necessarie per
codificare un’istanza
6
Codifica di un’istanza di problema
Esempio: Un problema di PL
Codificare i dati (n+mxn+m coeff.)
ci, i=1,...n; aij, i=1,...,n, j=1,...,m; bj, j=1,...m
Sistema binario (codifica di un numero x):
k+1 bit, con klog2k+1 più 1 bit per il segno
Numeri a precisione finita:
interi e razionali come rapporto tra interi
Codifica Ragionevole
 utilizza almeno 2 simboli
 non introduce dati irrilevanti né richiede una
generazione esponenziale di dati
7
Esempio:
Codifica decimale (ragionevole)
1 cifra (0-9)  10 simboli
10 (2 cifre)  100 simboli
10x10=100 (3 cifre)  1000 simboli
100x10=1000 (4 cifre)  10000 simboli
 mentre il numero di simboli cresce di fattori 10
il numero di cifre cresce come il logaritmo
Esempio:
Codifica unaria (non ragionevole)
1 cifra (1) 1 simbolo
10 decimale (10 cifre) 10 simboli
100 decimale (100 cifre) 100 simboli
1000 decimale (1000 cifre) 10000 simboli
mentre il numero di simboli cresce di fattori 10
il numero di cifre cresce linearmente
8
Esempio: Generazione esponenziale di dati
Problema di decisione difficile:
dato un grafo determinare se esiste un ciclo
hamiltoniano di lunghezza <K.
Problema di decisione semplice:
dati n numeri trovare se esiste un numero <K
(sorting)
Con una codifica non ragionevole (codificare il
grafo e tutti i suoi cicli) si potrebbe trasformare il
problema difficile del ciclo hamiltoniano nel
problema semplice del sorting.
La codifica non è ragionevole perché in essa è
contenuta la generazione delle soluzioni del
problema.
9
Efficienza di un
algoritmo
Tempo richiesto per risolvere
un’istanza del problema
codificata ragionevolmente
Il tempo di calcolo della soluzione è definito in
maniera indipendente dalle caratteristiche del
particolare calcolatore utilizzato.
Tempo di soluzione: numero delle operazioni
elementari necessarie all’algoritmo per risolvere
un’istanza di una dimensione data.
Operazioni
confronti.
elementari:
addizioni,
moltiplicazioni,
10
Definizione
La funzione di complessità nel tempo, f(k), dove
k è la dimensione di un’istanza, è la funzione che
restituisce il massimo numero di operazioni
elementari necessarie ad un algoritmo per risolvere
le istanze di dimensione k di un problema.


La funzione di complessità nel tempo è determinata
per mezzo della worst case analysis.
Un modo alternativo di valutare la complessità è
l’analisi statistica (più complicato).
11
Occorre conoscere solo il comportamento asintotico
(k) della funzione di complessità nel tempo, ossia
l’ordine di f(k)
Definizione
La funzione f(k) è di ordine g(k), indicato come
O(g(k)), se $k’ ed una costante c tali che
f(k)cg(k) per kk’
n
i
p
(k)

c
k
 i
Esempio: un polinomio
è O(kn)
i 0
12
Definizione
Un algoritmo è di tipo polinomiale se ha una
funzione di complessità nel tempo che è O(kp) per
un certo p fissato.
Definizione
Un algoritmo è di tipo esponenziale se non ha
una funzione di complessità nel tempo di tipo
polinomiale.
13
Definizione
Una funzione f(k) è di ordine esponenziale se non è
limitata da alcun polinomio, ossia
c1d1k  f (k)  c 2 dk2
per kk’, c1, c2>0 e d1, d2>1
Classe P
Appartengono alla classe P tutti i problemi di
decisione che possono essere risolti da algoritmi
di tipo polinomiale (Polynomial time algorithm).
I problemi in P sono ben risolti poiché per
essi esiste un algoritmo efficiente
14
Esempio: tre algoritmi su un calcolatore che esegue
una operazione in 10-6s
k
10
30
60
k 2 10  4 s 9  10  4 s 3.6  10  3 s
polinomiale
5
0.1s
24.3s
13m
O(f(k)) k
2k 10  3 s
17.9m
366c esponenziale
Legenda: s=secondi, m=minuti, c=secoli (!)
15
La complessità computazionale non dipende dalla
velocità del calcolatore utilizzato.
Esempio: un calcolatore 1000 volte più veloce (10-9s)
quante operazioni potrebbe eseguire in più per i tre
algoritmi?
10  6
10  9
k2
k5
n
n
3162
. n
3.98  n
2k
n
10  n
16
Esempio:
Sono algoritmi polinomiali gli algoritmi per
determinare il minimo albero ricoprente in un grafo:
Kruskal è O(nlogn), Prim è O(n2)
Il problema (di decisione) dello shortest spanning
tree: “dato un grafo stabilire se esiste un albero
ricoprente di lunghezza <K” è in P
17
Classe NP
Appartengono alla classe NP tutti i problemi di
decisione per cui, essendo nota una soluzione, è
possibile verificare in tempo polinomiale che la
risposta è affermativa (Non deterministic
Polynomial time algorithm)
La codifica di una soluzione è detta
certificato di ammissibilità
18
Esempio:
Problema:
Dato il grafo G, esiste un circuito hamiltoniano di
lunghezza <K?
Risposta:
Si
Certificato di ammissibilità:
Una sequenza di nodi del grafo
Verifica:
Seguire la sequenza dei nodi verificando che
corrisponde ad un circuito hamiltoniano di
lunghezza <K (polinomiale)
19
I problemi NP sono quelli che sono risolvibili da un
algoritmo di tipo polinomiale non deterministico (Non
deterministic Polynomial time algorithm).
Un algoritmo NP:
Guessing stage) Un oracolo “indovina” la soluzione
(non deterministico)
Checking stage) Verifica in tempo polinomiale della
soluzione
(ovviamente nella realtà non esistono tali algoritmi)
PNP
Congettura
PNP
NP
P
20
Esempi di problemi di decisione

Shortest spanning tree: è P e NP
 PL (determinare se esiste una soluzione >K): è NP
e dal 1979 è stato provato che è P (algoritmo
dell’ellissoide)
 Ciclo hamiltoniano di lunghezza <K: è NP ma non è
stato provato che sia in P
21
Problemi di decisione e problemi di
ottimizzazione

Le definizioni della teoria della complessità fanno
riferimento a problemi di decisione.

Quanto detto si può estendere ai problemi di
ottimizzazione
un algoritmo che risolve un problema di
decisione può essere utilizzato all’interno di un
algoritmo di tipo polinomiale per risolvere il
corrispondente problema di ottimizzazione.
22
Esempio:
Problema di decisione (CH(k))
Dato il grafo G, esiste un circuito hamiltoniano di
lunghezza <K?
Problema di ottimizzazione (TSP)
Determinare il ciclo hamiltoniano di G di lunghezza
minima.
23
Sia S l’algoritmo per risolvere CH(k).
L’algoritmo per risolvere TSP può essere costituito
dalla seguente procedura dicotomica:
1. Siano A e B la minima e massima lunghezza degli
archi di G ed m il numero di nodi di G.
Allora mAlunghezza circuto hamiltonianomB
Porre k= m(B-A)/2
2. Usare S per risolvere CH(k).
3. Se la risposta di S è si, porre k=k/2 altrimenti
k=k(3/2) ed andare a 2.
Poichè i coefficienti sono interi, al più ci saranno
(log(m(B-A))+1 iterazioni.
24
Problema Complementare
I problemi complementari (co-problemi) sono quelli per
cui viene formulata una domanda in termini “negati”.
Esempio:
Il problema complementare del ciclo hamiltoniano di
lunghezza<K:
“Dato il grafo G, è vero che non esistono cicli
hamiltoniano di lunghezza <K?”
25
I problemi complementari dei problemi in P sono
ancora in P.
Congettura
P=co-P
NPco-NP  PNP  co-NP
NP
P
co-NP
Esempio:
Il certificato di ammissibilità per il problema
complementare del ciclo hamiltoniano:
la lista di tutti i possibili cicli hamiltoniani
per un grafo completo con m nodi è pari a m! 
esponenziale quindi non verificabile in tempo
polinomiale
26
Trasformazioni ed NP-completezza
Definizione
Si definiscono come problemi più difficili di una
classe quei problemi appartenenti alla classe che
risultano almeno difficili quanto ogni altro
Se
si riuscisse a risolvere efficientemente uno dei
problemi più difficili allora si potrebbero risolvere
efficientemente anche tutti gli altri problemi della
classe
27
Trasformazione polinomiale
E’ un algoritmo che, data un’istanza I di un
problema p, produce in tempo polinomiale
un’istanza I’ di un problema p’ in modo tale che,
se la risposta è “SI” per I, allora la risposta è “SI”
anche per I’
La trasformazione polinomiale di p a p’
pp’
(p ridotto a p’)
Le trasformazioni polinomiali sono transitive
28
Classe NP-C (NP-Completi)
Appartengono alla classe NP-C tutti i problemi di
decisione della classe NP che sono almeno difficili
quanto ogni altro problema in NP.
Il problema p è NP-C se "p’NP, è possibile pp
I problemi NP-C sono quelli a cui possono essere
ridotti con una trasformazione polinomiale tutti i
problemi in NP
29
Conseguenze:

Se fosse possibile risolvere efficientemente un
pNP-C allora tutti i problemi NP sarebbero stati
risolti efficientemente.

Per dimostrare P=NP basterebbe provare che un
solo problema NP-C è P
NP
NP-C
P
co-NP
30
Il problema della soddisfacilità (SAT)
E’ stato il primo problema NP di cui è stata dimostrata
l’appartenenza ad NP-C
SAT Problem
Data un’espressione booleana in forma congiuntiva
normale in n variabili, x1,..., xn, e loro complementi,
dire se l’espressione è soddisfacibile.
Forma congiuntiva normale: un AND di OR:
  y1i ... yhi 
K
i 1
con y ji  x1,..., xn , x1,..., xn 
dove le espressioni in parentesi sono clausole di
cardinalità h
31
Esempio: Data
E x1x2 x4 x1 x2 (x4)x1x3  x4 x2  x3 x4
dire se esiste un’assegnazione VERO-FALSO alle
variabili per cui E=VERO.
Teorema di Cook (1971)
Il problema SAT è NP-C se h3.
Per dimostrare che pNP è tale che pNP-C, per la
transitività di  è sufficiente dimostrare che un p‘NP-C
(ad esempio, SAT) si riduce ad esso, pp.
32
Estensione ai problemi di ottimizzazione.
Problemi NP-hard
Un problema è NP-hard se esiste un problema
NP-C che può essere ridotto ad esso con una
trasformazione polinomiale.
33

Sono NP-hard problemi (anche non NP) almeno
difficili quanto ogni problema NP-C.

Se pNP-C per alcune delle sue istanze (le più
grandi) non potrà essere trovata la soluzione ottima
in un tempo accettabile per mezzo di algoritmi esatti
(enumerazione esplicita o implicita).

In
generale
è
possibili
determinare
soluzioni
accettabili per pNP-C per mezzo di
 algoritmi
approssimati (soluzioni sub-ottime)
 algoritmi
euristici
34
Esempi di problemi
Problemi P
 Programmazione Lineare Continua
 Matching
 Min Spanning Tree
3
2
 Shortest Path (Dijkstra O(m ), Bellman-Ford O(m ))
 Sistemi equazioni lineari
Problemi NP-C
 Travelling Salesman Problem
 SAT
 Set partitioning, packing, covering
 0-1 Integer programming
 Knapsack
35