tag:blogger.com,1999:blog-3722233.post2989408900824206426..comments2021-02-24T08:40:40.300-06:00Comments on Computational Complexity: A candidate for a new Millenium ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-46172309525277399952011-10-01T04:36:21.246-05:002011-10-01T04:36:21.246-05:00If I had to nominate a problem in this general are...If I had to nominate a problem in this general area as a millennium problem, then my choice would be finding upper and lower bounds for Szemerédi's theorem that were broadly comparable. I feel that the original Erdös-Turán problem isn't suitable because it focuses attention on what may well be the wrong bound (roughly n/log n). And I also think that if the polynomial version of the problem is ever solved, the real conceptual leap forward, which is what I would want to reward with a million dollars, will have taken place with the linear case.<br /><br />There's a reasonable chance that this wouldn't make too much difference, since the way to beat the n/log n bound might well turn out to be "to understand properly what is going on" -- which would then lead to a proof that gave a bound of the correct type. But in the case of Roth's theorem, I think there is also a chance that someone will at some point manage, thanks to a heroic effort (similar to what Bateman and Katz recently did in the F_3^n case), to get just beyond the n/log n bound. And I also think that the correct bound for this problem is much better.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79664521039372910042011-09-29T09:23:51.682-05:002011-09-29T09:23:51.682-05:00AH- Anon, you misunderstand.
`The Millennuim probl...AH- Anon, you misunderstand.<br />`The Millennuim problems' are a real set of problems<br />and P =? NP is already one of them.<br /><br />The Poincare Conjecture was one of them and it was solved hence the question has been raised (I first saw it on<br />Godel's Last Letter Blog) of if there is a problem to<br />replace it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11729565093271797822011-09-28T22:29:51.784-05:002011-09-28T22:29:51.784-05:00what about P=NP?what about P=NP?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71634125960441491852011-09-28T14:24:21.658-05:002011-09-28T14:24:21.658-05:00Anon- Great Question.
The problems I propose will ...Anon- Great Question.<br />The problems I propose will involve LOTS of diff areas of mathematics (as did their analogs for VDW's theorem)<br />and this is certainly a PLUS.<br /><br />As to the problems INTRINSIC worth, this is indeed<br />debatable. Is it like FLT- LOTS of nice things come out of it but FLT is not, in and of itself, that interesting.<br />Or is it like P=?NP--- which is asking a very<br />important question? How do my problems compare to the<br />other Mil Prize Problems in this regard?<br /><br />1) My problem is certainly LESS intrinsically important than P=?NP and Navier-Strokes. <br />These deal with important problems motivated by<br />the real real world.<br /><br />2) Poincare's Conjecture (now Perelman's theorem)<br />and Riemann hypothesis--- These deal with objects<br />that people in math care about- primes and surfaces.<br />Do they have real world motivations as well?<br />Are Primes actually important? Harder to argue for<br />these, though I think most mathematicians would agree<br />that both are MORE intrinsically important than<br />my problems.<br /><br />3) Birch and Swinnerton-Dyer Conj, Hodge Conj,<br />Yang-Mills Theory, I do not pretend to know<br />about, but if a reader wants to fill us in on<br />their intrinsic importance, that will help the<br />discussion.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65676362823651536672011-09-28T13:34:50.609-05:002011-09-28T13:34:50.609-05:00Why should it be a Millennium problem?
Apologies, ...Why should it be a Millennium problem?<br />Apologies, but it looks like a very hard problem which has perhaps some interesting applications, but it doesn't seem to be so groundbreaking as other Millennium problems.Anonymousnoreply@blogger.com