[Algoritmi, Teoria] NP - COMPLETO / NP- HARD
Buongiorno a tutti, ho alcune domande da farvi che probabilmente vi aiuteranno a smaltire i pandori e panettoni 
Ho un problema in forma optimization problem, e devo scoprire se è np-hard o meno. Ho ridotto il problema ad un altro problema np-completo il quale però accetta solo problemi di forma decisionale ovviamente. Ora vi chiedo, come infulisce questo sul mio optimization problem? In teoria, visto che riduco ad un np-completo il mio problema è np-hard, visto che il mi problema sarà as hard as l'altro problema a cui riduco. Ma allora posso dire che il mio problema di partenza è np-hard perche è possibile trasormarlo in un problema decisionale che puo essere risolto da un np-completo?
Spero di non aver fatto troppa confusione, grazie e auguri!
Ho un problema in forma optimization problem, e devo scoprire se è np-hard o meno. Ho ridotto il problema ad un altro problema np-completo il quale però accetta solo problemi di forma decisionale ovviamente. Ora vi chiedo, come infulisce questo sul mio optimization problem? In teoria, visto che riduco ad un np-completo il mio problema è np-hard, visto che il mi problema sarà as hard as l'altro problema a cui riduco. Ma allora posso dire che il mio problema di partenza è np-hard perche è possibile trasormarlo in un problema decisionale che puo essere risolto da un np-completo?
Spero di non aver fatto troppa confusione, grazie e auguri!
Risposte
Devi dimostrare che in tempo polinomiale ti puoi ridurre ad un altro problema NP-Completo
"starsuper":
il mio problema di partenza è np-hard perche è possibile trasformarlo in un problema decisionale che puo essere risolto da un np-completo
Questa è praticamente la definizione di NP-Hard modulo una parola, ti do la versione giusta:
"starsuper":
Ma allora posso dire che il mio problema di partenza è np-hard perche è possibile trasformarlo polinomialmente in un problema decisionale che puo essere risolto da un np-completo
la domanda ora è: la tua riduzione del tuo problema di ottimizzazione a quello decisionale è polinomiale?
Se si hai finito. Se no diventa più complicato (perchè potrebbe o non potrebbe esistere una riduzione polinomiale dal tuo problema originale a quello di decisione).
Si, ho omesso una cosa fondamentale: polinomialmente. Ma in che senso la riduzione da ottimizzazione a decisionale deve essere polinomiale? Voglio dire, il problema decisionale lo "scegliamo" noi ed è quello di cui cerchiamo risposta Si/No.
Esempio, Bin Packing. Diciamo che vogliamo minimizzare il numero di bin usati (Optimization Problem).Esso può essere ridotto polinomialmente a Number Partition, ma quest'ultimo risponderebbe al problema decisionale associato al caso in cui i bins disponibili siano solo 2. Cioè "é possiible caricare n items di peso wi ciascuno all'interno di due bins?".
Si,No.
Questo è un esempio che ho trovato sul libro, ma nessuno parla di passaggio polinomiale da optimization a decsion. Anzi, si verifica che bin packing è np-complete proprio perchè viene ridotto ad un np-completo(Number Partition), ma nessuno spiega il passaggio da opt. a decisionale.
Esempio, Bin Packing. Diciamo che vogliamo minimizzare il numero di bin usati (Optimization Problem).Esso può essere ridotto polinomialmente a Number Partition, ma quest'ultimo risponderebbe al problema decisionale associato al caso in cui i bins disponibili siano solo 2. Cioè "é possiible caricare n items di peso wi ciascuno all'interno di due bins?".
Si,No.
Questo è un esempio che ho trovato sul libro, ma nessuno parla di passaggio polinomiale da optimization a decsion. Anzi, si verifica che bin packing è np-complete proprio perchè viene ridotto ad un np-completo(Number Partition), ma nessuno spiega il passaggio da opt. a decisionale.
Forse non ti è chiaro cosa significa "ridursi ad un altro problema NP-Completo".. L'idea in realtà è semplice: devi capire se un certo problema $P1$ è NP-Completo.. Considera un problema $P2$ che hanno dimostrato per intero essere NP-Completo (ad esempio SAT). Allora se riesce a trovare un algoritmo $A$ che mappa istanze del problema $P2$ in istanze del problema $P1$ in tempo polinomiale allora dimostri che anche $P1$ è NP-Completo: infatti se esistesse un certo algoritmo che risolve $P1$ in tempo polinomiale allora lo sarebbe anche $P2$ (per delle semplici proprietà dei polinomi che puoi verificare tu stesso).
A questo punto la dimostrazione è finita, non ha senso fare anche l'altro verso: SAT per ipotesi è NP-Completo, non puoi prendere il tuo algoritmo e rimapparlo in SAT.. sarebbe un cane che si morde la coda
A questo punto la dimostrazione è finita, non ha senso fare anche l'altro verso: SAT per ipotesi è NP-Completo, non puoi prendere il tuo algoritmo e rimapparlo in SAT.. sarebbe un cane che si morde la coda
Va meglio adesso. Quello che non capisco è: se io ho un problema di ottimizzazione, come puo essere NP-hard, mentre un suo analogo decision problem è np-completo? esempio https://en.wikipedia.org/wiki/Bin_packing_problem nelle prime righe si legge che nella forma optimization è np-hard, mentre nella forma decsionale è np-completo.
Non ho capito, come passare da un problema combinatorio ad uno decisionale. Posso capire che trovare un algoritmo polinomiale che mappi un'istanza di P2 in P1 abbia senso, ma come posso trasformare in tempo polinomiale un problema di ottimizzazione in decisionale?
Scusatemi ma continua a sfuggirmi qualcosa, ancora buone feste!
Edit: Da Wikipedia si legge che : "There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each N, to decide whether the graph has any tour with weight less than N. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.
Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as operations research."
Quindi se volessi dimostrare la complessità di un problema di ottimizzazione, non posso passare al suo analogo decisionale in maniera diretta? Supponiamo che per dimostrare la complessità di un problema di ottimizzazione P1, debba ridurlo ad un altro problema P2. Quest'ultimo problema però risolve solo il problema decisionale. Come trasformo il mio problema iniziale P1 in uno decisionale per poi poterlo ridurre al problema P2?
Non ho capito, come passare da un problema combinatorio ad uno decisionale. Posso capire che trovare un algoritmo polinomiale che mappi un'istanza di P2 in P1 abbia senso, ma come posso trasformare in tempo polinomiale un problema di ottimizzazione in decisionale?
Scusatemi ma continua a sfuggirmi qualcosa, ancora buone feste!
Edit: Da Wikipedia si legge che : "There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each N, to decide whether the graph has any tour with weight less than N. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.
Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as operations research."
Quindi se volessi dimostrare la complessità di un problema di ottimizzazione, non posso passare al suo analogo decisionale in maniera diretta? Supponiamo che per dimostrare la complessità di un problema di ottimizzazione P1, debba ridurlo ad un altro problema P2. Quest'ultimo problema però risolve solo il problema decisionale. Come trasformo il mio problema iniziale P1 in uno decisionale per poi poterlo ridurre al problema P2?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo