Problemi di complessità e risoluzione Flashcards
(20 cards)
Cos’è il problema del circuito hamiltoniano?
Sia G = (V, E) grafo. Un cammino hamiltoniamo è un cammino semplice che visita tutti i nodi del grafo
Un circuito hamiltoniano è un cammino chiuso che visita tutti i nodi una e una sola volta.
Esiste circuito hamiltoniano
Algoritmo di risoluzione del circuito hamiltoniano
- Codifica
vertici: binario
lati: v1#v2
grafo: ###v1#v2##v2#v4###n
Approccio det:
MdT a 4 nastri
- 1. input (cioè il grafo)
- 4. Sequenza 1 nnnn…(n-1 volte) 1 (cioè ultima sequenza da generare)
- 2. genero via via tutte le sequenze di tipo 1 V1…Vn-1 1
Algoritmo
1. genero sequenza su #2
2. se è uguale a #4 -> termino e rifiuto
3. Controllo se sequenza è circuito hamiltoniano su #3
Come cambia la complessità all’aggiunta di un vertice?
Caso peggiore->non accettazione -> devo generare tutte le sequenze
n^{n-1} sequenze, quindi
tc_N=Omega(n^n)
Come si risolve il problema del cammino hamiltoniano con MdT non det.?
Uso mdt a 3 nastri gli stessi primi 3 di quella standard
1. Controllo quanti archi ha grafo, meno di n, non c’è circuito e termino rifiutando
2. genero non deterministicamente sequenza su #2
3. Uso #3 per controllare se è circuito hamiltoniano
Qual è la complessità di questa soluzione nel caso peggiore?
Ogni nodo O(logn)
k archi >= n nodi (altrimenti non c’è circuito)
- controllo presenza n archi O(k*n) = O(k^2)
- generazione sequenza O(nlogn) cioè scrivere n nodi binari
- ogni iterazione
. operazioni di spostamento testine O(nlogn)
. controllare se vertice è già presente tra i precedenti O(nlogn)
. controllare se c’è arco O(klogn)
iterazione = O(k^2 logk)
Perchè cambia complessita tra MdT det e non det?
La MdT deterministica “costruisce” la soluzione mentre MdT non deterministica verifica la soluzione in tempo polinomiale (rendendo il problema trattabile)
Cosa vuol dire che un linguaggio $L_1$ è polinomialmente riducibile ad un altro?
Esiste f funzione di riduzione e M MdT che calcola f in tempo polinomiale
L1 pol. rid. a L2, L1 in P => L1 in P
M1 che decide L1
Dato w in Sigma1*
calcolo f(w) -> O(n^r) pke pol.
controllo se f(w) in L2 O(n^s) pke pol
in totale O(n^rs)
Linguaggio NP-hard e NP-completo
NP-Hard quando VQ linguaggio in NP, esiste f rid. polinomiale da Q a L
NP-completo:
L in NP
L NP-hard
Se esistesse L in NPC, L in P => P = NP
P sube NP ovviamente
Sia Q NP, strategia per decidere P
L NP-hard quindi esiste riduzione da Q a L
Dato w
1) calcolo f(w) riduzione da Q a L
2) decido se f(w) in L -> L in P esiste polinomiale
Q NP in P -> NP sube P
Cosa vuol dire che rep1 è polinomialmente trasferibile in rep2?
Quando esiste funzione t: Sigma1->Sigma2 t.c.
1. forall p istanza t(rep1(p)=rep2(p)
2. forall w in Sigma1*,w not in Im(rep1) => w not in Im(rep2)
3. t computabile in tempo polinomiale
La complessità dipende dalla rappresentazione?
SI. rep1 è polinomialmente trasferibile in rep2 => |rep2(p)| è al più polinomiale nella lunghezza di rep2(p)
Dato Q problema, Q in P con rep2 allora Q in P con rep1
Due rappresentazioni distinte delle istanze di un problema se abbastanza “ragionevoli” si possono trasformare polinomialmente una nell’altra
Cosa sono polinomi booleani?
PB(x1,…,xn) è un polinomio booleano sulle indeterminate x1,…xn
- 0,1 in PB(…)
- xi in PB(…)
- p and q, p or q, not p in PB(…)
Come è definito l’assegnamento?
t: {x1,…,xn} -> {0,1}
si può estendere al polinomio usando l’algebra di boole
dati p,q polinomi booleani p equiv q se forall t assegnamento t(p)=t(q)
Come si definisce la Forma Normale Congiuntiva (CNF)?
- letterale (variabile o sua negazione)
- clausola (disgiunzione di letterali x1 or xk or not xn…)
- CNF: congiunzione di clausole
Cos’è il problema SAT?
Dato polinomio booleano in CNF trovare assegnamento tale che soddisfa ovvero t(p)=1
Come si può codificare problema SAT in MdT?
- variabili xi = codifica binaria
- letterale c(xi)#{0,1}
- polinomio: lista di letterali con simboli di and e or
es. 1#1or10#0and11#1 cioè
(x1 con valore 1 or x2 con valore 0) and (x3 con valore 1)
Come è fatto algoritmo di MdT per SAT?
INPUT: variabili##codifica pol booleano
MdT non det a 2 nastri
#1. INPUT
#2. Assegnamento da verificare
Algoritmo
- genero in modo non det. un assegnamento
- esamino polinomio in input
- se in clausola trovo letterale soddisfatto vado avanti
- nessun letterale soddisfatto rifiuto
Quali conseguenze ci sono se P≠NP?
NPC, P sube NP
NP \ (P u NPC) not empty = NP-intermedi
Quali conseguenze si hanno se P=NP?
NPC = NP = P
Prop: P = NP => ogni linguaggio P è NPC (tranne vuoto e sigma*)
Dim: Dato L in P vogliamo far vedere L np difficile
Sia Q NP descriviamo riduzione da Q a L
f:w to {a se w in Q, b se w notin Q}
a, b esistono perchè L notempty e L not sigma*
