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
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 = U
c≥0Time(n
c)
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.
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(a
p(n)), dove a>1 è una costante e p(n) è un polinomio in n; più formalmente, tenendo conto del fatto che a
p(n)= (2
log a)
p(n)= 2
log a (p(n))= 2
q(n), e che un polinomio di grado c è O(n
c), si può scrivere:
ExpTime=U
c≥0Time ( 2
(nc))
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.
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.
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
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
Esempio (2)
Per la formula: (x
1 x
2) (x
1 x
2 x
3) x
1x
2x
2x
3x
3x
3x
3T F
T F T F
T F T F T F T F
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 = U
c≥0NTime(n
c)
• SAT appartiene a NTime(n), e quindi SAT appartiene a
NP
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)
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…
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])
Gerarchia delle classi
Decidibili
ExpTime
(ARRESTO(k)) P (ricerca)
NP NP-completi (SAT)
Congettura P ≠ NP
