Problema P o NP_Completo
Ciao a tutti, spero di essere nella parte di forum giusto, in questi giorni mi è capitato un esercizio tra le mani che proprio non riesco a risolvere, sinceramente parlando non ho molto chiaro neanche da dove partire, vi scrivo il testo del problema:
"Determinare se il seguente problema è in P o in Np-completo, dato un insieme di m ballerini, alcune coppie di questi hanno in passato ballato in coppia, Si vuole determinare se esiste un insieme k di questi ballerini che non abbiano mai in precedenza ballato insieme"
se ho capito bene, prima di tutto devo dimostrare che questo problema appartiene alla classe NP, per far ciò devo utilizzare un una funzione che dia una soluzione in tempo polinomiale. terminata questa prima procedura, devo dimostrare che il problema è in NP-Completo, per far cio devo trovare un problema appartenente alla classe NP-Completo e applicare una riduzione polinomiale, l'unico problema che sta nella classe NP-completo che può essere risolto è l'independent set che mi permette di trovare un sottoinsieme di nodi che non sono collegati tra loro, ma ancora non sono riuscito ad attuare un ipotetica riduzione.
qualcuno mi saprebbe assistere su come svolgere questo esercizio, indicandomi del materiale, o qualche esempio inerente al mio problema, o come voi vi sareste comportati davanti ad un testo simile? grazie anticipatamente
"Determinare se il seguente problema è in P o in Np-completo, dato un insieme di m ballerini, alcune coppie di questi hanno in passato ballato in coppia, Si vuole determinare se esiste un insieme k di questi ballerini che non abbiano mai in precedenza ballato insieme"
se ho capito bene, prima di tutto devo dimostrare che questo problema appartiene alla classe NP, per far ciò devo utilizzare un una funzione che dia una soluzione in tempo polinomiale. terminata questa prima procedura, devo dimostrare che il problema è in NP-Completo, per far cio devo trovare un problema appartenente alla classe NP-Completo e applicare una riduzione polinomiale, l'unico problema che sta nella classe NP-completo che può essere risolto è l'independent set che mi permette di trovare un sottoinsieme di nodi che non sono collegati tra loro, ma ancora non sono riuscito ad attuare un ipotetica riduzione.
qualcuno mi saprebbe assistere su come svolgere questo esercizio, indicandomi del materiale, o qualche esempio inerente al mio problema, o come voi vi sareste comportati davanti ad un testo simile? grazie anticipatamente
Risposte
"ncknm":
"Determinare se il seguente problema è in P o in Np-completo, dato un insieme di m ballerini, alcune coppie di questi hanno in passato ballato in coppia, Si vuole determinare se esiste un insieme k di questi ballerini che non abbiano mai in precedenza ballato insieme"
fissiamo con $Y$ il tuo problema.
"ncknm":
se ho capito bene, prima di tutto devo dimostrare che questo problema appartiene alla classe NP, per far ciò devo utilizzare un una funzione che dia una soluzione in tempo polinomiale.
forse sbagli classe, se scrivi questo vuoi provare a dimostrare appartenere a \(\mathbb{P}\).
"ncknm":
qterminata questa prima procedura, devo dimostrare che il problema è in NP-Completo, per far cio devo trovare un problema appartenente alla classe NP-Completo e applicare una riduzione polinomiale, l'unico problema che sta nella classe NP-completo che può essere risolto è l'independent set che mi permette di trovare un sottoinsieme di nodi che non sono collegati tra loro,
se non mostri che appartiene a \(\mathbb{P}\) (lascio a te districare tale caso) passi al secondo caso.
Devi dimostrare che $Y$ è $\mathbb{NP}\text{-complete}$ allora:
1) $Y \in \mathbb{NP}$
2) $Y$ è $\mathbb{NP}\text{-hard}$
Dici che può assomigliare all'indipendent-set che è $\mathbb{NP}\text{-complete}$ (appartiene ad NP ed è NP-arduo), bene la sua riduzione in tempo polinomiale è la dimostrazione costruttiva per la np-completezza di $Y$.
Non serve che dimostri il caso 1) perchè è implicato dalla riduzione con l'indipendent set.
A te partire, un hint ovvio: $Y$ utilizza insiemi ed elementi, indipendent set gli archi e vertici; tale formalizzazione è la parte integrante della costruzione e riduzione.
"ncknm":
qualcuno mi saprebbe assistere su come svolgere questo esercizio, indicandomi del materiale, o qualche esempio inerente al mio problema
per del materiale: viewtopic.php?p=479901#p479901
Per prima cosa un chiarimento sul problema. Ti trovi con un grafo di m nodi (i ballerini) e un certo numero di archi, uno per ogni coppia che ha ballato insieme. Fin qui è corretto? A questo punto però stai cercando un algoritmo che stabilisca se esistono delle coppie di ballerini che non abbiano ballato insieme o vuoi trovare queste coppie? Oppure nessuna delle due cose?
A me sembra che in entrambi i casi che ho indicato, il problema sia polinomiale. Nel primo caso è infatti sufficiente verificare se il numero di archi è uguale a \(\frac{m^2 + m}{2}\) con complessità probabilmente costante o lineare, nel secondo caso si può semplicemente iterare su tutte le coppie (con tempo \(\sim C\,\frac{m^2 + m}{2}\)) e verificare se c'è un arco tra i due nodi (si suppone tempo costante \(C\)). Ho capito male il problema? Forse si chiede di trovare un insieme di dimensione massimale di ballerini in cui ogni ballerino dell'insieme non ha ballato con gli altri. In questo caso il problema diventa banalmente quello che hai indicato (nel senso che non solo è equivalente, ma è proprio quello).
A me sembra che in entrambi i casi che ho indicato, il problema sia polinomiale. Nel primo caso è infatti sufficiente verificare se il numero di archi è uguale a \(\frac{m^2 + m}{2}\) con complessità probabilmente costante o lineare, nel secondo caso si può semplicemente iterare su tutte le coppie (con tempo \(\sim C\,\frac{m^2 + m}{2}\)) e verificare se c'è un arco tra i due nodi (si suppone tempo costante \(C\)). Ho capito male il problema? Forse si chiede di trovare un insieme di dimensione massimale di ballerini in cui ogni ballerino dell'insieme non ha ballato con gli altri. In questo caso il problema diventa banalmente quello che hai indicato (nel senso che non solo è equivalente, ma è proprio quello).
"apatriarca":
Per prima cosa un chiarimento sul problema. Ti trovi con un grafo di m nodi (i ballerini) e un certo numero di archi, uno per ogni coppia che ha ballato insieme. Fin qui è corretto? A questo punto però stai cercando un algoritmo che stabilisca se esistono delle coppie di ballerini che non abbiano ballato insieme o vuoi trovare queste coppie? Oppure nessuna delle due cose?
Da come l'ho interpretato io.
Ci sono quattro tipi di insiemi:
- chi ha ballato in coppia
- l'attuale coppia
- chi non balla insieme (complementari)
- chi non ha ballato (complementari)
Bisogna sapere se esiste l'ultimo tipo insieme e sapere se è uguale a $k$, è un problema decisionale.
In effetti non avevo visto che si chiedeva che l'insieme avesse cardinalità \(k\). Questo cambia in effetti tutto..
Inizio con il ringraziarvi tutti per le risposte,
hamming_burst con certezza devo dimostrare che il mio problema risiede nella classe NP e per far ciò ho ipotizzato questo caso:
Prendiamo una istanza F del problema basandoci sull'esempio:
|k|=k=2
F={Marco, Ginevra}
F include C dove C={Adele, Luca, Ginevra, Marco, Marzio, Veronica} Elenco nomi ballerini
E={(Adele, Luca), (Luca, Ginevra), (Luca, Veronica), (Veronica, Marco)} Elenco coppie
Se F è soluzione del problema in tempo polinomiale, allora il problema è in NP.
F={n1, n2, n3, … ,nk) → insieme di k ballerini
" e E
se e unione F = insieme vuoto
allora termina, F è una soluzione del problema.
Il tempo richiesto per l'esecuzione di tale algoritmo è:
O(n) per effettuare il ciclo sull'insieme E delle coppie,
O(k) per l'esecuzione dell'unione tra i-esima coppia di E e gli elementi di F,
possiamo determinare che data un'istanza del problema, verifica in tempo polinomiale O(nk) la soluzione del nostro problema, dove n è la dimensione dei dati di ingresso e k una costante. il problema rientra nella categoria dei problemi NP in quanto risolvibile da una macchina di Turing non deterministica in tempo polinomiale. che ne pensi?
hamming_burst con certezza devo dimostrare che il mio problema risiede nella classe NP e per far ciò ho ipotizzato questo caso:
Prendiamo una istanza F del problema basandoci sull'esempio:
|k|=k=2
F={Marco, Ginevra}
F include C dove C={Adele, Luca, Ginevra, Marco, Marzio, Veronica} Elenco nomi ballerini
E={(Adele, Luca), (Luca, Ginevra), (Luca, Veronica), (Veronica, Marco)} Elenco coppie
Se F è soluzione del problema in tempo polinomiale, allora il problema è in NP.
F={n1, n2, n3, … ,nk) → insieme di k ballerini
" e E
se e unione F = insieme vuoto
allora termina, F è una soluzione del problema.
Il tempo richiesto per l'esecuzione di tale algoritmo è:
O(n) per effettuare il ciclo sull'insieme E delle coppie,
O(k) per l'esecuzione dell'unione tra i-esima coppia di E e gli elementi di F,
possiamo determinare che data un'istanza del problema, verifica in tempo polinomiale O(nk) la soluzione del nostro problema, dove n è la dimensione dei dati di ingresso e k una costante. il problema rientra nella categoria dei problemi NP in quanto risolvibile da una macchina di Turing non deterministica in tempo polinomiale. che ne pensi?
Alcune questioni linguistiche:
perchè include?
Direi $F \subseteq C$
meglio: se $F$ è soluzione del problema, verificabile in tempo polinomiale è in NP (lo hai scritto sotto cmq).
Penso sia da formalizzare il fatto che si parla di ballato in precedenza, che fa supporre che ci siano due sottinsiemi distinti come ho scritto, ma si può evitare e pensare che sia una frivolezza interpretativa.
La tua formalizzione comunque non funziona:
$E$ è un insieme di coppie (insieme di due elementi)
$F$ un insieme di elementi (ballerini)
es.
\(\text{(Adele, Luca)} \cup \text{{Marco, Ginevra}} = \text{{Adele, Luca,Marco, Ginevra}}\). L'insieme vuoto dubito che ti verrà mai fuori, forse intendevi l'intersezione...
\(\text{(Adele, Luca)} \cap \text{{Marco, Ginevra}} = \varnothing\)
ma non funziona anche con questa modifca, un controesempio:
\(\text{(Veronica, Marco)} \cap \text{{Marco, Ginevra}} = \{Marco\}\)
Sta a significare che se l'insieme vuoto è il fattore di terminazione non puoi utilizzare tale unione semplice (intendo a scoping non profondo) perchè se un ballerino è in coppia con qualcun'altro non in $F$ avrai un falso-positivo. L'insieme vuoto che intendi te è l'intersezione tra tutte le combinazioni semplici di due elementi di $F$ e l'insieme $E$.
In formule, io utilizzo il confronto invece che creare realmente un nuovo insieme da $F$:
\[\forall f_1,f_2 \in F,\nexists \in E\ |\ e_1 = f_1 \wedge e_2 = f_2\ ,\ f_1 \neq f_2\]
Complessità lascio a te, così vedi se è tutto chiaro. Se sì, basta continuare con l'altro punto più interessante.
"ncknm":
Prendiamo una istanza F del problema basandoci sull'esempio:
|k|=k=2
F={Marco, Ginevra}
F include C dove C={Adele, Luca, Ginevra, Marco, Marzio, Veronica} Elenco nomi ballerini
perchè include?
Direi $F \subseteq C$
"ncknm":
E={(Adele, Luca), (Luca, Ginevra), (Luca, Veronica), (Veronica, Marco)} Elenco coppie
Se F è soluzione del problema in tempo polinomiale, allora il problema è in NP.
meglio: se $F$ è soluzione del problema, verificabile in tempo polinomiale è in NP (lo hai scritto sotto cmq).
"ncknm":
$F={n_1, n_2, n_3, ... ,n_k}$ → insieme di k ballerini
\(e \in E\)
\(if\ e \cup F = \varnothing\)
allora termina, F è una soluzione del problema.
Il tempo richiesto per l'esecuzione di tale algoritmo è:
O(n) per effettuare il ciclo sull'insieme E delle coppie,
O(k) per l'esecuzione dell'unione tra i-esima coppia di E e gli elementi di F,
Penso sia da formalizzare il fatto che si parla di ballato in precedenza, che fa supporre che ci siano due sottinsiemi distinti come ho scritto, ma si può evitare e pensare che sia una frivolezza interpretativa.
La tua formalizzione comunque non funziona:
$E$ è un insieme di coppie (insieme di due elementi)
$F$ un insieme di elementi (ballerini)
es.
\(\text{(Adele, Luca)} \cup \text{{Marco, Ginevra}} = \text{{Adele, Luca,Marco, Ginevra}}\). L'insieme vuoto dubito che ti verrà mai fuori, forse intendevi l'intersezione...
\(\text{(Adele, Luca)} \cap \text{{Marco, Ginevra}} = \varnothing\)
ma non funziona anche con questa modifca, un controesempio:
\(\text{(Veronica, Marco)} \cap \text{{Marco, Ginevra}} = \{Marco\}\)
Sta a significare che se l'insieme vuoto è il fattore di terminazione non puoi utilizzare tale unione semplice (intendo a scoping non profondo) perchè se un ballerino è in coppia con qualcun'altro non in $F$ avrai un falso-positivo. L'insieme vuoto che intendi te è l'intersezione tra tutte le combinazioni semplici di due elementi di $F$ e l'insieme $E$.
In formule, io utilizzo il confronto invece che creare realmente un nuovo insieme da $F$:
\[\forall f_1,f_2 \in F,\nexists
Complessità lascio a te, così vedi se è tutto chiaro. Se sì, basta continuare con l'altro punto più interessante.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo