Teoria degli algoritmi e della
computabilità
Approfondimento: Un altro modo di definire la
classe NP: il concetto di certificato. La classe
dei problemi NP-completi ed esempi di riduzioni
(materiale predisposto in collaborazione con Luciano Gualà,
Università di Roma ‘’Tor Vergata’’)
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
Problemi di decisione
(visti come linguaggi)
Problema di decisione
X: insieme di stringhe (parole).
Istanza: stringa s.
Algoritmo A che risolve il problema X: A(s) = yes sse s  X.



Polinomialità temporale. Algoritmo A è polinomiale se per ogni stringa s,
A(s) termina in al più p(|s|) passi elementari, dove p() è un qualche
polinomio.
lunghezza di s
(dimensione dell’istanza)
PRIMES: X = { 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, …. }
Algoritmo. [Agrawal-Kayal-Saxena, 2002] p(|s|) = |s|8.
2
Definizione di P
P. problemi di decisione per i quali esiste algoritmo polinomiale.
Problema
Descrizione
Algoritmo
Sì
No
4
x
5
4
x
7
Cammino
minimo
C’è un cammino da x a y lungo al
più 10?
Dijkstra; BellmanFord
Ciclo Euleriano
Ammette G un ciclo Euleriano?
Eulero
PRIMES
Is x prime?
AKS (2002)
53
51
EDITDISTANCE
È la distanza di edit fra x e y al
più 5?
Programmazione
dinamica
Gaber
Haber
acgggt
ttttta
Max Matching
c’è un matching di dimensione
almeno 2?
Edmonds
9
6
7
9
y
9
6
7
9
y
3
la classe NP
Il Certifier (Certificatore): intuizione
Certifier vede le cose da un punto di vista "manageriale”
Certifier non determina se s  X da solo;
invece verifica usando una certa “prova” t che s  X.


Def. Algoritmo C(s, t) è un certifier per un problema X se per ogni
stringa s  X esiste una stringa t tale che C(s, t) = yes.
certificato
NP. problemi di decisione per i quali esiste un certifier polinomiale
C(s, t) è un algoritmo polinomiale e
|t|  p(|s|) per un qualche polinomio p().
Osservazione. NP sta per ”nondeterministic polynomial-time”.
Una definizione equivalente di NP: linguaggi che possono essere decisi
in tempo polinomiale da macchine di Turing non deterministiche.
4
Certifier e certificati: SAT
SAT. data una formula  in FNC, c’è un assegnamento di verità che la
soddisfa?
Certificato. un assegnamento di verità per le n variabili booleane.
Certifier. verifica che ogni clausula di  ha almeno un letterale vero.
Ex.
 x1
 x2  x3  
 x1
 x2  x3  
 x1
 x2  x4   x1  x3  x4 
istanza s

x1  1, x2  1, x3  0, x4  1
certificato t

Conclusione. SAT appartiene a NP.
5
Certifier e Certificati: ciclo Hamiltoniano
HAM-CYCLE. Dato un grafo non diretto G = (V, E), c’è un ciclo C che
visita tutti i nodi una e una sola volta?
Certificato. Una permutazione degli n nodi.
Certifier. Verifica che la permutazione contiene tutti i nodi di V
esattamente una volta, e che c’è un arco fra ogni coppia di nodi
adiacenti della permutazione.
Conclusione. HAM-CYCLE appartiene a NP.
instanza s
certificato t
6
Certifier e Certificati: 3-Colorabilità
3-COL. dato un grafo non diretto G = (V, E), si possono colorare i suoi nodi con
tre colori in modo che due nodi adiacenti abbiamo sempre colori diversi?
Certificato. Una colorazione dei nodi.
Certifier. Verifica che la colorazione usa solo tre colori, e che per ogni arco
di G i suoi estremi hanno colori diversi.
Conclusione. 3-COL appartiene a NP.
instanza s
certificato t
P, NP, EXP
P. Problemi di decisione per i quali c’è un algoritmo polinomiale.
EXP. Problemi di decisione per i quali c’è un algoritmo esponenziale.
NP. Problemi di decisione per i quali c’è un certifier polinomiale.
Claim. P  NP.
Pf. Considera un qualsiasi problema X in P.
per definizione, c’è un algoritmo polinomiale A(s) che risolve X.
Certificato: t =  (stringa vuota), certifier C(s, t) = A(s).


