Timeline for Why is "P vs. NP" necessarily relevant?
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2023 at 6:34 | comment | added | Aravindh Krishnamoorthy | @GilKalai Thank you for the excellent answer. Would it be please possible to explain the following statement further: "A counterexample (which is not expected) may lead to a major change of our reality and not just our understanding of it." -> Do you mean the mathematical reality or computational complexity or something like the often-quoted (lay) example of music production (hard) vs discerning good music (relatively easy)? | |
| Mar 29, 2021 at 21:13 | comment | added | Gil Kalai | Hi Lucia, thank you! Gil | |
| Mar 27, 2021 at 19:10 | comment | added | Lucia | Hi Gil, I'd like to draw your attention to meta.mathoverflow.net/questions/4926/… | |
| Oct 18, 2018 at 18:20 | comment | added | Simd | Why is it regarded as implausible that a proof that P=NP might give a $n^{1000}$ time algorithm for popular np-hard problems? I mean once you condition on the implausible assumption that P=NP. | |
| Oct 18, 2018 at 17:30 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
minor typos
|
| Oct 29, 2015 at 16:01 | history | edited | Gil Kalai | CC BY-SA 3.0 |
added 58 characters in body
|
| Oct 29, 2015 at 16:00 | comment | added | Gil Kalai | Joshua, When I say "certain" I do not mean "there exist" but rather certain specific algorithmic problem. I edit my answer to make it clearer. | |
| Oct 29, 2015 at 15:56 | comment | added | Joshua Grochow | @GilKalai: I do not think P versus NP is the formulation - even morally - of the idea that certain algorithms require exponential time. The latter question is essentially P vs EXP, where we've known the answer for half a century. I think P versus NP is much closer to the formalization of the question of whether some algorithmic problems require brute force search (which is, conjecturally, just a small subset of EXP). However, perhaps the more relevant point is that whatever P vs NP formalizes, it is "just" a flagship conjecture indicative of a huge number of related open conjectures. | |
| Feb 28, 2011 at 16:40 | vote | accept | Andreas Thom | ||
| Feb 28, 2011 at 11:57 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 885 characters in body
|
| Feb 4, 2011 at 22:11 | comment | added | Suresh Venkat | There's a whole thread of examples for this too !! cstheory.stackexchange.com/questions/4491/… | |
| Feb 4, 2011 at 21:09 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 976 characters in body
|
| Feb 4, 2011 at 15:36 | comment | added | Timothy Chow | @Andreas: There's the ellipsoid method for linear programming, and the fully polynomial randomized approximation scheme for the permanent. | |
| Feb 4, 2011 at 7:08 | comment | added | Andreas Thom | Right. These examples show surprisingly good performance and a priori need exponential time. I was more asking for surprisingly bad performance and a priori polynomial time (but large constants). | |
| Feb 4, 2011 at 0:08 | comment | added | Suresh Venkat | There's a whole thread of examples :) cstheory.stackexchange.com/questions/305/… | |
| Feb 3, 2011 at 22:46 | comment | added | Andreas Thom | Thanks for this answer. Do you have other good examples where the asymptotic and the practical behavior (as you put it) differ drastically? | |
| Feb 3, 2011 at 22:34 | history | answered | Gil Kalai | CC BY-SA 2.5 |