Timeline for For which Millennium Problems does undecidable -> true?
Current License: CC BY-SA 3.0
37 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Apr 19, 2014 at 17:57 | history | edited | John Sidles | CC BY-SA 3.0 |
numerous clarifications and grammatical improvements
|
| S Apr 18, 2014 at 15:47 | history | bounty ended | John Sidles | ||
| S Apr 18, 2014 at 15:47 | history | notice removed | John Sidles | ||
| Apr 18, 2014 at 0:44 | history | made wiki | Post Made Community Wiki by Todd Trimble | ||
| Apr 18, 2014 at 0:43 | comment | added | Todd Trimble | Made CW at OP's request. | |
| Apr 18, 2014 at 0:34 | history | edited | John Sidles | CC BY-SA 3.0 |
plausibly -> conceivably
|
| Apr 18, 2014 at 0:22 | history | edited | John Sidles | CC BY-SA 3.0 |
Summary of answer
|
| Apr 17, 2014 at 23:07 | vote | accept | John Sidles | ||
| Apr 14, 2014 at 9:49 | comment | added | John Sidles | On Dick Lipton and Ken Regan's weblog Godel's Lost Letter and P=NP, I have posted a comment that summarizes the CMI's Millennium Prize criteria, together with a link to Dick and Ken's favorite Far Side cartoon: "The One Where They're Lighting Their Arrows". | |
| Apr 12, 2014 at 0:45 | answer | added | Terry Tao | timeline score: 19 | |
| Apr 11, 2014 at 17:35 | answer | added | Alex Gavrilov | timeline score: 17 | |
| Apr 11, 2014 at 16:52 | comment | added | Włodzimierz Holsztyński | You're talking about the Millennium problems, and you are offering only a 100pt bounty? I guess, when it is only a single "n" instead of "nn" then the prize is lower. | |
| Apr 11, 2014 at 16:37 | answer | added | Bjørn Kjos-Hanssen | timeline score: 21 | |
| Apr 11, 2014 at 14:30 | history | edited | Ricardo Andrade |
added top level tag
|
|
| Apr 11, 2014 at 13:48 | comment | added | John Sidles | @Ansgar, one counterintuitive obstruction (of many) that makes the assertion P=NP surprisingly difficult to verify, even if it's true, is the formal possibility --- which is excluded neither by existing mathematical knowledge nor by the Clay Institute problem statement for PvsNP --- that P=NP for languages whose membership in P is affirmed by an oracle yet not decidable in ZFC. The TCS Stackexchange community wiki "Does P contain languages whose existence is independent of PA or ZFC?" surveys these considerations. Oracles are tricky! | |
| Apr 11, 2014 at 13:21 | comment | added | Ansgar Esztermann | Somewhat related: NP captures something about the nature of a proof: proofs are (in general) hard to find but (by definition) easy to check. Therefore, if $P\neq NP$, proving this might be very hard (or even infeasible). If, on the other hand, $P=NP$, a proof should be much easier to find. | |
| S Apr 11, 2014 at 12:31 | history | bounty started | John Sidles | ||
| S Apr 11, 2014 at 12:31 | history | notice added | John Sidles | Canonical answer required | |
| Apr 11, 2014 at 12:28 | history | edited | John Sidles | CC BY-SA 3.0 |
Preparing to offer bounty
|
| Sep 30, 2012 at 21:12 | comment | added | Thierry Zell | @Denis: You might be thinking of a result from Erdos that I learned in proofs from THE BOOK: suppose $\lbrace f_\alpha \rbrace$ is a family of holomorphic functions such that when you evaluate the family at some fixed $z\in \mathbb{C}$, you can only get countably many values. Then, $\neg CH$ implies that such a family must itself be countable, but there are such families of continuum size if $CH$ holds. There is a link to the original paper in this MO answer: mathoverflow.net/questions/1924/… | |
| Sep 30, 2012 at 19:53 | comment | added | HJRW | Ben - yes, but the proof that one can decide if a 3-manifold is simply connected relies on the Poincare Conjecture! So that reasoning is circular. | |
| Sep 30, 2012 at 19:39 | comment | added | Denis Serre | This reminds me the situation with the continuum hypothesis (CH), which is known to be undecidable in ZFC theory. There is statement that under CH, there exists an entire holomorphic function with some property P about its zero; and the opposite, under the negation of CH, there does not exist such a function. I apologize for having forgotten what is P. | |
| Sep 30, 2012 at 19:03 | comment | added | Ben Wieland | It is undecidable whether a 2-complex is simply connected, but it is decidable whether a 3-manifold is simply connected. (This should not be shocking to someone who know how to make a 4-manifold with arbitrary fundamental group.) | |
| Sep 30, 2012 at 12:30 | history | edited | John Sidles | CC BY-SA 3.0 |
Godel's lost letter and the "immanence of the eschaton"
|
| Sep 30, 2012 at 6:54 | comment | added | HJRW | Will - yes, but the undecidable bit is to prove that a CW-complex is not simply connected. There is a partial algorithm that terminates if and only if an input CW-complex is simply connected or, equivalently, an group presentation presents the trivial group, and this is enough for these purposes. The partial algorithm simply tries to write each generator as a product of conjugates of relators. | |
| Sep 30, 2012 at 6:48 | comment | added | Will Sawin | @HW: Isn't computing whether a CW-complex is simply-connected an undecidable problem? | |
| Sep 30, 2012 at 6:25 | comment | added | HJRW | Like the Riemann Hypothesis, the Poincar\'e Conjecture (which is, of course, now known to be true) also had the property that there is an algorithm to find a counterexample. Rubinstein described an algorithm that determines whether or not a 3-manifold is the 3-sphere. On the other hand, a naive procedure will eventually confirm if any CW-complex is simply connected. | |
| Sep 30, 2012 at 5:59 | comment | added | Will Sawin | If an elliptic curve has rank at least $n$ we can always write down $n$ rational solutions. If the $L$-function has a zero of order less than $n$ at $s=1$ then we can determine this by accurately approximating a contour integral in sufficiently small loop around $s=1$, which I think is always possible. If this works then undecidability of BSD implies that the analytic rank is greater than the algebraic rank. The other inequality appears more elusive. | |
| Sep 30, 2012 at 4:01 | comment | added | Harry Altman | So if I understand correctly, this is essentially asking which of these statements are equivalent to a $\Pi_1^0$ statement, right? | |
| Sep 30, 2012 at 3:19 | comment | added | Andrés E. Caicedo | @zeb: "True" means "true in the standard model". | |
| Sep 30, 2012 at 3:11 | comment | added | zeb | What if a different model of set theory contained an extra complex number that violated the Riemann Hypothesis? Or a nonstandard natural number violating one of the equivalent finitary statements? Would you still consider the Riemann Hypothesis to be a "true" statement? | |
| Sep 30, 2012 at 3:03 | comment | added | Noam D. Elkies | The point is that if there's a counterexample then one can prove it by a contour integral: no need to actually locate the zero, only to prove there's one in a circle disjoint from the critical line. | |
| Sep 30, 2012 at 2:51 | comment | added | Andrés E. Caicedo | @darij: This is the point of mathoverflow.net/questions/31846/… | |
| Sep 30, 2012 at 2:17 | comment | added | darij grinberg | I don't understand the RH argument. Complex numbers can be arbitrarily complicated (as Chaitin himself should know best!). One can easily find a sequence that is Cauchy if and only if your favorite Turing machine halts. | |
| Sep 30, 2012 at 2:05 | history | edited | John Sidles | CC BY-SA 3.0 |
Spell millennium correctly. Doh!
|
| Sep 30, 2012 at 1:56 | history | asked | John Sidles | CC BY-SA 3.0 |
