tag:blogger.com,1999:blog-3722233.post8662824536602091064..comments2019-12-06T14:58:16.038-05:00Comments on Computational Complexity: Eight (yes eight) math problems worth $1,000,000Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-2998014520412847412008-09-18T09:14:00.000-04:002008-09-18T09:14:00.000-04:00Although the logic of the notion that should the G...Although the logic of the notion that should the GC be undecidable, it must be true is quite plain theoretically, I actually have a problem with it. It's easy to imagine numbers so large that no man made device will ever be able to verify them in relation to the GC. Just make them large enough for your own taste. This leaves us with undecidability on practical grounds. Until now it is undecidED, but unless we actually prove or disprove the GC, this state is practically indistinguishable from being undecidable.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33102124091129921032008-08-10T15:58:00.000-04:002008-08-10T15:58:00.000-04:00c above... (same guy)0, coz 0 is the representati...c above... (same guy)<BR/>0, coz 0 is the representation of nothinmathmadeEZnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37878828187672997322008-08-10T15:55:00.000-04:002008-08-10T15:55:00.000-04:00FOUND THE ANSWER!!! (u bin dun by a 11 year old.FOUND THE ANSWER!!! (u bin dun by a 11 year old.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65486168961622029082008-04-15T17:42:00.000-04:002008-04-15T17:42:00.000-04:00According to wikipedia, this is true only for the ...<I>According to wikipedia, this is true only for the "weak" Goldbach conjecture.</I><BR/><BR/>Right, we know that every large enough odd integer is the sum of three primes (that's <A HREF="http://en.wikipedia.org/wiki/Vinogradov%27s_theorem" REL="nofollow">Vinogradov's Theorem</A>), and that every large enough even integer is the sum of a prime and either a prime or a product of two primes. The example of these results does suggest that we're more likely to see Goldbach eventually proven for all sufficiently large integers than for all integers. And in that case, its truth for small integers might have to be established by computer search (maybe helped by GRH as with Vinogradov's Theorem), and could indeed be seen as "accidental."Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-796787279337009942008-04-15T17:28:00.000-04:002008-04-15T17:28:00.000-04:00Actually, there's a pretty big error in the book: ...Actually, there's a pretty big error in the book: Uncle Petros muses for a long time about Goldbach's conjecture being formally undecidable, completely missing that if it's undecidable then it has to be true.Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31047969249320130402008-04-14T20:25:00.000-04:002008-04-14T20:25:00.000-04:00I remember reading that Goldbach conjecture is kno...<EM>I remember reading that Goldbach conjecture is known to be true for all primes > some really large constant(something like 10^1000).</EM><BR/><BR/>According to wikipedia, this is true only for the "weak" Goldbach conjecture.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21551902274308300412008-04-14T19:03:00.000-04:002008-04-14T19:03:00.000-04:00I remember reading that Goldbach conjecture is kno...I remember reading that Goldbach conjecture is known to be true for all primes > some really large constant(something like 10^1000).<BR/><BR/>Thus the remaining case is just primes less than this constant. Is there a reason to believe there will be an elegant proof showing it for numbers less than 10^1000?<BR/><BR/>Could it just be that for numbers less than 10^1000 the conjecture holds accidentally, and for no good reason? I mean this is just a property of constantly many primes, probably if the conjecture went eitherway on these numbers, it probably wouldnt change anything about asymptotic distribution of primes..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69912310989319587382008-04-14T15:14:00.000-04:002008-04-14T15:14:00.000-04:00Spelling flame -- the first problem is named in pa...Spelling flame -- the first problem is named in part after <A HREF=HTTP://EN.WIKIPEDIA.ORG/WIKI/SWINNERTON-DYER HREF="" REL="nofollow">Sir Peter Swinnerton-Dyer</A>, who was on the faculty of Cambridge when I was there in 1981-2. His title was not conferred for his achievements in mathematics, as he is a baronet by birth, but his KBE and FRS presumably were.DaveMBwww.cs.umass.edu/~barringnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36445971640479463112008-04-14T14:48:00.000-04:002008-04-14T14:48:00.000-04:00The prize was offered by the British publisher Ton...The prize was offered by the British publisher Tony Faber, in 2000. [See Times of London article, Apr 16, 2000: http://tinyurl.com/5h5hh3].<BR/><BR/>It offered $1M to anyone solving the conjecture within two years of the offer, i.e. April 2002.<BR/><BR/>Pity, really, as it's an amazing problem. Simple statement, and apparently ridiculously hard to prove. =)nickstenninghttps://www.blogger.com/profile/03675001990722603034noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56411679726989859112008-04-14T13:32:00.000-04:002008-04-14T13:32:00.000-04:00The Wikipedia article http://en.wikipedia.org/wiki...The Wikipedia article http://en.wikipedia.org/wiki/Uncle_Petros_and_Goldbach's_Conjecture says that the Goldbach prize offer was only valid for two years (I guess 1992–1994).Anonymousnoreply@blogger.com