Didattica e Fondamenti degli
Algoritmi e della Calcolabilità
Terza giornata: principali classi di
complessità computazionale dei problemi
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
La classe P
La classe P è la classe dei problemi decidibili su
una RAM in tempo polinomiale nella dimensione n
dell’istanza di ingresso:
P = Uc≥0 Time(nc)
La classe P contiene i problemi «facili» da risolvere, in quanto una
risoluzione in tempo polinomiale, considerata la velocità di un
calcolatore, richiede pochi secondi anche se la dimensione
dell’istanza divente grande, purché il polinomio non abbia grado
troppo elevato! Si dà però il caso che tutti i problemi naturali
risolvibili in tempo polinomiale siano dominati da O(n4), e anzi la
stragrande maggioranza di essi è dominata da O(n2).
Esempi di problemi polinomiali: ordinamento, ricerca, prodotto di
matrici, cammini minimi su un grafo, etc. etc. etc.
2
La classe ExpTime
La classe ExpTime è invece la classe dei problemi decidibili su
una RAM in tempo esponenziale nella dimensione n dell’istanza di
ingresso, ovvero in O(ap(n)), dove a>1 è una costante e p(n) è un
polinomio in n; più formalmente, tenendo conto del fatto che ap(n)=
(2log a) p(n)= 2 log a (p(n)) = 2q(n), e che un polinomio di grado c è O(nc),
si può scrivere:
ExpTime=Uc≥0Time(
c
(n
2 )
)
Chiaramente, P ⊑ ExpTime
Si può dimostrare che l’inclusione è propria, cioè esistono
problemi in ExpTime che non appartengono a P: uno di questi
problemi è quello di verificare se dato un generico algoritmo, esso
si arresta o meno su un generico input in al più k passi, con k
fissato.
3
Un altro problema in ExpTime: SAT
Data un’espressione booleana in forma normale congiuntiva, cioè come
congiunzione (operatore logico AND) di un insieme di clausole, in cui ogni
clausola è la disgiunzione (operatore logico OR) di un certo insieme di
variabili booleane (ovvero, che possono assumere valore TRUE o FALSE) o
di loro negazioni, il problema della soddisfacibilità (SAT) richiede di
verificare se esiste un’assegnazione di valori di verità alle variabili che
rende l’espressione TRUE.
Es.: (x1  x2)  (x1  x2  x3) è soddisfacibile: basta scegliere
x1=x2=TRUE e x3 arbitrario.
Es.: (x1  x2)  (x1  x2)  (x1   x2)  (x1   x2) non è soddisfacibile.
Verificatelo…
È facile convincersi che SAT appartiene ad ExpTime, in quanto può essere
risolto provando le 2n possibili assegnazioni di verità alle n variabili. Ma la
vera domanda è: SAT appartiene a P? Sembra incredibile, ma non siamo in
grado di dare una risposta a questa semplice domanda, anche se si
congettura che la risposta sia NO.
4
Non determinismo
•
•
•
•
Negli algoritmi visti finora ogni passo è determinato univocamente dallo
stato della computazione; vengono quindi detti deterministici. Tale
ipotesi dipende dal modello di calcolo che abbiamo adottato (che può
eseguire solo operazioni aritmetiche e logiche elementari).
Supponiamo ora di avere un modello di calcolo (apparentemente) più
potente, ovvero una macchina non deterministica che ci consenta, ad
ogni passo dell’esecuzione di un algoritmo, di proseguire la
computazione lungo un numero finito di esecuzioni multiple. Si noti che
stiamo parlando di un modello di calcolo astratto, che non esiste nella
realtà!
Un algoritmo non deterministico è un algoritmo che ha il potere, ad ogni
istante della computazione non deterministica, di indovinare
l’esecuzione giusta lungo cui proseguire per arrivare alla risoluzione del
problema, attraverso un’operazione virtuale denominata INDOVINA.
Chiamiamo RAM non deterministica una RAM che riconosce algoritmi
non deterministici
5
Esempio
Come potrebbe funzionare un algoritmo non
deterministico per SAT?
– Indovina ad ogni passo il valore giusto da
assegnare ad una variabile (TRUE o FALSE)
– La computazione sarà descritta da un albero
binario, dove le ramificazioni corrispondono alle
scelte non deterministiche (la computazione
deterministica è invece descritta da una
catena)
– Quindi se la formula è soddisfacibile, esiste
almeno un cammino che porta a una foglia con
valore TRUE. Si noti che tale cammino è lungo n
6
Esempio (2)
Per la formula: (x1  x2)  (x1  x2  x3)
x1
T
T
T
x3
x2
F
T
F
T
F
x3
F T
x3
x2
F T
F
x3
F
7
La classe NP
• Data una qualunque funzione f(n), chiamiamo
NTime(f(n)) l’insiemi dei problemi che possono
essere decisi su una RAM non deterministica
(ovvero in grado di riconoscere algoritmi non
deterministici) in tempo O(f(n))
• La classe NP è la classe dei problemi che possono
essere decisi su una RAM non deterministica in
tempo polinomiale nella dimensione n dell’istanza
di ingresso:
NP = Uc≥0 NTime(nc)
• SAT appartiene a NTime(n), e quindi SAT
appartiene a NP
8
Gerarchia delle classi
P è incluso in NP oppure no?
– Ovviamente sì: un algoritmo deterministico
è un caso particolare di un algoritmo non
deterministico, in cui però le computazioni
non si ramificano
– L’inclusione è propria? Non si sa, e questo è
uno dei 6 problemi matematici aperti la cui
risoluzione vi farà vincere 1 Milione di
Dollari! (si veda Wikipedia)
9
Gerarchia delle classi (2)
NP è incluso in ExpTime oppure no?
– Ovviamente sì: un algoritmo non
deterministico può essere ‘’simulato’’ da un
algoritmo deterministico che esplora una
dopo l’altra tutte le computazioni
ramificate in tempo esponenziale
– L’inclusione è propria? Non si sa…
10
Gerarchia delle classi (3)
• Quindi abbiamo
P ⊑ NP ⊑ ExpTime, con P ≠ ExpTime
• Si congettura che tutte le inclusioni siano proprie
• In NP c’è una classe molto speciale di problemi che
sicuramente non apparterrebbero a P se fosse NP ≠ P: i
problemi NP-completi
• Questi sono quindi esattamente i problemi per i quali non
siamo in grado di esibire un algoritmo risolutivo polinomiale!
Sfortunatamente, moltissimi problemi computazionali con cui
ci confrontiamo quotidianamente, sono NP-completi!
• Si può dimostrare che SAT è NP-completo (più
precisamente, è stato il primo problema per cui si è provata
la NP-completezza [Stephen Cook, 1971])
11
Gerarchia delle classi
Decidibili
P (ricerca)
NP
ExpTime
(ARRESTO(k))
NP-completi (SAT)
Congettura P ≠ NP
12
Altri famosi problemi NP-completi
• Commesso viaggiatore
– Dati un grafo completo G con pesi reali sugli
archi ed un valore reale k, verificare se esiste
un ciclo in G di peso al più k che attraversa ogni
vertice una ed una sola volta
• Colorazione
– Dati un grafo G ed un intero k, verificare se è
possibile colorare i vertici di G con al più k
colori tali che due vertici adiacenti non siano
dello stesso colore
13
Altri famosi problemi NP-completi (2)
• Somme di sottoinsiemi
– Dati un insieme S di numeri naturali ed un intero
t, verificare se esiste un sottoinsieme di S i cui
elementi sommano esattamente a t
• Zaino
– Dati un intero k, uno zaino di capacità c, e n
oggetti di dimensioni s1, …., sn cui sono associati
profitti p1, …., pn, bisogna verificare se esiste un
sottoinsieme degli oggetti di dimensione ≤c che
garantisca profitto ≥k
14