Claim. NP  EXP.
Pf. Considera un qualsiasi problema X in NP.
per definizione, c’è un Certifier polinomiale C(s, t) per X.
Per risolvere istanza s, esegui C(s, t) per tutte le stringhe t con
|t|  p(|s|).
Return yes, se C(s, t) returns yes per una qualsiasi delle stringhe t.



8
P Versus NP
P = NP? [Cook 1971, Edmonds, Levin, Yablonski, Gödel]
Trovare una soluzione è altrettanto facile che verificarne una data?
Fondazione Clay ha messo in palio premio da $1.000.000.


NP
EXP
EXP
P
P = NP
se P  NP
se P = NP
romperebbe protocollo crittografico RSA (e
potenzialmente farebbe collassare l’economia)
Se sì: algoritmi efficienti per 3-COLOR, TSP, FACTOR, SAT, …
Se no: nessuna algoritmo efficiente per 3-COLOR, TSP, SAT, …
Opinione condivisa su P = NP? Probabilmente no.
9
NP-Completezza
Riduzione polinomiale
Def. Problema X si riduce polinomialmente (Cook) al problema Y se
istanze generiche del problema X possono essere risolte usando:
numero polinomiale di passi elementari, più
numero polinomiale di chiamate a un oracolo che risolve il problema Y


Def. Problema X si riduce polinomialmente (Karp) al problema Y se per
ogni istanza x di X, possiamo costruire in tempo polinomiale un’istanza y
di Y tale che x è un’istanza yes di X sse y è un’istanza yes di Y.
richiediamo che |y| sia polinomiale in |x|
Nota. Riduzione secondo Karp è un caso particolare di Cook riduzione
con una sola chiamata all’oracolo di Y esattamente alla fine
dell’algoritmo per X. (Riduzioni viste sono tutte di questa forma.)
Problema aperto. sono lo stesso concetto rispetto a NP?
abusiamo la notazione  p
e non facciamo distinzione
11
problemi NP-Completi
NP-completo. Un problema Y in NP con la proprietà che per ogni altro
problema X in NP, X  p Y.
Teorema. Sia Y un problema NP-completo. Allora Y può essere risolto in
tempo polinomiale sse P = NP.
dim.  se P = NP allora Y può essere risolto in tempo polinomiale
poiché Y appartiente a NP.
dim.  se Y può essere risolto in tempo polinomiale:
sia X un qualsiasi problema in NP. Poiché X  p Y, possiamo risolvere
X in tempo polinomiale. Questo implica che NP  P.
ma sappiamo già che P  NP. Quindi P = NP. ▪


Questione fondamentale. esiste almeno un problema NP-completo?
12
Il “primo" problema NP-Completo
Teorema. SAT è NP-completo. [Cook 1971, Levin 1973]
13
dimostrare NP-Completezza di un problema
Osservazione. Una volta trovato il primo problema
NP-completo, gli altri si dimostrano per riduzione.
Strategia per stabilire NP-completezza di un problema Y.
Step 1. mostra che Y è in NP.
Step 2. scegli un problema X NP-completo.
Step 3. dimostra che X  p Y.



claim. se X è NP-completo e Y è in NP con la proprietà che
X  P Y allora Y è NP-completo.
Dim. sia W un qualsiasi problema in NP. Allora W  P X  P Y.
per transitività: W  P Y.
per def di
per assunzione
Quindi Y è NP-completo. ▪


