Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 16.Altri problemi NP-Completi


Perché vedere altri problemi Np-complete?

Per ragioni che non sono ben conosciute, la maggior parte dei problemi NP presenti in natura sono noti per essere o in P o NP-complete.
Se si cerca un algoritmo in tempo polinomiale per un nuovo problema NP, spendere una buona parte degli sforzi nel cercare di dimostrare la NP-completezza del problema è una cosa sensata perché, se così fosse, l’esperienza insegna che molto probabilmente un algoritm polinomiale per P non sarà mai trovato.
Questo spiega perché sono importanti le prove di NP-completezza.
Tali prove consistono nel provare oltre l’appartenenza a P di un problema, una riduzione polinomiale ad esso di un altro problema NP-Completo.
Per i problemi che vedremo in questa lezione, un buon candidato alla riduzione è 3SAT (l’insieme delle formule booleane 3CNF soddisfacibili).

  • In tali riduzioni, cerchiamo di strutturare il linguaggio sotto esame in modo che possa simulare le variabili e le clausole delle formule Booleane.
  • Ad esempio, quando riduciamo 3SAT a CLIQUE, le variabili sono simulate da vertici, e le clausole da triple.
  • Tali strutture sono spesso chiamati gadget.

Np-completezza per Clique

Corollario: CLIQUE è NP-completo.
Dimostrazione:

  • Come è già stato (facilmente) dimostrato, CLIQUE è in NP.
  • Con un precedente teorema abbiamo dimostrato che 3SAT è riducibile in tempo polinomiale a CLIQUE, ed inoltre abbiamo anche dimostrato che 3SAT è NP-completo.
  • Per il teorema della NP-completezza abbiamo che se un linguaggio B NP-completo è riducibile in tempo polinomiale ad un linguaggio C in NP, allora C è anchesso NP-completo.
  • Per questo motivo CLIQUE è NP-completo.

Si ricordi che un linguaggio A NP-completo se solo se:

  • A è in NP.
  • Ogni altro linguaggio NP è riducibile ad A (se prendiamo un linguaggio A NP-completo, allora basta solo questo per provare questa proprietà).

Problema di definire un Vertex Cover

Se G è un grafo, una copertura dei vertici di G (Vertex Cover) è un sottoinsieme di nodi in cui ogni arco di G tocchi (almeno) uno di questi nodi.

