Definizione della classe NP
Ciao,
a breve dovrò affrontare l'orale di quel mega mostro di algoritmi e strutture dati...
Stò avendo qualche dubbio riguardante la parte di programma relativa all'intrattabilità dei problemi, vi prego di dirmi se quello che ho capito è corretto o se stò facendo confusione (ed eventualmente bacchettatemi pure e correggetemi !!!)
Da quello che ho capito se trovo un algoritmo POLINOMIALE per un certo problema quel problema appartiene alla classe P
Poi ho la classe dei problemi intrattabili (ovvero per i quali non ho algoritmi che li risolvano in tempo polinomiale). All'interno di tale classe vi è la sottoclasse NP che è una sotto classe dei problemi intrattabili che è molto ben caratterizzata.
La CARATTERISTICA DELLA CLASSE NP è la seguente: Non è noto alcun algoritmo polinomiale che risolva un problema in NP ma data una soluzione potenziale siamo in grado di testare in tempo polinomiale se questa soluzione potenziale fornita è soluzione del problema
Per affrontare meglio la caratterizzazione della classe NP intanto bisogna parlare di problemi e della loro versione decisionale.
Quando si parla di versione decisionale di un problema (o di problema decisionale) si intende la seguente cosa: CI CHIEDIAMO SOLO SE ESISTA UNA SOLUZIONE AL PROBLEMA DI PARTENZA, SENZA INTENTO DI CALCOLARLA.
Il problema decisionale risponde solo SI se esiste una soluzione o NO altrimenti.
Per fare un esempio si può usare il Problema di Cammino Hamiltoniano
Ho un problema P (ad esempio Cammino Hamiltoniano)
Ho un'istanza X del problema P (ad esempio un certo grafo G=(V,E) di cui voglio sapere se in G esiste un cammino hamiltoniano)
Ho una soluzione Y che posso considerare come fornitami da un ORACOLO (nel caso di cammino hamiltoniano ad esempio Y è una PERMUTAZIONE DI NODI rappresentante il cammino dei nodi all'interno del grafo G, quindi Y potrebbe essere qualcosa del tipo Y = {A, C, B, D}
Ora posso dire che se esiste un algoritmo A che in TEMPO POLINOMIALE mi risolve il problema decisionale, ovvero A(X,Y)=SI se X è istanza SI del problema originale e NO se X è istanza NO del problema originale. Allora il problema originale appartiene alla classe NP.
In altre parole nel caso del mio esempio posso dire che se esiste un algoritmo che prende in input un grafo G ed una permutazione di nodi Y mi calcola in tempo polinomiale se Y è un Cammino Hamiltoniano, allora il problema del Cammino Hamiltoniano appartiene alla classe NP
Ed in questo caso è vero e Cammino Hamiltoniano di fatto appartiene alla classe NP perchè tale algoritmo che risolve il problema decisionale in tempo polinomiale esiste ed è il seguente:
Guardo le coppie di nodi consecutive nella permutazione Y fornita e verifico se:
1) Per ogni nodo u,v tale che u PRECEDE v nella permutazione Y esiste in E un arco (u,v)
2) Verifico che la permutazione Y tocchi TUTTI i nodi del grafo G
3) Verifico che nella permutazione Y non ci siano permutazioni (perchè il problema del cammino hamiltoniano impone che non si possa passare 2 volte sullo stesso nodo)
Ognuna di tali operazioni può essere fatta in tempo polinomiale rispetto alla dimensione della soluzione Y fornita ---> la versione decisionale del problema del cammino hamiltoniano è polinomiale, quindi il problema originale di cammino hamiltoniano appartiene ad NP
Fin quì ok? ci stò?
Ora mi impippo un pochino sulla formalizzazione matematica di questa cosa...sulle dispense trovo le seguenti definzioni:
|X| è la lunghezza dell'istanza del problema di partenza (quindi riferendomi all'esempio di cammino hamiltoniano credo il numero di nodi in G, giusto?
Formalmente lui mi dice che:
Sia \( \Pi \) un PROBLEMA DECISIONALE e sia x una sua istanza di lunghezza |x|.
Allora \( \Pi \) appartiene alla classe NP se esiste un algoritmo polinomiale A ed un POLINOMIO p tali che se X ammette una soluzione (se X è un'istanza SI del problema originale) allora esiste una soluzione potenziale Y (chiamata anche certificato polinomiale, è l'istanza che viene fornita dall'oracolo all'algoritmo A) di lunghezza al più p(|x|) (deve essere polinomiale nella dimensione dell'istanza del problema originale) e tale che A(X,Y) = 1. Se invece X invece è un'istanza NO allora per ogni potenziale soluzione Y fornita da un oralcolo con Y di lunghezza al più p(|X|) allora A(X,Y) = 0
In pratica stà ripetendo la stessa cosa in maniera più formale ma mi impippo su questo fatto che la soluzione Y fornita dall'oracolo e da verificare deve essere polinomiale nella dimensione dell'istanza del problema X da verificare...
In pratica che vuol dire?
Io stò cercando di vederla nel seguente modo facendo sempre riferimento all'esempio di Cammino Hamiltoniano:
X è un particolare grafo G = (V,E) ed è un'istanza del problema di Cammino Hamiltoniano
Tale istanza X avrà una certa dimensione e per dimensione considero |V| cioè il NUMERO DEI NODI DEL GRAFO G.
Poi ho una soluzione Y fornita da un oracolo da verificare. Y è una PERMUTAZIONE DI NODI che rappresenta appunto un CAMMINO IN G. Tale permutazione avrà una dimensione |Y| che rappresenta la LUNGHEZZA DEL CAMMINO.
Uno dei requisiti per essere istanza SI è che devo toccare tutti i nodi del grafo G, quindi avrò che |Y| == |X| e quindi è sicuramente di dimensione polinomiale nella dimensione dell'input e di conseguenza l'algoritmo A quando prende in pasto l'istanza X e la soluzione Y potrà ritornare 1 in tempo polinomiale
Potrei anche aver un caso in cui mi viene fornita una soluzione Y da verificare rappresentata da una permutazione di nodi in cui passo 2 volte in ogni nodo, quindi |Y| 2*|X| che è comunque POLINOMIALE NELLA DIMENSIONE DELL'ISTANZA X DEL PROBLEMA, e di conseguenza l'algoritmo A potrà ritornare 0 in tempo polinomiale (perchè non è rispettato sicuramente la condizione per cui non devo passare 2 volte in uno stesso nodo)
Se invece fornissi soluzioni Y esponenziali nella dimensione delle istanze X del problema originale...beh allora non potrei verificare che Y è istanza si o istanza no in tempo polinomiale perchè nel caso specifico di cammino hamiltoniano dovrei scorrere permutazioni di dimensioni esponenziali rispetto a quelle dell'istanza del problema...
Più o meno come intuizione ci può stare o stò cannando tutto?
Per favore, è veramente importante questo esame per me (sono 2 anni che ci soffro dietro), datemi una manina
Grazie mille
Andrea
a breve dovrò affrontare l'orale di quel mega mostro di algoritmi e strutture dati...
Stò avendo qualche dubbio riguardante la parte di programma relativa all'intrattabilità dei problemi, vi prego di dirmi se quello che ho capito è corretto o se stò facendo confusione (ed eventualmente bacchettatemi pure e correggetemi !!!)
Da quello che ho capito se trovo un algoritmo POLINOMIALE per un certo problema quel problema appartiene alla classe P
Poi ho la classe dei problemi intrattabili (ovvero per i quali non ho algoritmi che li risolvano in tempo polinomiale). All'interno di tale classe vi è la sottoclasse NP che è una sotto classe dei problemi intrattabili che è molto ben caratterizzata.
La CARATTERISTICA DELLA CLASSE NP è la seguente: Non è noto alcun algoritmo polinomiale che risolva un problema in NP ma data una soluzione potenziale siamo in grado di testare in tempo polinomiale se questa soluzione potenziale fornita è soluzione del problema
Per affrontare meglio la caratterizzazione della classe NP intanto bisogna parlare di problemi e della loro versione decisionale.
Quando si parla di versione decisionale di un problema (o di problema decisionale) si intende la seguente cosa: CI CHIEDIAMO SOLO SE ESISTA UNA SOLUZIONE AL PROBLEMA DI PARTENZA, SENZA INTENTO DI CALCOLARLA.
Il problema decisionale risponde solo SI se esiste una soluzione o NO altrimenti.
Per fare un esempio si può usare il Problema di Cammino Hamiltoniano
Ho un problema P (ad esempio Cammino Hamiltoniano)
Ho un'istanza X del problema P (ad esempio un certo grafo G=(V,E) di cui voglio sapere se in G esiste un cammino hamiltoniano)
Ho una soluzione Y che posso considerare come fornitami da un ORACOLO (nel caso di cammino hamiltoniano ad esempio Y è una PERMUTAZIONE DI NODI rappresentante il cammino dei nodi all'interno del grafo G, quindi Y potrebbe essere qualcosa del tipo Y = {A, C, B, D}
Ora posso dire che se esiste un algoritmo A che in TEMPO POLINOMIALE mi risolve il problema decisionale, ovvero A(X,Y)=SI se X è istanza SI del problema originale e NO se X è istanza NO del problema originale. Allora il problema originale appartiene alla classe NP.
In altre parole nel caso del mio esempio posso dire che se esiste un algoritmo che prende in input un grafo G ed una permutazione di nodi Y mi calcola in tempo polinomiale se Y è un Cammino Hamiltoniano, allora il problema del Cammino Hamiltoniano appartiene alla classe NP
Ed in questo caso è vero e Cammino Hamiltoniano di fatto appartiene alla classe NP perchè tale algoritmo che risolve il problema decisionale in tempo polinomiale esiste ed è il seguente:
Guardo le coppie di nodi consecutive nella permutazione Y fornita e verifico se:
1) Per ogni nodo u,v tale che u PRECEDE v nella permutazione Y esiste in E un arco (u,v)
2) Verifico che la permutazione Y tocchi TUTTI i nodi del grafo G
3) Verifico che nella permutazione Y non ci siano permutazioni (perchè il problema del cammino hamiltoniano impone che non si possa passare 2 volte sullo stesso nodo)
Ognuna di tali operazioni può essere fatta in tempo polinomiale rispetto alla dimensione della soluzione Y fornita ---> la versione decisionale del problema del cammino hamiltoniano è polinomiale, quindi il problema originale di cammino hamiltoniano appartiene ad NP
Fin quì ok? ci stò?
Ora mi impippo un pochino sulla formalizzazione matematica di questa cosa...sulle dispense trovo le seguenti definzioni:
|X| è la lunghezza dell'istanza del problema di partenza (quindi riferendomi all'esempio di cammino hamiltoniano credo il numero di nodi in G, giusto?
Formalmente lui mi dice che:
Sia \( \Pi \) un PROBLEMA DECISIONALE e sia x una sua istanza di lunghezza |x|.
Allora \( \Pi \) appartiene alla classe NP se esiste un algoritmo polinomiale A ed un POLINOMIO p tali che se X ammette una soluzione (se X è un'istanza SI del problema originale) allora esiste una soluzione potenziale Y (chiamata anche certificato polinomiale, è l'istanza che viene fornita dall'oracolo all'algoritmo A) di lunghezza al più p(|x|) (deve essere polinomiale nella dimensione dell'istanza del problema originale) e tale che A(X,Y) = 1. Se invece X invece è un'istanza NO allora per ogni potenziale soluzione Y fornita da un oralcolo con Y di lunghezza al più p(|X|) allora A(X,Y) = 0
In pratica stà ripetendo la stessa cosa in maniera più formale ma mi impippo su questo fatto che la soluzione Y fornita dall'oracolo e da verificare deve essere polinomiale nella dimensione dell'istanza del problema X da verificare...
In pratica che vuol dire?
Io stò cercando di vederla nel seguente modo facendo sempre riferimento all'esempio di Cammino Hamiltoniano:
X è un particolare grafo G = (V,E) ed è un'istanza del problema di Cammino Hamiltoniano
Tale istanza X avrà una certa dimensione e per dimensione considero |V| cioè il NUMERO DEI NODI DEL GRAFO G.
Poi ho una soluzione Y fornita da un oracolo da verificare. Y è una PERMUTAZIONE DI NODI che rappresenta appunto un CAMMINO IN G. Tale permutazione avrà una dimensione |Y| che rappresenta la LUNGHEZZA DEL CAMMINO.
Uno dei requisiti per essere istanza SI è che devo toccare tutti i nodi del grafo G, quindi avrò che |Y| == |X| e quindi è sicuramente di dimensione polinomiale nella dimensione dell'input e di conseguenza l'algoritmo A quando prende in pasto l'istanza X e la soluzione Y potrà ritornare 1 in tempo polinomiale
Potrei anche aver un caso in cui mi viene fornita una soluzione Y da verificare rappresentata da una permutazione di nodi in cui passo 2 volte in ogni nodo, quindi |Y| 2*|X| che è comunque POLINOMIALE NELLA DIMENSIONE DELL'ISTANZA X DEL PROBLEMA, e di conseguenza l'algoritmo A potrà ritornare 0 in tempo polinomiale (perchè non è rispettato sicuramente la condizione per cui non devo passare 2 volte in uno stesso nodo)
Se invece fornissi soluzioni Y esponenziali nella dimensione delle istanze X del problema originale...beh allora non potrei verificare che Y è istanza si o istanza no in tempo polinomiale perchè nel caso specifico di cammino hamiltoniano dovrei scorrere permutazioni di dimensioni esponenziali rispetto a quelle dell'istanza del problema...
Più o meno come intuizione ci può stare o stò cannando tutto?
Per favore, è veramente importante questo esame per me (sono 2 anni che ci soffro dietro), datemi una manina
Grazie mille
Andrea
Risposte
Occhio che $P subseteq NP$ quindi non è vero che i problemi in NP non possono essere risolti da un algoritmo efficiente (= che lavora in tempo polinomiale). Sono i problemi NP-completi (una sottoclasse dei problemi in NP) ad essere considerati non risolubili in tempo polinomiale. Il resto del tuo post non ho però il tempo di leggerlo ora, magari più tardi.
"Deckard":
Occhio che $P subseteq NP$ quindi non è vero che i problemi in NP non possono essere risolti da un algoritmo efficiente (= che lavora in tempo polinomiale). Sono i problemi NP-completi (una sottoclasse dei problemi in NP) ad essere considerati non risolubili in tempo polinomiale. Il resto del tuo post non ho però il tempo di leggerlo ora, magari più tardi.
Si grazie per la precisazione...hai ragione !!!
Per favore, lo sò che è lunghetto ma se riesci a trovare il tempo di leggerlo (anche domani, con calma) e di dirmi te ne sarei estremamente grato...stò un po' nella disperazione rara...
Grazie
Andrea
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo