Timeline for Why is "P vs. NP" necessarily relevant?
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Apr 15 at 8:54 | history | suggested | The Amplitwist | CC BY-SA 4.0 |
fixed broken link to Wikipedia; fixed Markdown list formatting of paragraphs
|
| Apr 15 at 6:43 | review | Suggested edits | |||
| S Apr 15 at 8:54 | |||||
| Oct 18, 2018 at 18:14 | comment | added | Simd | If P is proved not to equal NP it is possible the proof would be unsatisfactory in the sense that it gives no hint at all about the best possible complexities of NP hard problems except that it can’t be poly time. Similarly if NP is proved to equal P it may give no hint as to the exponents of the now poly time NP hard problems. That would be quite bad luck however. | |
| Oct 18, 2018 at 13:25 | history | edited | Martin Sleziak |
added the (np) tag - the question has been bumped anyway (by a new answer which is now deleted)
|
|
| Oct 21, 2014 at 19:22 | comment | added | user | @YaroslavBulatov: SAT is NP-complete, not NP-hard. | |
| Sep 20, 2012 at 20:41 | comment | added | vzn | in your writeup you raise issues very similar to this one, cs.se, "why polynomial time is called efficient" cs.stackexchange.com/questions/210/… | |
| Feb 28, 2011 at 16:40 | vote | accept | Andreas Thom | ||
| Feb 4, 2011 at 6:06 | comment | added | Theo Johnson-Freyd | The blogger @Yaroslav links to also wrote a post rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem which addresses some of your questions. | |
| Feb 4, 2011 at 3:16 | comment | added | Yaroslav Bulatov | There's also the converse, P!=NP but there's algorithm that solves any real-life NP-hard instance in a blink. For instance, SAT is NP-hard, but all SAT instances that "come up in practice" are easy -- rjlipton.wordpress.com/2009/07/13/… | |
| Feb 3, 2011 at 22:34 | answer | added | Gil Kalai | timeline score: 26 | |
| Feb 3, 2011 at 22:32 | history | edited | Andreas Thom | CC BY-SA 2.5 |
added 160 characters in body
|
| Feb 3, 2011 at 22:29 | answer | added | Timothy Chow | timeline score: 13 | |
| Feb 3, 2011 at 22:18 | answer | added | Henry Towsner | timeline score: 8 | |
| Feb 3, 2011 at 22:12 | comment | added | Qiaochu Yuan | Related (duplicate?): mathoverflow.net/questions/47954/… | |
| Feb 3, 2011 at 22:05 | comment | added | David Harris | The goal of complexity theory is not to describe the time scales that are relevant to humans. We humans are just passing by. If you insist that results be relevant to daily life, you are no longer doing mathematics. | |
| Feb 3, 2011 at 22:01 | answer | added | Greg Kuperberg | timeline score: 30 | |
| Feb 3, 2011 at 22:00 | comment | added | Andreas Thom | Thanks a lot for this comment. I hope that the examples show that my concerns do not root in ignorance; but rather question simplifying assumptions because of concrete instances where they seem to fail. | |
| Feb 3, 2011 at 21:43 | comment | added | aorq | "To me, dismissing complexity theory because of its love affair with worst-case, asymptotic analysis is like dismissing physics because of its love affair with frictionless surfaces, point particles, elastic collisions, and ideal springs and resistors. In both cases, people make the simplifying assumptions not because they’re under any illusions that the world really is that way, but rather because their goal is understanding." -- Scott Aaronson | |
| Feb 3, 2011 at 21:04 | history | asked | Andreas Thom | CC BY-SA 2.5 |