Teoria degli algoritmi e della computabilità

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

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|⁸.

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?

Programmazione dinamica

Gaber

Haber acgggt ttttta

Max Matching c’è un matching di dimensione

almeno 2? Edmonds

x 6 y

4 5

9 9 7

x 6 y

4 7

9 9 7

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 def di per assunzione 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 (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

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

e v_in

a_out

b_out c_out

d_in

e_in

G G'

v v_out

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 2ⁿ cicli Hamiltoniani che corrispondono in modo naturale alle 2ⁿ possibili assegnamenti di verità.

3-SAT si riduce a Directed Hamiltonian Cycle

20

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 2ⁿ cicli Hamiltoniani.

 Intuizione: attraversare il cammino i da sinistra a destra  metto la variabile xi = 1.

s

t

3k + 3

x₁

x₂

x₃

21

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.

s

t

nodo-clausula nodo-clausula

x₁

x₂

x₃

22

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 C_j , ci sarà almeno una riga i nella quale stiamo andando nella direzione "corretta" per inserire il nodo C_j nel ciclo.

23

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 C_j , deve uscire dall’arco “compagno” di quello da cui è entrato.

– perciò, nodi immediatamente prima e dopo C_j sono collegati da un arco e in G

– rimovendo C_j dal ciclo, e rimpiazzandolo con l’arco otteniamo un ciclo Hamiltoniano di G - { C_j }

 Continuando in questo modo, otteniamo un ciclo Hamiltoniano ' in G - {C₁ , C₂ , . . . , C_k }.

 Imposta x*i = 1 sse ' attraversa riga i da sinistra a destra.

 poiché  visita ogni nodo-clausula C_j , 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

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

26

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.

27

3-Dimensional Matching

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.

x₁ x₂ x₃

core

x_i = vero x_i = falso

k: numero di clausule

k = 2 clauses n = 3 variables

true

false clause 1 tips

28

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.

x₁ x₂ x₃

clause 1 tips core



C_j  x₁  x₂  x₃

true

false

gadget clausula 1

29

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.

x₁ x₂ x₃

core

cleanup gadget

true

false clause 1 tips

gadget clausula 1

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?

x₁ x₂ x₃

core

cleanup gadget

true

false clause 1 tips

gadget clausula 1

31

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?

x₁ x₂ x₃

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 Munro

http://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 x₂ y₂ z₄

x₄ y₃ z₄ x₃ y₁ z₂ x₃ y₁ z₃ x₃ y₁ z₁ x₄ y₄ z₄ x₁ y₂ z₃ x₂ y₄ z₂ x₁ y₁ z₁

Triplet t_i w_i

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

x₁ x₂ x₃ x₄ y₁ y₂ y₃ y₄ z₁ z₂ z₃ z₄

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-CYCLE INDEPENDENT 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 ?