NP-completo
14
Ancora qualche riduzione
(carina)
SAT si riduce a 3-SAT
claim: SAT  P3-SAT
costruizione. Idea: data un’istanza  di SAT, costruisco un’istanza ’
equivalente di 3-SAT rendendo le clausule tutte di lunghezza 3. Lo faccio
aggiungendo (un numero polinomiale di) variabili ausiliarie e clausule.
clausula in  della forma (a1a2) sostituita in ’ con (a1a2 y ) ( y a1a2)
clausula in  della forma:
(a1a2…ak)
sostituita in ’ con
(a1a2y1) (y1a3y2) (y2a4y3) …(yk-3ak-1ak)
claim:  è soddisfacibile sse ’ è soddisfacibile
16
Directed Hamiltonian Cycle
DIR-HAM-CYCLE: dato un grafo diretto G = (V, E), esiste un cammino
diretto  che passa per tutti i nodi V una e una sola volta?
Claim. DIR-HAM-CYCLE  P HAM-CYCLE.
Pf. dato un grafo diretto G = (V, E), costruiamo un grafo non diretto G'
con 3n nodi.
aout
a
din
d
b
v
e
c
G
bout
cout
vin
v
vout
ein
G'
17
Directed Hamiltonian Cycle
Claim. G ha un ciclo (diretto) Hamiltoniano sse G' ha ciclo Hamiltoniano
(non diretto).
dim. 
Supponi G ha ciclo Hamiltoniano diretto .
Allora G' ha ciclo Hamiltoniano non diretto (stesso ordine dei nodi).


dim. 
Supponi G' ha ciclo Hamiltoniano non diretto '.
' deve visitare i nodi di G' in uno dei sguenti due ordini :
…, B, V, R, B, V, R, B, V, R, B, …
…, B, R, V, B, R, V, B, R, V, B, …
i nodi blu in ' formano un ciclo Hamiltoniano diretto  in G (in uno
dei due ordini). ▪



18
3-SAT si riduce a Directed Hamiltonian Cycle
Claim. 3-SAT  P DIR-HAM-CYCLE.
Dim. data un’istanza  di 3-SAT, costruiamo un’istanza di DIR-HAMCYCLE che ha un ciclo Hamiltoniano sse  è soddisfacibile.
Construction. Prima creiamo un grafo che ha 2n cicli Hamiltoniani che
corrispondono in modo naturale alle 2n possibili assegnamenti di
verità.
19
3-SAT si riduce a Directed Hamiltonian Cycle
Construzione. data un’istanza  di 3-SAT con n variabili xi e k clausule.
Costruisci G in modo che abbia 2n cicli Hamiltoniani.
Intuizione: attraversare il cammino i da sinistra a destra
 metto la variabile xi = 1.


s
x1
x2
x3
t
3k + 3
20
3-SAT si riduce a Directed Hamiltonian Cycle
Costruzione. data un’istanza  di 3-SAT con n variabili xi e k clausule.
per ogni clausula: aggiungi un nodo e 6 archi.

C1  x1 V x2 V x3
nodo-clausula C2  x1 V x2 V x3
nodo-clausula
s
x1
x2
x3
t
21
3-SAT si riduce a Directed Hamiltonian Cycle
Claim.  è soddisfacibile sse G ha un ciclo Hamiltoniano.
dim. 
supponi istanza 3-SAT ha un assegnamento x* che soddisfa  .
Allora, definisci ciclo Hamiltoniano in G come segue:
– se x*i = 1, attraversa riga i da sinistra a destra
– se x*i = 0, attraversa riga i da destra a sinistra
– per ogni clausula Cj , ci sarà almeno una riga i nella quale stiamo
andando nella direzione "corretta" per inserire il nodo Cj nel ciclo.


22
3-SAT si riduce a Directed Hamiltonian Cycle
Claim.  è soddisfacibile sse G ha un ciclo Hamiltoniano.
dim. 
Supponi G ha ciclo Hamiltoniano .
se  entra nel nodo-clausula Cj , deve uscire dall’arco “compagno” di
quello da cui è entrato.
– perciò, nodi immediatamente prima e dopo Cj sono collegati da un
arco e in G
– rimovendo Cj dal ciclo, e rimpiazzandolo con l’arco otteniamo un
ciclo Hamiltoniano di G - { Cj }
Continuando in questo modo, otteniamo un ciclo Hamiltoniano ' in
G - { C1 , C2 , . . . , Ck }.
Imposta x*i = 1 sse ' attraversa riga i da sinistra a destra.
poiché  visita ogni nodo-clausula Cj , almeno uno dei cammini è
attraversato nella direzione "corretta", e tutte le clausule sono
soddisfatte. ▪





23
Traveling Salesperson Problem
TSP. dato un insieme di n città con relative distaze coppia-coppia d(u,v),
c’è un tour di lunghezza  D?
HAM-CYCLE: dato un grafo G = (V, E), c’è un ciclo semplice che passa una
e una sola volta per tutti i nodi di V?
Claim. HAM-CYCLE  P TSP.
dim.
data un’istanza G = (V, E) di HAM-CYCLE, crea n città la cui distanze
sono:
 1 if (u, v)  E
