Timeline for Why is "P vs. NP" necessarily relevant?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 4, 2011 at 5:44 | comment | added | Greg Kuperberg | Maybe you're discussing it as an applied problem, whereas I view it as a pure problem? I think that it would be a cruel outcome because, as Gil says, people believe that NP-hard problems (those that are NP-hard in the Karp-reducible sense) take exponential time. | |
| Feb 3, 2011 at 22:47 | comment | added | Andreas Thom | Thanks for your answer. However, my point was not that "Every once in a blue moon, mathematics is a little bit cruel.", but that there are concrete and natural instances where constants are just too big. Gurevich ends his note (see the link in Timothy Chow's answer) by saying "A good theory of non-asymptotic complexity is a biggest challenge of all in the area. | |
| Feb 3, 2011 at 22:01 | history | answered | Greg Kuperberg | CC BY-SA 2.5 |