Teoria degli algoritmi e della computabilità Approfondimento: Un altro modo di definire la classe...

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 ProiettiEmail: [email protected]

URL: www.di.univaq.it/~proietti/index_personal

1

http://www.di.univaq.it/~proietti/index_personal

2

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.

PRIMES: X = { 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, …. }Algoritmo. [Agrawal-Kayal-Saxena, 2002] p(|s|) = |s|8.

lunghezza di s(dimensione dell’istanza)

3

Definizione di P

P. problemi di decisione per i quali esiste algoritmo polinomiale.

Problema Descrizione Algoritmo Sì No

Cammino minimo

C’è un cammino da x a y lungo al più 10?

Dijkstra; Bellman-Ford

Ciclo Euleriano

Ammette G un ciclo Euleriano?

Eulero

PRIMES Is x prime? AKS (2002) 53 51

EDIT-DISTANCE

È la distanza di edit fra x e y al più 5?

Programmazionedinamica

GaberHaber

acgggt ttttta

Max Matchingc’è un matching di

dimensione almeno 2?Edmonds

x

y6

45

997

x

y6

47

997

4

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.

NP. problemi di decisione per i quali esiste un certifier polinomiale

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.

C(s, t) è un algoritmo polinomiale e|t| p(|s|) per un qualche polinomio p().

certificato

5

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.

Conclusione. SAT appartiene a NP.

istanza s

certificato t

6

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

Certifier e Certificati: ciclo Hamiltoniano

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

Certifier e Certificati: 3-Colorabilità

8

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.

9

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.

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.

EXP NP

P

se P NP se P = NP

EXP

P = NP

romperebbe protocollo crittografico RSA (e potenzialmente farebbe collassare l’economia)

NP-Completezza

11

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.

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?

richiediamo che |y| sia polinomiale in |x|

abusiamo la notazione p

e non facciamo distinzione

12

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?

13

Il “primo" problema NP-Completo

Teorema. SAT è NP-completo. [Cook 1971, Levin 1973]

14

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. Quindi Y è NP-completo. ▪ per assunzioneper def di

NP-completo

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 (a1a2) sostituita in ’ con (a1a2 y ) ( y a1a2)

clausula in della forma: (a1a2…ak)

sostituita in ’ con (a1a2y1) (y1a3y2) (y2a4y3) …(yk-3ak-1ak)

claim: è soddisfacibile sse ’ è soddisfacibile

16

17

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.

v

a

b

c

d

evin

aout

bout

cout

din

ein

G G'

v vout

18

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). ▪

19

Claim. 3-SAT P DIR-HAM-CYCLE.

Dim. data un’istanza di 3-SAT, costruiamo un’istanza di DIR-

HAM-CYCLE 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à.

3-SAT si riduce a Directed Hamiltonian Cycle

20


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

t

3k + 3

x1

x2

x3

21


Costruzione. data un’istanza di 3-SAT con n variabili xi e k

clausule. per ogni clausula: aggiungi un nodo e 6 archi.

s

t

nodo-clausulanodo-clausula

x1

x2

x3

22


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.

23


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 '

inG - { 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. ▪

24

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:

l’istanza di TSP ha un tour di lunghezza n sse G è Hamiltoniano. ▪

Osservazione. l’istanza di TSP nella riduzione soddisfa la disuguaglianza triangolare.

d(u, v) 1 if (u, v) E

2 if (u, v) E

25

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



Tardos COS 523 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

26


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.

27


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.

x1x3x2

core

xi = vero

xi = falso

k: numero di clausule

k = 2 clausesn = 3 variables

true

false

clause 1 tips

28


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.

x1x3x2

clause 1 tips core

C j x1 x2 x3

true

false

gadget clausula 1

29


Costruzione. (parte 3) aggiungi k(n-1) cleanup gadget ogni cleanup gadget è formato da due elementi e 2kn triple, una

per ogni tip.

x1x3x2

core

cleanup gadget

true

false

clause 1 tips

gadget clausula 1

30


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?

x1x3x2

core

cleanup gadget

true

false

clause 1 tips

gadget clausula 1

31


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?

x1x3x2

core

cleanup gadget

clause 1 tips

gadget clausula 1

32

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.

33

My Hobby

Randall Munrohttp://xkcd.com/c287.html

34

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.

Claim. 3D-matching sse un qualche sottoinsieme somma a W = 111,…, 111.

100,010,001

1,010,001,000

1,010,000,010

1,010,000,100

10,001,000,001

100,010,001,000

10,000,010,100

100,001,000,010

100,100,001

x2 y2 z4

x4 y3 z4

x3 y1 z2

x3 y1 z3

x3 y1 z1

x4 y4 z4

x1 y2 z3

x2 y4 z2

x1 y1 z1

Triplet ti wi

0 0 0 1 0 0 0 1 0 0 0 1

0 0 1 0 1 0 0 0 1 0 0 0

0 0 1 0 1 0 0 0 0 0 1 0

0 0 1 0 1 0 0 0 0 1 0 0

0 1 0 0 0 1 0 0 0 0 0 1

1 0 0 0 1 0 0 0 1 0 0 0

0 1 0 0 0 0 0 1 0 1 0 0

1 0 0 0 0 1 0 0 0 0 1 0

0 0 0 1 0 0 1 0 0 0 0 1

x1 x2 x3 x4 y1 y2 y3 y4 z1 z2 z3 z4

111,111,111,111

cosiderato in base m+1

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.

riassumendo: una parziale tassonomia dei problemi

36

Osservazione. tutti i problemi sotto sono NP-completi polinomialmente riducibili l’uno all’altro!

SAT

3-SAT

DIR-HAM-CYCLEINDEPENDENT SET

VERTEX COVER

3-SAT si riduce a

INDEPENDENT SET

HAM-CYCLE

TSP

3D-Matching

SUBSET-SUM

SET COVER

NP-Completezza

per definizione di NP-completenzza

co-NP e l’asimmetria di NP

38

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

39

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.

40

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.

NP = co-NP ?

Teoria degli algoritmi e della computabilità Approfondimento: Un altro modo di definire la classe...

Documents

Transcript of Teoria degli algoritmi e della computabilità Approfondimento: Un altro modo di definire la classe...