d(u, v)  
 2 if (u, v)  E


l’istanza di TSP ha un tour di lunghezza  n sse G è Hamiltoniano. ▪

Osservazione. l’istanza di TSP nella riduzione soddisfa la disuguaglianza
triangolare.
24
3-Dimensional Matching
3D-MATCHING. dati n docenti, n corsi, and n orari, e una lista di
possibili corsi e orari che ogni docente è disposto a insegnare, è
possibile assegnare un corso a ogni docente in modo che i corsi
abbiano tutti orari diversi?
Instructor
Course
Time
Wayne
COS 423
MW 11-12:20
Wayne
COS 423
TTh 11-12:20
Wayne
COS 226
TTh 11-12:20
Wayne
COS 126
TTh 11-12:20
Tardos
COS 523
TTh 3-4:20
Tardos
COS 423
TTh 11-12:20
Tardos
COS 423
TTh 3-4:20
Kleinberg
COS 226
TTh 3-4:20
Kleinberg
COS 226
MW 11-12:20
Kleinberg
COS 423
MW 11-12:20
25
3-Dimensional Matching
3D-MATCHING. dati tre insiemi disgiunti X, Y, e Z, ognuno di dimensione
n e un insieme T  X  Y  Z di triple, esiste un insieme di n triple in
T tale che ogni elemento di X  Y  Z è in esattamente una di
queste triple?
Claim. 3-SAT  P 3D-MATCHING.
Pf. data un’istanza  di 3-SAT, costruiamo un’istanza di 3D-matching
che ha un perfect matching sse  è soddisfacibile.
26
3-Dimensional Matching
k: numero di clausule
Costruzione. (parte 1)
Crea gadget per ogni variabile xi con 2k elementi core e 2k elementi tip.
Nessun’altra tripla conterà elementi core.
nel gadget i, 3D-matching deve usare o entrambe le triple grigie o
entrambe le triple blue.



xi = vero
xi = falso
false
clause 1 tips
core
true
k = 2 clauses
n = 3 variables x
1
x2
x3
27
3-Dimensional Matching
Costruzione. (parte 2)
per ogni clausula Cj crea due elementi e tre triple.
esattamente una di queste tre triple sarà usata in un generico 3D-matching.
assicura che un generico 3D-matching usa o (i) triple grigie di x1 o (ii) triple
blu di x2 o (iii) triple grigie di x3.



gadget clausula 1
false
clause 1 tips
C j  x1  x2  x3

core
true
x1
x2
x3
28
3-Dimensional Matching
Costruzione. (parte 3)
aggiungi k(n-1) cleanup gadget
ogni cleanup gadget è formato da due elementi e 2kn triple, una per
ogni tip.


gadget clausula 1
cleanup gadget
false
clause 1 tips
core
true
x1
x2
x3
29
3-Dimensional Matching
Claim. l’istanza ha un 3D-matching sse  is soddisfacibile.
Dettagli. Quali sono X, Y, e Z? Contiene ogni tripla un elemento da X
uno da Y e uno da Z?
gadget clausula 1
cleanup gadget
false
clause 1 tips
core
true
x1
x2
x3
30
3-Dimensional Matching
Claim. l’istanza ha un 3D-matching sse  is soddisfacibile.
Dettagli. Quali sono X, Y, e Z? Contiene ogni tripla un elemento da X
uno da Y e uno da Z?
gadget clausula 1
cleanup gadget
clause 1 tips
core
x1
x2
x3
31
Subset Sum
SUBSET-SUM. dato un insieme di numeri naturali w1, …, wn e un intero W,
c’è un sottoinsieme dei numeri che sommano esattamente a W?
Es: { 1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344 }, W = 3754.
Sì. 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754.
Osservazione. Nei problemi numerici, l’istanza è rappresentata in
binario. Una riduzione polinomiale deve essere polinomiale nella
codifica binaria.
Claim. 3D-Matching  P SUBSET-SUM.
32
My Hobby
Randall Munro
http://xkcd.com/c287.html
33
Subset Sum
Construction. Sia X  Y  Z un’istanza di 3D-MATCHING con insieme
di triple T. Sia n = |X| = |Y| = |Z| e m = |T|.
Siano X = { x1, x2, x3 x4 }, Y = { y1, y2, y3, y4 } , Z = { z1, z2, z3, z4 }
per ogni tripla t= (xi, yj, zk )  T, crea un intero wt di 3n cifre che ha
un 1 nelle posizioni i, n+j, e 2n+k.


