Problemi NP
Provare che il seguente problema è NP:
Problema:
Dato un array a[1...n] ed un naturale k, esiste un sottoinsieme di S di {1...n} tale che la somma degli a con i in S è uguale a K ossia K = sommatoria i appartententi a S a[1]
Io ho provato a risolvarlo in questo modo: dato che noi dobbiamo considerare in quanti modi è possibile gestire i nostri elementi n dell' insieme S, il numero totale di combinazioni sarà 2^n. Per ciascuna di queste 2^n combinazione dobbiamo verificare se avviene la seguente proprietà "...che la somma degli a con i in S è uguale a K ossia K = sommatoria i appartententi a S a[1]". Questo confronto avrà complessità lineare, ma tutte le possibilità combinazioni sono state create con un algoritmo di complessità 2^n, pertanto il problema è NP.
La mia risposta è giusta? come si può migliorare? Ma secondo voi si dovrebbe pure scrivere un algoritmo? Perchè questo è un vecchio tema d' esame su cui mi sto esercitanto ma non ho capito se la risposta deve essere concettuale come l' ho detta io prima oppure in forma di algoritmo.
Grazie mille ragazzi!!
Problema:
Dato un array a[1...n] ed un naturale k, esiste un sottoinsieme di S di {1...n} tale che la somma degli a con i in S è uguale a K ossia K = sommatoria i appartententi a S a[1]
Io ho provato a risolvarlo in questo modo: dato che noi dobbiamo considerare in quanti modi è possibile gestire i nostri elementi n dell' insieme S, il numero totale di combinazioni sarà 2^n. Per ciascuna di queste 2^n combinazione dobbiamo verificare se avviene la seguente proprietà "...che la somma degli a con i in S è uguale a K ossia K = sommatoria i appartententi a S a[1]". Questo confronto avrà complessità lineare, ma tutte le possibilità combinazioni sono state create con un algoritmo di complessità 2^n, pertanto il problema è NP.
La mia risposta è giusta? come si può migliorare? Ma secondo voi si dovrebbe pure scrivere un algoritmo? Perchè questo è un vecchio tema d' esame su cui mi sto esercitanto ma non ho capito se la risposta deve essere concettuale come l' ho detta io prima oppure in forma di algoritmo.
Grazie mille ragazzi!!
Risposte
Credo tu abbia un po' di confusione su "cosa" sia la classe NP. Prova a riguardarti le definizioni, in particolar modo quella che sfrutta il concetto di "certificato polinomiale".
E poni attenzione al fatto che da nessuna parte c'è scritto che se un linguaggio non è decidibile in tempo polinomiale allora visto che non è in P è in NP (che è l'argomento che tu hai erroneamente utilizzato). Inoltre la tua dimostrazione di questo fatto è comunque non corretta: perchè il tuo algoritmo non è polinomiale non è detto che non ce ne sia uno tale.
E poni attenzione al fatto che da nessuna parte c'è scritto che se un linguaggio non è decidibile in tempo polinomiale allora visto che non è in P è in NP (che è l'argomento che tu hai erroneamente utilizzato). Inoltre la tua dimostrazione di questo fatto è comunque non corretta: perchè il tuo algoritmo non è polinomiale non è detto che non ce ne sia uno tale.
come si potrebbe giustificare allora il fatto che è NP?
Non voglio la pappa pronta, è che questo argomento non lo capisco proprio e quando cerco su internet trovo tutte cose teoriche e nessun esercizio pratico, dunque ti chiedo anche se hai qualche sito dove sono esposti esercizi perchè io finora non li ho trovati.
Non voglio la pappa pronta, è che questo argomento non lo capisco proprio e quando cerco su internet trovo tutte cose teoriche e nessun esercizio pratico, dunque ti chiedo anche se hai qualche sito dove sono esposti esercizi perchè io finora non li ho trovati.
Per del materiale ti consiglio di guardare nell'aposita sezione del forum (è li per quello 
):
- https://www.matematicamente.it/forum/pos ... tml#479901 sezione Algoritmi Avanzati e il link sugli algoritmi di ottimizzazione
- https://www.matematicamente.it/forum/pos ... tml#496939 guarda pure qua, di sicuro trovi qualcosa.
per il tuo problema, a me pare la versione decisionale del problema "Subset sum".
Un modo classico per dimostrare che un problema è NP (NP-Hard il primo step) è utilizzare la riducibilità polinomiale.
ma come dice Deckard ti consiglio pure io di vederti le difinizioni, l'argomento è piuttosto vasto
PS: se vuoi un libro valido con molti esercizi pratici ti consiglio "Algoritmi e Strutture Dati - 2° edizione" Bertossi e Montresor
per la teoria c'è il classico libro Cormen, ma su questi argomenti pure io ho trovato difficolta a svolgere esercizi formalmente corretti.
):- https://www.matematicamente.it/forum/pos ... tml#479901 sezione Algoritmi Avanzati e il link sugli algoritmi di ottimizzazione
- https://www.matematicamente.it/forum/pos ... tml#496939 guarda pure qua, di sicuro trovi qualcosa.
per il tuo problema, a me pare la versione decisionale del problema "Subset sum".
Un modo classico per dimostrare che un problema è NP (NP-Hard il primo step) è utilizzare la riducibilità polinomiale.
ma come dice Deckard ti consiglio pure io di vederti le difinizioni, l'argomento è piuttosto vasto
PS: se vuoi un libro valido con molti esercizi pratici ti consiglio "Algoritmi e Strutture Dati - 2° edizione" Bertossi e Montresor
per la teoria c'è il classico libro Cormen, ma su questi argomenti pure io ho trovato difficolta a svolgere esercizi formalmente corretti.
"ham_burst":
per il tuo problema, a me pare la versione decisionale del problema "Subset sum".
Un modo classico per dimostrare che un problema è NP (NP-Hard il primo step) è utilizzare la riducibilità polinomiale.
Utilizzando la riducibilità polinomiale tu non dimostri che un problema è NP, ma al più che è NP-hard. Ma non tutti i linguaggi NP-hard appartengono a NP (e allo stesso modo un linguaggio in NP non deve essere per forza completo).
Secondo me, giorgio90p, non hai ben compreso la definizione di NP: compresa quella l'esercizio diventa molto semplice; è per questo che ti ho detto semplicemente di riguardarti la (le) definizioni della classe NP.
In effetti è abbastanza semplice, come dice Deckard. Qual è la definizione di linguaggio appartenente a NP sul tuo testo o dispensa che sia?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo