Home

Federica EU

1/19

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) ∧ (x ∨ z ∨ z) ∧ (x ∨ z ∨ z),

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

Np-completezza di Vertex Cover (segue)

φ= (x ∨ x ∨ z) ∧ (x ∨ z ∨ z) ∧ (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) ∧ (x ∨ z ∨ z) ∧ (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)

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 c₁,…,c_k.
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 c₁ include x e x₁ è selezionata per c₁, abbiamo gli archi dal primo diamante a c1 e viceversa.

Np-completezza di Hampath (segue)

Dall’altro lato, se c₁ include x₂, 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 u_in u_mid e u_out; eccetto il nodo s che viene sostituito con s_out, e il nodo t che viene sostituito dal nodo t_in. G’ ha due tipi di archi. Un tipo connette ciascun nodo u_mid, e u_out. 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

s_out, u_1in, u_1mid, u_1out, u_2in, u_2mid, u_2out, …, u_kin, u_kmid, u_kout, t_in

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 x₁,…,x_l variabili e c₁,…,c_k clausole.
Costruiamo un tabella di decimali con (l+k) colonne e (2l+2k+1) righe .
Le colonne sono marcate con x₁,…,x_l,c₁,…,cl, e le righe sono marcate con y₁,z₁,…,y_l,z_l,g₁,h₁,…g_k,h_k, 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 y_i ha un 1 nella colonna x_i, e così in ciascuna colonna c_j tale che la clausola c_j contiene x_i.
Ciascuna riga zi ha un 1 nelle colonne x_i, e così in ciascuna colonna c_j tale che la clausola c_j contiene x_i.
Infine, ciascuna riga g_i e h_i ha un 1 nelle colonne c_i.
Le cifre non specificate sono da sottintendersi a 0.

Np-completezza di Subset-Sum (segue)

Ciascuna riga y_i ha un 1 nella colonna x_i se c_j contiene x_i.
Ciascuna riga y_i ha un 1 nella colonna c_j se c_j contiene x_i vera.
Ciascuna riga z_i ha un 1 nelle colonne x_i, e così in ciascuna colonna c_j tale che la clausola c_j contiene x_i.
Infine, ciascuna riga g_i e h_i ha un 1 nelle colonne c_i.
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 y_i se x_i è true, e selziona z_i se x_i è false. Se sommiamo quello che abbiamo selezionato fin ora otteniamo un 1 in ciascuna delle prime l cifre perché abbiamo selezionato le y_i o z_i 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 y_i o delle z_i per ciascuna i.
Se abbiamo y_i, assegnamo x_i a true, altrimenti a false.
Questo assenamento deve soddisfare φ perchè in ciascuna delle colonne finali k la somma è sempre 3.
Nella colonna c_j, al massimo 2 possono venire da g_j e h_j, così almeno 1 in questa colonna dovrebbero provenire da qualche y_i o da qualche z_i nel sottoinsieme. Se abbiamo y_i, allora x_i appare a c_j e allora c_j è assegnata a true, così c_j è soddisfacibile. Se abbiamo z_i, allora x_iappare in c_j e x_i è assegnato a false, così c_j è soddisfacibile.
Pertanto φ è soddisfacibile.