cosiderato in base m+1
Claim. 3D-matching sse un qualche sottoinsieme somma a W = 111,…, 111.
Triplet ti
x1
x2 x3 x4
y1
y2
y3
y4
z1
z2
z3
z4
wi
x1
y2
z3
1
0
0
0
0
1
0
0
0
0
1
0
100,001,000,010
x2
y4
z2
0
1
0
0
0
0
0
1
0
1
0
0
10,000,010,100
x1
y1
z1
1
0
0
0
1
0
0
0
1
0
0
0
100,010,001,000
x2
y2
z4
0
1
0
0
0
1
0
0
0
0
0
1
10,001,000,001
x4
y3
z4
0
0
0
1
0
0
1
0
0
0
0
1
100,100,001
x3
y1
z2
0
0
1
0
1
0
0
0
0
1
0
0
1,010,000,100
x3
y1
z3
0
0
1
0
1
0
0
0
0
0
1
0
1,010,000,010
x3
y1
z1
0
0
1
0
1
0
0
0
1
0
0
0
1,010,001,000
x4
y4
z4
0
0
0
1
0
0
0
1
0
0
0
1
100,010,001
111,111,111,111
34
riassumendo:
una parziale tassonomia dei problemi
Tipologie:
 Packing problems: SET-PACKING, INDEPENDENT SET.
 Covering problems: SET-COVER, VERTEX-COVER.
 Constraint satisfaction problems: SAT, 3-SAT.
 Sequencing problems: HAMILTONIAN-CYCLE, TSP.
 Partitioning problems: 3D-MATCHING, 3-COLOR.
 Numerical problems: SUBSET-SUM, KNAPSACK.
NP-Completezza
Osservazione. tutti i problemi sotto sono NP-completi polinomialmente
riducibili l’uno all’altro!
SAT
per definizione di NP-completenzza
3-SAT
INDEPENDENT SET
DIR-HAM-CYCLE
3D-Matching
VERTEX COVER
HAM-CYCLE
SUBSET-SUM
SET COVER
TSP
36
co-NP e l’asimmetria di NP
Asimmetria di NP
Asimmetria di NP. Abbiamo solo bisogno di avere certificati corti per
istanze yes.
Es 1. SAT vs. TAUTOLOGY.
possiamo provare che una formula FNC è soddisfacibile fornendo un
assignamento di verità che la rende vera.
come possiamo provare che la formula non è soddisfacibile?


Es 2. HAM-CYCLE vs. NO-HAM-CYCLE.
possiamo provare che un grafo è Hamiltoniano fornendo un ciclo
Hamiltoniano.
come possiamo provare che un grafo non è Hamiltoniano?


Osservazione. SAT è NP-completo e SAT  P TAUTOLOGY, ma come
classifichiamo TAUTOLOGY?
non sappiamo neanche se è in NP
38
NP e co-NP
NP. Problemi di decisione per i quali c’è un certifier polinomiale.
Es. SAT, HAM-CYCLE, COMPOSITES.
Def. dato un problema di decisione X, il suo complemento X è lo stesso
problema con le risposte yes e no invertite.
Es. X = { 0, 1, 4, 6, 8, 9, 10, 12, 14, 15, … }
Ex. X = { 2, 3, 5, 7, 11, 13, 17, 23, 29, … }
co-NP. Complementi dei problemi di decisione in NP.
Ex. TAUTOLOGY, NO-HAM-CYCLE, NO-PRIMES.
39
NP = co-NP ?
Questione fondamentale. NP = co-NP?
Hanno le istanze yes certificati corti sse le hanno le istanze no?
Opinione diffusa: probabilmente no.


Teorema. se NP  co-NP, allora P  NP.
Dim (idea).
P è chiuso rispetto alla complementazione.
se P = NP, allora NP è chiuso rispetto alla complementazione.
In altre parole, NP = co-NP.



40