For which Millennium Problems does undecidable -> true? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T02:43:43Z http://mathoverflow.net/feeds/question/108433 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108433/for-which-millennium-problems-does-undecidable-true For which Millennium Problems does undecidable -> true? John Sidles 2012-09-30T01:56:35Z 2012-09-30T12:30:06Z <p>Gregory Chaitin <a href="http://www.maa.org/features/chaitin.html" rel="nofollow">has quoted Marcus du Sautoy</a> to the effect that:</p> <blockquote> <p>If the <em>Riemann Hypothesis</em> (RH) is undecidable this implies that it's true, because if the RH were false it would be easy to confirm that a particular zero of the zeta function is in the wrong place. </p> </blockquote> <p><strong>Question(s)</strong>&nbsp; Which of the other five (at present) unsolved <a href="http://www.claymath.org/millennium/" rel="nofollow">Clay Institute <em>Millenium Prize Problems</em></a> similarly have the attribute $\text{undecidable}\to\text{true}$? And do any of the five have the attribute $\text{undecidable}\to\text{false}$? </p> <hr> <p><strong>Context</strong>&nbsp; This question first arose in the discussion of "<a href="http://rjlipton.wordpress.com/2012/09/26/how-not-to-prove-integer-factoring-is-in-p/#comment-27171" rel="nofollow">a whole lot of basic questions</a>" that were asked by Tim Gowers on Dick Lipton and Ken Regan's weblog <em>G&ouml;del's Lost Letter and P-NP</em>. </p> <p><strong>Edit</strong>&nbsp;Dick and Ken subsequently posted an essay <a href="https://rjlipton.wordpress.com/2012/09/29/why-we-lose-sleep-some-nights/" rel="nofollow"><em>Why We Lose Sleep Some Nights</em></a> in which (<a href="http://rjlipton.wordpress.com/2012/09/29/why-we-lose-sleep-some-nights/#comment-27207" rel="nofollow">in&nbsp;a&nbsp;comment</a>) the question is associated to the <a href="http://en.wikipedia.org/wiki/Immanentize_the_eschaton" rel="nofollow"><em>immanence of the eschaton</em></a> (or perhaps not) in&nbsp;computational complexity theory. ☺</p>