tag:blogger.com,1999:blog-3722233.post6523089462446502801..comments2024-05-16T12:04:28.523-05:00Comments on Computational Complexity: An undervalued Math ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-32990270836586130282009-11-30T16:22:50.568-06:002009-11-30T16:22:50.568-06:00If the conjecture is true, it would imply:
Whenev...If the conjecture is true, it would imply:<br /><br />Whenever both A and B lack arbitrarily large A.P.s, then so does their union.<br /><br />This would generalize Gleason's theorem (consider the contrapositive, and apply to a finite union which is all of N) but somehow, it doesn't seem particularly plausible.WorkingLadhttps://www.blogger.com/profile/05781702216580702505noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72865020852260234112009-11-27T13:49:09.662-06:002009-11-27T13:49:09.662-06:00I think that when the Clay problems were chosen - ...I think that when the Clay problems were chosen - the problem was not considered important in the "Hamming sense" - let me quote " `important problem' must be phrased carefully. The three outstanding problems in physics, in a certain sense, were never worked on while I was at Bell Labs...We didn't work on (1) time travel, (2) teleportation, and (3) antigravity. They are not important problems <br />because we do not have an attack". Things have change after Green/Tao and the transference principle.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37382982805901989872009-11-24T06:04:05.662-06:002009-11-24T06:04:05.662-06:00I solved all problems but feel a little too tired ...I solved all problems but feel a little too tired and selfish to share them here.cinnemannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3414475536371034082009-11-24T02:20:00.089-06:002009-11-24T02:20:00.089-06:00To be fair, I'm not sure that Erdos knew how m...To be fair, I'm not sure that Erdos knew how much harder that problem was than, for instance, Szemeredi's theorem. Glancing at the history, it seems to have been conjectured roughly contemporaneously with Szemeredi's proof, and I suspect that part of the reason the bounty's so high is that Erdos saw that the "incremental" arguments of Roth and Szemeredi wouldn't generalize to this case, and so the prize was offered to find different approaches to arithmetic Ramsey theorems. But even Furstenberg's ergodic methods aren't nearly strong enough to approach this conjecture -- indeed, I think Green and Tao's transference principle is the only thing we have (so far!) that allows us to do density Ramsey theory in a set of density zero.harrisonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75976873765331750202009-11-23T16:39:34.390-06:002009-11-23T16:39:34.390-06:00If it is solved quickly (very unlikely) then NO.
...<i>If it is solved quickly (very unlikely) then NO. </i><br /><br />In general important insights do not come by easily, but you should not confuse correlation with causality.<br /><br />For example, Frey's conjecture on Fermat's Last Theorem was based on an embarrasingly simple observation. It was surprising no one else noticed it before, but it was the key link connecting FLT to a rich area of mathematics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3696003337744606522009-11-23T14:31:25.994-06:002009-11-23T14:31:25.994-06:00There are a few lists of Erdős problems, but I don...There are a few lists of Erdős problems, but I don't know if anyone's compiled a comprehensive list. I've read that Erdős liked to throw out problems and prizes offhandedly, in talks and lectures, so a few might not be well-documented.<br /><br />Fan Chung has compiled a list of Erdős problems in graph theory:<br />http://math.ucsd.edu/~fan/ep.pdf<br /><br />Here's another partial list:<br />http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd<br /><br />It's interesting to ask whether the practice of offering cash prizes for problems has proven effective in getting problems solved more quickly.<br /><br />In the case of Erdős, I imagine it's the prestige (and pleasure) of cracking an Erdős problem that draws people in, not the cash. I don't know if small bounties by someone less prolific would prove as attractive!Anandhttps://www.blogger.com/profile/16850233492185797581noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14911129331239773132009-11-23T14:25:57.994-06:002009-11-23T14:25:57.994-06:00"Neither money nor politics should mix with m..."Neither money nor politics should mix with mathematics."<br /><br />Yes! Also, I should have a pony.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36470473598618896112009-11-23T13:15:53.368-06:002009-11-23T13:15:53.368-06:00Neither money nor politics should mix with mathema...Neither money nor politics should mix with mathematics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40482176295109667922009-11-23T13:14:09.637-06:002009-11-23T13:14:09.637-06:00the available space for the comment is not suffici...the available space for the comment is not sufficient to contain a full proof for this conjecture..Anonymousnoreply@blogger.com