VERTEX-COVER =
{ | G è un grafo non direzionato che ha un sottoinsime G' di cardinalità k che è un vertex cover}

<G,4> ∈ VERTEX-COVER?

<G,3> ∈ VERTEX-COVER?

<G,2> ∈ VERTEX-COVER?

<G,1> ∈ VERTEX-COVER?

Nota: Si può facilmente dimostrare che se è un vertex cover allora lo è anche per ogni m>k.


Np-completezza di Vertex Cover

Teorema: VERTEX-COVER è NP-completo.
Dimostrazione:
È facile dimostrare che Vertex-cover è in NP [esercizio per gli studenti].
Per provare l’hardness, costruiamo una riduzione in tempo polinomiale da 3SAT a VERTEX-COVER.
La riduzione deve quindi “mappare” una formula 3CNF φ in un grafo G e un valore k, tale che φ è soddisfacibile sse G ha un Vertex Cover di taglia k.
Per ogni variabile x in φ, costruiamo un arco orizzontale che connette due nodi che marchiamo con i “gadget” x e x.
Chiamiamo ognuno di questi sottografi “variabile-gadget“.
Intuitivamente, settare x a true corrisponde a selezionare il nodo di sinistra per il Vertex Cover, mentre falso corrisponde a selezionare il nodo di destra.
Per esempio, se

φ= (x ∨ x ∨ z) ∧ (xzz) ∧ (x ∨ z ∨ z),

la riduzione produce i due archi indicati nella figura a lato.


Np-completezza di Vertex Cover (segue)

φ= (x ∨ x ∨ z) ∧ (xzz) ∧ (x ∨ z ∨ z),

Per ciascuna clausola, si produce un “triangolo” di interconnessione tra i nodi.
Ciascun nodo del triangolo è marcato con un letterale della clausola.
Ogni triangolo rappresenta una “clausola gadget“.
Infine, connettiamo ciascun nodo “variabile-gadget” con ciascun nodo “clausola-gadget” che hanno identica marcatura.


Np-completezza di Vertex Cover (segue)

Si noti che il grafo G così costruito avrà 2m+3i nodi, dove m è il numero di variabili in φ e i è il numero di clausole.
k sarà invece m+2i. Nell’esempio visto avremo che k=2+(2*3)=8.

Claim: φ è soddisfacibile sse G ha un Vertex Cover di taglia k.

φ= (x ∨ x ∨ z) ∧ (xzz) ∧ (x ∨ z ∨ z)


Np-completezza di Vertex Cover (segue)

Supponiamo che φ sia soddisfacibile.
Si considerino i nodi di variabili-gadget nel Vertex Cover che corrispondono a letterali “veri” nella formula.
Per ciascuna “clausola-gadget”, si selezioni un nodo letterale “marcato vero”, e si includino gli altri due nodi nel Vertex Cover. Otteniamo così un numero totale di k nodi.
Tutti gli archi di queste variabili e clausole gadget sono ovviamente “cover” (coperti). Inoltre, ciascun arco tra i gadget è coperto da un nodo (vero) di variabile gadget, o da uno dei due nodi della clausola gadget che è stata inclusa nel Vertex Cover.


Np-completezza di Vertex Cover (segue)

Supponiamo ora che G ha un VC di taglia k. Chiaramente, deve includere almeno un nodo da ciascuna variabile gadget (per coprire l’arco corrispondente), e almeno due nodi per ciascuna clausola gadget (altrimenti un arco rimane non coperto).
Siccome la somma di questi numeri è pari a k, questi nodi sono esattamente i nodi del vertex-cover (non servono altri nodi e non possiamo prendere nodi differenti).
Prendiamo i nodi delle variabili gadget che sono nel VC e assegniamo a true i corrispondenti letterali nella formula. Questo è un assegnamento soddisfacibile per φ perchè, se si prende una qualsiasi clausola gadget, il nodo che non è in VC è sicuramente connesso tramite un arco a un nodo letterale vero di una variabile gadget, altrimenti quell’arco tra gadget non sarebbe coperto.


Np-completezza di Hampath


Np-completezza di Hampath (segue)

La struttura complessiva di G avrà una forma del tipo mostrato a lato.

Ci sono degli archi aggiuntivi che connettono i nodi delle clausole con nodi interni alla struttura a diamante. Nella prossima diapositiva vedremo il perchè.


Np-completezza di Hampath (segue)


Np-completezza di Hampath (segue)

Si supponga che φ sia soddisfacibile

Si consideri il percorso che fa “zig-zag” attraverso i nodi true del diamante, e “zag- zig” attraverso i nodi false del diamante.
Questo percorso copre tutti i nodi eccetto i nodi della clausola c1,…,ck.
Possiamo facilmente includerli selezionando un letterale vero in ciascuna clausola e aggiungendo una “deviazione” dalla corrispondente coppia di nodi orizzontali del corrispondente diamante.
Per esempio quando c1 include x e x1 è selezionata per c1, abbiamo gli archi dal primo diamante a c1 e viceversa.


Np-completezza di Hampath (segue)

Dall’altro lato, se c1 include x2, selezioneremo c1 con una deviazione, ma in senso opposto.

E così via…

Il path risultante con le deviazioni è ovviamente Hamiltoniano.


Np-completezza di Hampath (segue)

Per la direzione inversa assumiamo che G ha un path Hamiltoniano da S a t. Con un pò di immaginazione, possiamo vedere che il path
deve essere “normalizzato“, significa che va immaginato dal primo in alto all’ultimo in basso, eccetto che per la deviazione dei nodi della
clausola. Da questo percorso Normalizzato possiamo facilmente ottenere un assegnamento soddisfacibile: se attraversiamo il diamante in
zig-zag verso sinistra assegnamo true alle corrispondenti varibiabili. Altrimenti le assegnamo false.


Np-completezza di Uhampath

UHAMPATH è la versione non direzionata di HAMPATH
Teorema: UHAMPATH è NP-completo.

  • Dimostrazione: Riduciamo Hampath ad Uhampath. Da un grafo direzionato G, costruiamo il suo equivalente G’ non direzionato sostituendo ciascun nodo u di G con tre nodi uin umid e uout; eccetto il nodo s che viene sostituito con sout, e il nodo t che viene sostituito dal nodo tin. G’ ha due tipi di archi. Un tipo connette ciascun nodo umid, e uout. Il secondo connette ciasciun nodo uin con uou, finchè c’è un arco da u a v in G. Supponiamo che G ha un path Hamiltoniano

s, u1, u2, …, uk, t

Allora ovviamente segue che G’ ha un path Hamiltoniano

sout, u1in, u1mid, u1out, u2in, u2mid, u2out, …, ukin, ukmid, ukout, tin

Ugualmente vale per l’altra direzione.

Np-completezza di Subset-Sum

Teorema: Subset-Sum è Np-completo.
Dimostrazione:

  • Che Subset-sum appartine a NP è già stato dimostrato.
  • Riduciamo adesso in tempo polinomiale 3SAT a Subset-Sum.
  • Sia φ una formula 3-cnf booleana con x1,…,xl variabili e c1,…,ck clausole.
  • Costruiamo un tabella di decimali con (l+k) colonne e (2l+2k+1) righe .
  • Le colonne sono marcate con x1,…,xl,c1,…,cl, e le righe sono marcate con y1,z1,…,yl,zl,g1,h1,…gk,hk, t.
  • Il contenuto delle righe sono numeri decimali. Le prime 2l+2k righe, con numeri di S, e l’ultima riga è il numero target t.
  • Mostreremo in seguito che S ha un sottoinsieme che sommato da t sse φ è soddisfacibile.
  • In particolare, la riga/numero t consiste di l uno seguiti da k tre.
  • Ciascuna riga yi ha un 1 nella colonna xi, e così in ciascuna colonna cj tale che la clausola cj contiene xi.
  • Ciascuna riga zi ha un 1 nelle colonne xi, e così in ciascuna colonna cj tale che la clausola cj contiene xi.
  • Infine, ciascuna riga gi e hi ha un 1 nelle colonne ci.
  • Le cifre non specificate sono da sottintendersi a 0.

Np-completezza di Subset-Sum (segue)

Ciascuna riga yi ha un 1 nella colonna xi se cj contiene xi.
Ciascuna riga yi ha un 1 nella colonna cj se cj contiene xi vera.
Ciascuna riga zi ha un 1 nelle colonne xi, e così in ciascuna colonna cj tale che la clausola cj contiene xi.
Infine, ciascuna riga gi e hi ha un 1 nelle colonne ci.
Le cifre non specificate sono da sottintendersi a 0.


Np-completezza di Subset-Sum (segue)

Supponi φ ha un assegnamento soddisfacibile. Costruiamo S come segue:

Seleziona yi se xi è true, e selziona zi se xi è false. Se sommiamo quello che abbiamo selezionato fin ora otteniamo un 1 in ciascuna delle prime l cifre perché abbiamo selezionato le yi o zi per ciascun i.

Inoltre, ciascuna delle ultime k cifre è un numero compreso tra 1 e 3 perché ciascuna clausola è soddisfacibile e così contengono litterali veri tra 1 e 3.
In dipendenza di questo numero, selezioniamo ulteriormente i numeri di g e h per portare ciascuno delle ultime k cifre a 3.


Np-completezza di Subset-Sum (segue)

Supponiamo che la somma di S dia t. Osserviamo che ciascuna colonna nella tabella che descrive S ha al più cinque 1.
Per ottenere un 1 in ciascuna delle prime l colonne di t, abbiamo bisogno o delle yi o delle zi per ciascuna i.
Se abbiamo yi, assegnamo xi a true, altrimenti a false.
Questo assenamento deve soddisfare φ perchè in ciascuna delle colonne finali k la somma è sempre 3.
Nella colonna cj, al massimo 2 possono venire da gj e hj, così almeno 1 in questa colonna dovrebbero provenire da qualche yi o da qualche zi nel sottoinsieme. Se abbiamo yi, allora xi appare a cj e allora cj è assegnata a true, così cj è soddisfacibile. Se abbiamo zi, allora xi appare in cj e xi è assegnato a false, così cj è soddisfacibile.
Pertanto φ è soddisfacibile.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion