Esempi di problemi NP-Hard Flashcards
(13 cards)
Qual è il Teorema di Cook e perché SAT è NP-hard?
Dice che SAT è NP-hard
L NP, M MdT non det che accetta L per stati finali
supponiamo che per ogni stringa n M esegue esattamente p(n) transizioni
Descrivere proprietà computazione accettante
Set variabili
- S(u,t): 1 istante t, stato qu
- L(i,t): testina su cella i, istante t
- C(i,j,t): cella i ha valore aj all’istante t
i in {1,…, p(n)+1}
t in {0,…, p(n)}
u in {1,…, |Q|}
j in {1,…,|Sigma|}
Modello MdT
1-3)per ogni istante esiste ed è unico stato (unico S(u,t), L(i,t), C(i,j,t)
4) Stato iniziale
5) Stato finale
6) Se testina non è su cella, carattere con cambia
7) S, L, C dipendono da lista di transizioni
Chiamo U polinomio booleano che assume valore 1 esattamente 1 volta
U(y1,…,yk)=(y1 or … or yk) and (and_{i!=j} yi’ or yj’)
Traduco proprietà sopra con U
Per esempio A=and_{0, p(n)} U(s(1,t)…, s(s,t))
Ovvero per ogni t, solo uno stato
Dato w, esso è accettatto solo se tutte le proprietà sono definite
L NP-hard, f rid. pol. da L a Q => Q NP-hard
Sia R NP, g rid. pol da R a L (esiste per hp)
rid. pol. da R a Q
Dato w stringa
- calcolo g(w) R->L
- calcolo f(g(w)) R->L->Q
Che cos’è il problema 3-SAT?
Dato polinomio CNF dove ogni clausola ha esattamente 3 letterali, determinare se esiste assegnamento
Perché 3-SAT è NP-hard?
Descriviamo rid. pol. da SAT a 3-SAT
hp: p pol.bool in 3-CNF, u generica clausola di p -> da u costruiamo ~u pol bool in 3-cnf in modo che u sodd. sse ~u sodd
- u=v (v letterale)
~u=(v or x or y) and (v or x’ or y’) and (v or x’ or y) and (v or x or y’) con x, y variabili nuove (ma che non cambiano risultato) - u=v or w
~u=(v or w or x) and (v or w or x’) - u=v or w or t (duh)
- u=v1 or v2 or … or vn
~u=(v1 or v2 or y1) and (v3 or y1’ or y2’) and (v3 or y1’ or y2) and … and (vn-2 or yn-4’ or yn-3) and (vn-1 or vn or y’n-3)
u sodd <=> ~u sodd
=>) sia V insieme variabili u
soddisfatta quindi esiste t assegnazione
~t = t(x) se x in V, 1 se x=y1,…yj-2,0 se x=yj-1,…yn-3
<=) u non sodd quindi ogni t assegnazione t(u)=0
fissiamo t tale che vi in V t(vi)=0
se voglio soddisfare ~u necessariamente ~t(yj)=1 j=1,…,n-3
In questo modo l’ultima clausola non è soddisfatta (vn-1 or vn or yn-3’) quindi ~u non sodd.
Qual è il problema del vertex cover?
Sia G grafo non orientato
C sube V è vertext cover quando forall {x,y} in E x in C oppure y in c
Perché il problema del vertex cover è NP-hard?
Descriviamo rid. polinomiale da 3-SAT a VC
Sia p = (u1,1 or u1,2 or u1,3) and (…) and (un,1 or un,2 or un,3) pol. booleano con m=#clausole, n=#variabili
Costruisco grafo non orientato G(p)
1. un vertice per ogni variabile e per ogni variabile negata
2. un vertice per ogni letterale di ogni clausola
3. lato xi-xi’, ui,j-ui,k
4. lato xi’-ui,j quando xi=ui,j
G(p) ha 2n+3m nodi, vertex cover ha almeno n+2m nodi
Sia k(p)=n+2m
p sodd <=> G(p) ha un vertex cover i cardinalità n+2m
=>) sia p sodd, t assegnamento
def. vertici t(xi)=1, prendiamo xi, altrimenti xi’
per ogni clausola selezioniamo due nodi, escludendo uno dei nodi soddisfatti da t
<=) sia G(p) con vertex cover di cardinalità n+2m
per ogni clausola di p, c’è un nodo ui,j che non sta nel mio vertex cover. Definisco t ponendo t(ui,j)=1 per ognuno dei nodi
Che cos’è il problema clique?
Dato un grafo non orientato G ed un intero k, determiniamo se G possiede un sottografo completo con k vertici
Perché il problema clique è NP-hard?
Rid. pol. da 3-SAT a clique
p = (u1,1 or u1,2 or u1,3) and … and (uk,1 or uk,2 or u k,3)
Costruiamo grafo G(p)
- vertici: ciascun letterale è un vertice di G(p)
- lati: ogni coppia di vertici è collegata da un lato, tranne
- vertici sulla stessa clausola
- vertici che rappresentano letterali opposti
p sodd <=> G(p) contiene sottografo completo di cardinalità k
=>) t assegnamento che soddisfa p, per ognuna delle clausole di p, scelgo uno dei letterali soddisfatti da t
i k vertici selezionati determinano sottografo completo
<=)C sube V, |C|=k, C individua sottografo completo di G(p)
Definiamo t assegnamento ponendo t(v) = 1 forall v in C
Qual è il problema del circuito hamiltoniano (HAM)?
Trovare circuito (torna a nodo partenza) che attraversa 1 e 1 sola volta tutti i vertici
Perché il problema HAM è NP-difficile?
creo rid. pol da 3-SAT a HAM
Costruiamo grafo G(p)
per ogni variabile creo esagono
esco e torno
Vedi esempio
Perché 2-SAT è risolvibile in tempo polinomiale? (Qual è la costruzione?)
Dato pol. bool in 2-CNF costruisco G(p)
- vertici: forall k variabile di p, xi e xi’ sono vertici
- archi: tutti quelli della forma ui,1 NEGATO -> ui,2
ui,2 NEGATO -> ui,1
Qual è la condizione di soddisfacibilità per 2-SAT?
Qual è l’algoritmo per risolvere 2-SAT?
