NP-completezza
Avrei i seguenti due problemi:
k-CLIQUE: ($k \ge 2$ fisso)
(un k-Clique è un sottografo completo (cioè che tutti i vertici sono collegati tra di solo in tutti i modi possibili) che fa uso di k vertici)
Input: Un grafo $G=(V,E)$, dove V è l'insieme dei vertici e E è l'insieme degli spigoli.
Domanda: Il grafo G possiede un k-Clique?
e
CLIQUE:
Input: Grafo $G=(V,E)$, $k \ge 2$
Domanda: Il grafo G possiede un k-Clique?
Dovrei dimostrare:
a) Il problema k-CLIQUE appartiene a P.
b) Il problema CLIQUE è invece NP completo, e qui come suggerimento mi dice di ricondurlo al problema SAT.
Non so da dove partire...HELP!
k-CLIQUE: ($k \ge 2$ fisso)
(un k-Clique è un sottografo completo (cioè che tutti i vertici sono collegati tra di solo in tutti i modi possibili) che fa uso di k vertici)
Input: Un grafo $G=(V,E)$, dove V è l'insieme dei vertici e E è l'insieme degli spigoli.
Domanda: Il grafo G possiede un k-Clique?
e
CLIQUE:
Input: Grafo $G=(V,E)$, $k \ge 2$
Domanda: Il grafo G possiede un k-Clique?
Dovrei dimostrare:
a) Il problema k-CLIQUE appartiene a P.
b) Il problema CLIQUE è invece NP completo, e qui come suggerimento mi dice di ricondurlo al problema SAT.
Non so da dove partire...HELP!
Risposte
"pat87":
a) Il problema k-CLIQUE appartiene a P.
Eh sì, magari! In tal caso $P =NP$, dato che il problema di massima Clique è NP-completo.
Per prima cosa devi mostrare che il problema di massima Clique è il NP. Supponi di avere un grafo $G = (V, E)$, e che ti siano dati $k$ nodi, per vedere se è NP devi solo verificare se in tempo polinomiale nella dimensione dell'istanza tu riesci a vedere se quei $k$ nodi formano una clique.
Al più dovrai fare $k^2$ confronti, pertanto il problema di massima Clique è NP-completo.
Dimostriamo ora che il problema di soddisfacibilità (SAT) si riduce polinomialmente a massima Clique. Ogni funzione booleana può essere sempre espressa in forma normale congiuntiva, ossia
$C_1 " OR " C_2 " OR " \ldots " OR " C_n$
dove ogni clausola $C_i$ è un'AND logico di variabili booleane (le quali possono essere affermate o complementate). Consideriamo un grafo, in cui si vanno a costruire tanti gruppi di nodi quante sono le clausole, e ogni gruppo di nodi ha tanti nodi quante variabili sono presenti nella rispettiva cluausola.
Fatto questo, creiamo gli archi del grafo, secondo questa regola; un arco congiunge due nodi se:
1) tali nodi appartengono a gruppi diversi
2) tali nodi sono relativi a variabili che non sono una il complementare dell'altra
Presa una clique di grado $k$ su questo grafo, e associando il valore logico vero ai nodi toccati dagli archi facenti parte della clique, si nota che in questo modo si rendono vere $k$ clausole del problema di SAT. Per come è costruito il grafo, il grado della massima clique è proprio $n$ (numero di clausole), trovando quindi una massima clique si trova una soluzione al problema SAT. Quindi SAT si riduce a CLIQUE. Resta da dimostrare che la riduzione è polinomiale (nella dimensione dell'istanza di SAT).
Supponendo che le variabili del problema di SAT siano $m$, e che le clausole siano $n$, per costruire il grafo servono $m n$ nodi e al più $m^2 n^2$ archi, pertanto la riduzione è polinomiale e il problema di massima clicque è NP-completo dal momento che, per il teorema di Cook, SAT è NP-completo.
Ma perché nel foglio ho che k-CLIQUE appartiene a P? 
Mmmm...cosa davvero strana.
Grazie della risposta, adesso tento di capire...
Mmmm...cosa davvero strana.
Grazie della risposta, adesso tento di capire...
Aspè, forse ho inteso male io... Il problema di massima clique è NP-completo, e, a meno che $P = NP$, non sta in $P$. Forse non è NP-completo, ma P, il problema di trovare una clique di grado $k$, in tal caso andrebbe trovato un algoritmo polinomiale nella dimensione dell'istanza, oppure un problema P che si riduce polinomialmente a K-clique... Può darsi che abbia capito male io.
Per quanto riguarda il problema a), effettivamente k-CLIQUE è in P.
Un algoritmo a forza bruta fa il lavoro. Basta enumerare tutti i sottinsiemi di k vertici e controllare se sono una cricca oppure no. Poiché il numero $s_k$ dei sottinsiemi di $V$ con $k$ elementi è polinomiale in $|V|$ ($s_k=((|V|),(k))=1/(k!)|V|(|V|-1)...(|V|-(k-1))=O(|V|^k)$, con $k$ costante) e poiche' si controlla se un sottinsieme di $k$ vertici e' una cricca in tempo costante ($k(k-1)$ archi da controllare), il tempo di esecuzione dell'algoritmo e' $O(|V|^k)$
Un algoritmo a forza bruta fa il lavoro. Basta enumerare tutti i sottinsiemi di k vertici e controllare se sono una cricca oppure no. Poiché il numero $s_k$ dei sottinsiemi di $V$ con $k$ elementi è polinomiale in $|V|$ ($s_k=((|V|),(k))=1/(k!)|V|(|V|-1)...(|V|-(k-1))=O(|V|^k)$, con $k$ costante) e poiche' si controlla se un sottinsieme di $k$ vertici e' una cricca in tempo costante ($k(k-1)$ archi da controllare), il tempo di esecuzione dell'algoritmo e' $O(|V|^k)$
salve a tutti!!
colgo l'occasione di questo post per farvi una richiesta, cioè mi affascina molto questo tipo di matematica (si chiama teoria della complessità o non c'entra nulla?) e volevo chiedervi:
1) se c'è un qualche libro facile per chi non sa nemmeno cosa voglia dire P-completo, giusto per iniziare un po'.
2) se magari vi andrebbe di farlo voi un piccolo thread del tipo: P VS NP for dummies...
grazie mille!!!buon anno a tutti
colgo l'occasione di questo post per farvi una richiesta, cioè mi affascina molto questo tipo di matematica (si chiama teoria della complessità o non c'entra nulla?) e volevo chiedervi:
1) se c'è un qualche libro facile per chi non sa nemmeno cosa voglia dire P-completo, giusto per iniziare un po'.
2) se magari vi andrebbe di farlo voi un piccolo thread del tipo: P VS NP for dummies...
grazie mille!!!buon anno a tutti
Allora, ti spiego:
Questa branca della matematica o dell'informatica teorica si chiama teoria della complessità computazionale, in pratica lo scopo è quello di classificare gli algoritmi per risolvere i problemi in base alla loro "difficoltà", cioè di classificarli in base a quanto tempo ci mettono per ridarti la risposta corretta in funzione della grandezza del dato di partenza iniziale (input). In questa teoria vengono in particolar modo definiti due classi di complessità, ovvero due insiemi che chiamiamo P e NP, che raccolgono innumerevoli problemi di complessità "simili".
Un problema appartiene a P se esiste un algoritmo che in tempo polinomiale rispetto alla grandezza dell'input $n$, cioè in tempo $O(n^k)$ riesce a ridarti la soluzione corretta. Fin qui tutto ok. Ma qui arriva il bello.
Un problema appartiene a NP se è possibile VERIFICARE in tempo polinomiale che x è una soluzione, ma non necessariamente esiste un algoritmo che ti risolva in tempo polinomiale il problema.
Naturalmente $P\subset NP$, ma il vero problema è se anche l'altra inclusione è vera:
$P=NP$? Non è ancora stata trovata nessuna risposta a questo quesito, senza dubbio il più grande dell'informatica teorica. Avrebbe conseguenze molto rilevanti una sua eventuale dimostrazione o confutazione. Letteralmente vuol dire:
"se è possibile verificare in "poco" tempo che una data soluzione è corretta, allora è possibile anche trovare la soluzione al dato problema in poco tempo?"
Un problema è NP completo se è uno dei più difficili problemi in NP, ovvero un problema $\Pi$ per cui vale la seguente proprietà:
$\Pi \in NP$-completo & $\exists$ Algoritmo polinomiale per $\Pi \Rightarrow P=NP$
(esiste una definizione un po' più formale di NP-completo, ma credo che per adesso vada bene)
Per cui ti basta trovare anche solo UN algoritmo che in tempo polinomiale ti risolva un problema NP-completo, per dimostrare che P=NP (e vincere 1 milione di dollari!
). Il problema è però effettivamente trovarlo!
Prova a guardare su wikipedia per maggiori informazioni...
@fields: perché s_k è esprimibile come il binomiale del numero degli spigoli su k? Non ho capito molto bene il tuo ragionamento...
@Tipper: grazie mille ho capito tutto!
Questa branca della matematica o dell'informatica teorica si chiama teoria della complessità computazionale, in pratica lo scopo è quello di classificare gli algoritmi per risolvere i problemi in base alla loro "difficoltà", cioè di classificarli in base a quanto tempo ci mettono per ridarti la risposta corretta in funzione della grandezza del dato di partenza iniziale (input). In questa teoria vengono in particolar modo definiti due classi di complessità, ovvero due insiemi che chiamiamo P e NP, che raccolgono innumerevoli problemi di complessità "simili".
Un problema appartiene a P se esiste un algoritmo che in tempo polinomiale rispetto alla grandezza dell'input $n$, cioè in tempo $O(n^k)$ riesce a ridarti la soluzione corretta. Fin qui tutto ok. Ma qui arriva il bello.
Un problema appartiene a NP se è possibile VERIFICARE in tempo polinomiale che x è una soluzione, ma non necessariamente esiste un algoritmo che ti risolva in tempo polinomiale il problema.
Naturalmente $P\subset NP$, ma il vero problema è se anche l'altra inclusione è vera:
$P=NP$? Non è ancora stata trovata nessuna risposta a questo quesito, senza dubbio il più grande dell'informatica teorica. Avrebbe conseguenze molto rilevanti una sua eventuale dimostrazione o confutazione. Letteralmente vuol dire:
"se è possibile verificare in "poco" tempo che una data soluzione è corretta, allora è possibile anche trovare la soluzione al dato problema in poco tempo?"
Un problema è NP completo se è uno dei più difficili problemi in NP, ovvero un problema $\Pi$ per cui vale la seguente proprietà:
$\Pi \in NP$-completo & $\exists$ Algoritmo polinomiale per $\Pi \Rightarrow P=NP$
(esiste una definizione un po' più formale di NP-completo, ma credo che per adesso vada bene)
Per cui ti basta trovare anche solo UN algoritmo che in tempo polinomiale ti risolva un problema NP-completo, per dimostrare che P=NP (e vincere 1 milione di dollari!
). Il problema è però effettivamente trovarlo!Prova a guardare su wikipedia per maggiori informazioni...
@fields: perché s_k è esprimibile come il binomiale del numero degli spigoli su k? Non ho capito molto bene il tuo ragionamento...
@Tipper: grazie mille ho capito tutto!
@pat 87 $s_k$ e' il numero di sottinsiemi di $V$ aventi $k$ elementi, che e' dato, come ben noto, dal coefficiente binomiale. Siccome noi enumeriamo i sottinsiemi di $V$ con $k$ elementi, ovviamente dobbiamo considerare il numero $s_k$.
@e^iteta
Un libro classico e' Papadimitriou, Computational Complexity. Ottimo, ma incomincia ad avere i suoi annetti, e dunque non arriva alle frontiere della ricerca attuale.
L'idea di un thread P vs NP for dummies non e' male, perche' ci sono letteralmente migliaia di problemi interessanti, simili a quelli che ha postato pat87, da proporre. Il guaio, per me, e' che non ho molto tempo per dargli vita.
@e^iteta
Un libro classico e' Papadimitriou, Computational Complexity. Ottimo, ma incomincia ad avere i suoi annetti, e dunque non arriva alle frontiere della ricerca attuale.
L'idea di un thread P vs NP for dummies non e' male, perche' ci sono letteralmente migliaia di problemi interessanti, simili a quelli che ha postato pat87, da proporre. Il guaio, per me, e' che non ho molto tempo per dargli vita.
Per non scrivere un altro topic, avrei un altro problemino:
$k-COL$: ($k \ge 2$)
Dati: Grafo $G=(V,E)$
Domanda: esiste una k-"colorazione" dei vertici per cui per ogni due vertici legati da uno spigolo i colori siano diversi? Ovvero, esiste una funzione $f: V \to \{1,...,k\}$, per cui per tutti i vertici:
$f(x) ne f(y)$, per $\{x,y\} \in E$?
Sapendo che $3-COL$ è NP-completo (lo abbiamo dimostrato in classe), dimostrare che:
1) $k-COL$ è NP-completo per $k\ge 3$ (utilizzare una riduzione per $3-COL$)
2) $2-COL$ appartiene a P, e in tal caso trovare un algoritmo polinomiale che lo risolva.
Grazie mille!
$k-COL$: ($k \ge 2$)
Dati: Grafo $G=(V,E)$
Domanda: esiste una k-"colorazione" dei vertici per cui per ogni due vertici legati da uno spigolo i colori siano diversi? Ovvero, esiste una funzione $f: V \to \{1,...,k\}$, per cui per tutti i vertici:
$f(x) ne f(y)$, per $\{x,y\} \in E$?
Sapendo che $3-COL$ è NP-completo (lo abbiamo dimostrato in classe), dimostrare che:
1) $k-COL$ è NP-completo per $k\ge 3$ (utilizzare una riduzione per $3-COL$)
2) $2-COL$ appartiene a P, e in tal caso trovare un algoritmo polinomiale che lo risolva.
Grazie mille!
2) Si tratta di notare che $G$ e' $2$-colorabile se e solo se e' bipartito.
Detto questo, avrete sicuramente visto un algoritmo per testare la bipartiteness di un grafo...
ad esempio puoi adattare una BFS o una DFS.
1)Intuitivamente l'idea mi sembra semplice, introduciamo un gadget: un grafo completo di $k-3$ vertici
e colleghiamo ogni vecchio vertice ad ogni nuovo vertice del grafo completo. Provo a formalizzare un po'
la cosa.
$k-"COL"$ e' in $NP$: la prova e' il grafo (qui inteso come le coppie $("vertice","colore")$)
della $f:V\rightarrow {1, \ldots, k}$. Dato quello, puoi testare in $E(G)$ passi
che $f(x) \ne f(y)$ per ogni ${x,y}\in E$.
Per la riduzione $3-"COL" \leq_{"P"} k-"COL"$, procederei come segue, dato $G$ costruiamo $G'$:
$V(G') = V(G) \cup V'$ t.c. $V'={x_1, \ldots, x_{k-3}}$ $V(G) \cap V' = \emptyset$, $|V'|=k-3$ (calcolabile in $O(1)$)
$E(G') = E(G) \cup E'$ t.c.
i) per ogni $u \in V, v \in V'$, ${u,v} \in E'$ (calcolabile in $O(V(G))$)
ii) per ogni $u,v \in V'$, ${u,v} \in E'$ (calc in $O(1)$)
iii) niente altro e' in $E'$
Intutivamente: Abbiamo aggiunto un grafo completo di $k-3$ vertici, inoltre ogni vertice di $G$ e' linkato
ad ogni vertice di questo nuovo grafo completo.
Claim: $G \in 3-"COL"$ sse $G' \in k-COL$
Prova: Chiamiamo i k colori $c_1, \ldots, c_k$
Se $G \in 3-"COL"$ con colorazione $f:V\rightarrow {c_1, c_2, c_3}$ coloriamo $G'$ con colorazione $f'$ definita come segue:
se $v \in V(G)$ $f'(v)=f(v)$, se $x_i \in V'$ $f(x_i) = c_{3+i}$ per $1 \leq i \leq k-3$. Ovvero, ad ogni nuovo vertice del grafo completo, diamo un colore diverso.
$f'$ risulta subito essere una $k$-colorazione. (i lati che abbiamo aggiunto sono "salvi" per definizione, e lo sono anche quelli "vecchi" per ipotesi)
Se $G' \in k-"COL"$, allora i vertici del nuovo grafo completo, ovvero i vertici in $V'$ devono avere tutti un colore diverso, perche' tale grafo e'
completo, e tali colori diversi sono esattamente k-3 come |V'|. Inoltre i colori del vecchio grafo $G$ devono essere tutti distinti da questi $k-3$ colori
perche' ogni vertice di $G$ tocca ogni vertice in $V'$. Dunque il vecchio $G$ deve avere $\leq 3$ colori. Questo conclude la prova.
Detto questo, avrete sicuramente visto un algoritmo per testare la bipartiteness di un grafo...
ad esempio puoi adattare una BFS o una DFS.
1)Intuitivamente l'idea mi sembra semplice, introduciamo un gadget: un grafo completo di $k-3$ vertici
e colleghiamo ogni vecchio vertice ad ogni nuovo vertice del grafo completo. Provo a formalizzare un po'
la cosa.
$k-"COL"$ e' in $NP$: la prova e' il grafo (qui inteso come le coppie $("vertice","colore")$)
della $f:V\rightarrow {1, \ldots, k}$. Dato quello, puoi testare in $E(G)$ passi
che $f(x) \ne f(y)$ per ogni ${x,y}\in E$.
Per la riduzione $3-"COL" \leq_{"P"} k-"COL"$, procederei come segue, dato $G$ costruiamo $G'$:
$V(G') = V(G) \cup V'$ t.c. $V'={x_1, \ldots, x_{k-3}}$ $V(G) \cap V' = \emptyset$, $|V'|=k-3$ (calcolabile in $O(1)$)
$E(G') = E(G) \cup E'$ t.c.
i) per ogni $u \in V, v \in V'$, ${u,v} \in E'$ (calcolabile in $O(V(G))$)
ii) per ogni $u,v \in V'$, ${u,v} \in E'$ (calc in $O(1)$)
iii) niente altro e' in $E'$
Intutivamente: Abbiamo aggiunto un grafo completo di $k-3$ vertici, inoltre ogni vertice di $G$ e' linkato
ad ogni vertice di questo nuovo grafo completo.
Claim: $G \in 3-"COL"$ sse $G' \in k-COL$
Prova: Chiamiamo i k colori $c_1, \ldots, c_k$
Se $G \in 3-"COL"$ con colorazione $f:V\rightarrow {c_1, c_2, c_3}$ coloriamo $G'$ con colorazione $f'$ definita come segue:
se $v \in V(G)$ $f'(v)=f(v)$, se $x_i \in V'$ $f(x_i) = c_{3+i}$ per $1 \leq i \leq k-3$. Ovvero, ad ogni nuovo vertice del grafo completo, diamo un colore diverso.
$f'$ risulta subito essere una $k$-colorazione. (i lati che abbiamo aggiunto sono "salvi" per definizione, e lo sono anche quelli "vecchi" per ipotesi)
Se $G' \in k-"COL"$, allora i vertici del nuovo grafo completo, ovvero i vertici in $V'$ devono avere tutti un colore diverso, perche' tale grafo e'
completo, e tali colori diversi sono esattamente k-3 come |V'|. Inoltre i colori del vecchio grafo $G$ devono essere tutti distinti da questi $k-3$ colori
perche' ogni vertice di $G$ tocca ogni vertice in $V'$. Dunque il vecchio $G$ deve avere $\leq 3$ colori. Questo conclude la prova.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo