Timeline for How Reduction works in proving NP-Hard?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 22, 2019 at 18:11 | comment | added | David Richerby | @KGhatak That's not very interesting. $\mathrm{P}\subseteq\mathrm{NP}$ and TSP is $\mathrm{NP}$-complete so we already know that every problem in $\mathrm{P}$ reduces to TSP. We have much more efficient ways of solving problems that are in $\mathrm{P}$, though. | |
| Jul 22, 2019 at 17:22 | comment | added | KGhatak | @ David Richerby Thanks for the definiteness in your response. It helps big time. Wondering what happens if someone comes with a curious case of reducing a problem in $P$ to TSP! | |
| Jul 22, 2019 at 15:48 | comment | added | David Richerby | @KGhatak No, you can't say anything about $\overline{X_1}$. But TSP is still hard overall because its hardest instances let you solve HAM-CYCLE. | |
| Jul 22, 2019 at 14:59 | comment | added | KGhatak | Sorry if I'm missing something trivial. The problem I'm trying to solve is to find out how hard is any $TSP$ (NOT trying to find out how hard is HAM-CYCLE using knowledge of $TSP$ ). All I know is how to solve HAM-CYCLE, and how to transform each HAM-CYCLE to a $TSP$. With this, we divide all instances of TSP into two sets $X_1$ and $\overline{X_1}$ where $X_1$ includes all instances reducible from HAM-CYCLE. Given this set-up, my understanding is that I can say all TSP instances in $X_1$ are as hard as HAM-CYCLE. But I'm not sure if I can comment something about those in $\overline{X_1}$. | |
| Jul 22, 2019 at 9:44 | history | answered | David Richerby | CC BY-SA 4.0 |