Timeline for Is there a lower bound for the computational complexity of the traveling salesman problem?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 13, 2017 at 4:20 | comment | added | usul | This question is confusing because you mention P=NP in your last sentence, but the previous one sounds like you do not understand the P vs NP problem and the how the TSP relates to it... | |
| Nov 12, 2017 at 23:25 | comment | added | Sasho Nikolov | @DendiSuhubdy What does this fact about random TSP instances have to do with the computational complexity of the problem? | |
| Nov 12, 2017 at 18:19 | answer | added | Timothy Chow | timeline score: 11 | |
| Nov 12, 2017 at 15:42 | comment | added | Dendi Suhubdy | See the Beardwood–Halton–Hammersley Theorem theoremoftheday.org/OR/BHH/TotDBHH.pdf | |
| Nov 12, 2017 at 15:12 | answer | added | user117147 | timeline score: 8 | |
| Nov 12, 2017 at 14:45 | comment | added | Emil Jeřábek | The existence of such a thing is equivalent to P = NP. Hence we can’t. | |
| Nov 12, 2017 at 14:26 | history | asked | Simon Rose | CC BY-SA 3.0 |