tag:blogger.com,1999:blog-3722233.post6962839272142423312..comments2020-09-19T14:59:31.151-05:00Comments on Computational Complexity: Believing an open problem has been closedLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-3722233.post-21497134888469120082007-05-10T05:55:00.000-05:002007-05-10T05:55:00.000-05:00The Pati paper is incorrect, due to a circular cho...The Pati paper is incorrect, due to a circular choice of parameter definitions. On page 10 equations (10), (11), t is defined in terms of delta, and delta defined in terms of A_*, where A_* is to be defined "in the sequel". On page 13 equation (20), A_* is defined in terms of t. One cannot make all of these definitions simultaneously.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54575609956248309662007-05-09T20:22:00.000-05:002007-05-09T20:22:00.000-05:00FYI: The hotel reservation deadline for FCRC (inc...FYI: The hotel reservation deadline for FCRC (includes STOC, Complexity) is today.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7907972770107767952007-05-09T11:41:00.000-05:002007-05-09T11:41:00.000-05:00am I the only one who noticed that the variables t...am I the only one who noticed that the variables that Bill chose happened to be the initials of Bush Senior?Anonymoushttps://www.blogger.com/profile/16827659860728144034noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75393435028702345732007-05-07T23:32:00.000-05:002007-05-07T23:32:00.000-05:00Anyone reading the Computational Complexity postin...Anyone reading the Computational Complexity postings on the ArXiv can get at least a monthly chance at triage of this sort... <BR/><BR/>One doesn't need to rely on author names. There is a simple test to see if one should read on in a paper claiming some answer to a question like P vs NP:<BR/>The minimal standard is that the authors explain why their approach avoids the known pitfalls in the literature to answering the question such as: having an argument that relativizes, or using a natural proof argument. Any paper by reputable authors would discuss these issues.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74748262661992830172007-05-07T21:55:00.000-05:002007-05-07T21:55:00.000-05:00The best I can find on the Riemann paper via Googl...The best I can find on the Riemann paper via Googling are some mid-April comments by <A HREF="http://guests.mpim-bonn.mpg.de/kroetz/" REL="nofollow">Bernhard Kroetz</A> at the bottom of this <A HREF="http://www.arsmathematica.net/archives/2007/03/24/latest-paper-on-arxiv/" REL="nofollow">March 24 Ars Mathematica item</A>. He writes "Lemma 1 is correct" then "All Lemmas are correct." Terence Tao seems not to have a mention of it on his homepage or <A HREF="http://terrytao.wordpress.com/" REL="nofollow">blog</A>. Can someone take this further?<BR/><BR/>A comment relevant to both the matter at hand and to blog dynamics: <A HREF="http://comet.lehman.cuny.edu/sormani/others/smith.html" REL="nofollow">Penelope Smith</A> had titled her Navier-Stokes claim paper "Immortal Smooth Solution of the Three Space Dimensional Navier-Stokes System" (and another paper similarly noun, not process). She has a link to C. Sormani at CUNY, who in turn links to <A HREF="http://www.seedmagazine.com/news/2006/10/the_proof_is_in_the_blogging.php?page=2" REL="nofollow">this article</A> on how Peter Woit's "Not Even Wrong" blog focused the review and eventual deconstruction of the paper. I'd be curious to know of cases where blog discussion did paper construction as well. Overall I don't think the comments in this thread are hostile, and the long "anonymous" poster has some data and interesting things to say.KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-723649855168774302007-05-07T21:38:00.000-05:002007-05-07T21:38:00.000-05:00T. Hales. The Kepler Conjecture.OK, this is not en...T. Hales. The Kepler Conjecture.<BR/><BR/>OK, this is not entirely fair since it was preceded by a sequence of papers, but they had short titles like "Sphere Packing III".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-152515348779349582007-05-07T18:21:00.000-05:002007-05-07T18:21:00.000-05:00As a followup to the above, it seems that Appel an...As a followup to the above, it seems that Appel and Haken used six words to describe their original (computer assisted) proof of the Four-Color Theorem.<BR/><BR/>K. Appel and W. Haken, Every planar map is four colorable, Contemporary Math. 98 (1989).<BR/><BR/>I still know of no three-word (or shorter) title claiming a major result ... but I am pretty confident that such titles are out there!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77196431815329897342007-05-07T18:07:00.000-05:002007-05-07T18:07:00.000-05:00Here is another title that, like "Primes is in P",...Here is another title that, like "Primes is in P", needs only four words to claim a major mathematical result:<BR/><BR/>N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, J. Combin. Theory Ser. B. 70 (1997), 2-44. <BR/><BR/>So today's puzzler is, what is the shortest mathematical title that claims a major result? Is there one in three words or fewer?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71196189140379205662007-05-07T07:40:00.000-05:002007-05-07T07:40:00.000-05:00Ah, so THIS is how you get your name attached to a...Ah, so THIS is how you get your name attached to a conjecture! By having little or nothing to do with it! Say, Bill -- "naming theorems and conjectures after people" -- subject for another post?<BR/><BR/>(Of course, you may have meant another Green, in which case who? I mean, how many of us are there? :-)<BR/><BR/>Now, roughly speaking, this was the motivation of my original question: How many (good) people, if any, were paying attention to the claimed result?<BR/><BR/>So, following Bill's theme, given a paper purporting to prove a major theorem, how much attention A_N will you (the Nth reader of the paper) pay to it? Surely A_N is proportional to B and inversely proportional to H, but it's also proportional to the total attention that others have already payed to it, and how good (G_i) and articulate (W_i) those individuals were. This gives a possible recurrence relation (pardon the tex):<BR/><BR/> A_1 = G_1*B_1*W_1/H<BR/> A_N = (B/H)*(1/(N-1))\sum_{i=1}^{N-1} G_i*W_i*A_{i-1}.<BR/><BR/>And if A_N > C, you should read the paper. Of course I introduced this for one and only one reason: To name it Gasarch's Conjecture.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89681997676122034052007-05-06T21:56:00.000-05:002007-05-06T21:56:00.000-05:00(APOLOGIES- NOT ON TOPIC, BUTIMPORTANT WARNING- th...(APOLOGIES- NOT ON TOPIC, BUT<BR/>IMPORTANT WARNING- this blog<BR/>is set up so that if someone<BR/>links to it, it automatically<BR/>links back. Usually thats great,<BR/>BUT the link to Bill Gates<BR/>blog at bottom of the comments<BR/>is probably a phishing site-<BR/>DO NOT go to it. I'm looking into<BR/>how to remove it. DO not respond<BR/>to this, please resume your<BR/>on-topic comments.<BR/><BR/>Bill GasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22401579754821792852007-05-06T21:11:00.000-05:002007-05-06T21:11:00.000-05:00While I appreciate the feedback, I think this disc...While I appreciate the feedback, I think this discussion is too focused on why I'm wrong, vs. seriously dealing with Bill G and Fred G's question. In that spirit:<BR/><BR/>#1: this is the last comment I will post in this thread, as this will be my fourth.<BR/><BR/>#2: Anon 19, please consider re-reading my last comment, as what you wrote seems to indicate you did not notice that I included the title of Immerman's paper. Perhaps you skimmed and misunderstood my point.<BR/><BR/>#3: The real issue at hand here is "When should we believe an open problem is closed?"<BR/><BR/>If Karp, Immerman, Shelah, Wigderson, Agrawal, wrote a paper titled "P!=NP" then hell, yeah, I'm going to read it. But they have a long track record of deep theorems. However, if you run acorss a paper with the same title written by someone you've never heard of, then what are you going to do? Read it? Read all of them?<BR/><BR/>If you don't like my research criteria, OK, what are yours, and why are they better?<BR/><BR/>I go out of my way to read "unknown"/non-STOC-FOCS authors. I need a way to prioritize my time. It is true I came off strong in my earlier comments. That is because people who keep posting and reposting the same false proofs are doing all the rest of us a disservice. If a significant percentage of arxiv papers are lousy (and they are) it makes those of us who are busy more likely to read "safe" papers. <BR/><BR/>That in turn leads to what is called "mafioso" behavior. Read S. Arora's responses to accusations of a STOC/FOCS mafia. He basically said, "No, man, we're just busy!"<BR/><BR/>If an unknown author demonstrates, in title and abstract, that by reading the paper I will learn a new method or application, I am much more likely to read that paper. You don't have to agree with me, but if you want to comment on what I've said, please talk about a better way to read "non-big-name" papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67173785839950892012007-05-06T17:35:00.000-05:002007-05-06T17:35:00.000-05:0018: Only your first example demonstrates the "tre...18: Only your first example demonstrates the "trend" you've noticed. The other two titles state the problem that has been solved (or proved to be unsolvable); they don't refer to the technique used. They are analogous to naming your paper "P \ne NP" or "P = BPP". And in your next three examples, I see you conveniently chose Szelepcsnyi's paper to help make your point, since Immerman's contemporaneous "Nondeterministic Space is Closed Under Complementation" states the problem and its solution.<BR/><BR/>Funny thing is, I actually thought you were right before you started posting examples!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45586323668896294622007-05-06T16:05:00.000-05:002007-05-06T16:05:00.000-05:00I apologize if I'm writing too vaguely to be prope...I apologize if I'm writing too vaguely to be properly understood. Consider the following examples also:<BR/><BR/>1. Resolution of Fermat's Last Theorem.<BR/>2. Special Theory of Relativity<BR/>3. NPSPACE=co-NPSPACE<BR/><BR/>a. Modular Elliptic Curves and Fermat's Last Theorem<BR/>b. On the Electrodynamics of Moving Bodies<BR/>c. The Method of Forcing for Nondeterministic Automata.<BR/><BR/>There really is a pattern here.<BR/><BR/>Method-focused titles for big results are much more common than results-focused titles. Of course, both exist. In addition to "Primes in P" as an example, an alternative to (c) is the title of Immerman's paper, "Nondeterministic Space is Closed Under Complement."<BR/><BR/>The real contrast, though, comes when you examine, for instance, the papers on Stas Busygin's excellent P/NP page. 100% of those papers claiming to resolve P/NP feature the problem statement prominently in their titles, with the methods attempted receiving little or no mention.<BR/><BR/>I don't wish to be "hostile," but I am trying to convey something useful that took me many hours to learn: in the limited time you have to read papers by writers who are unknown (at least to you), it is my experience that the proof is more likely to go through if the author(s) is very clear about the proof techniques used, up front, and explains how these techniques can be used to solve other problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81397233538680279142007-05-06T13:35:00.000-05:002007-05-06T13:35:00.000-05:00My point is that (a) is not "I just won a million ...<I>My point is that (a) is not "I just won a million dollars," (b) is not "Hilbert was wrong again" and (c) is not "Hilbert's program is smashed."</I><BR/><BR/>A title like "P \neq NP" is not in the same category as a title like "I just won a million dollars" or a title that puts down other people...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13725608594704762132007-05-06T12:12:00.000-05:002007-05-06T12:12:00.000-05:00I'm starting to see the reason for Lance leaving t...I'm starting to see the reason for Lance leaving the blog. I might be wrong about this, but it might have to do with the bad vibes in the comments. Too much hostility...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53645430848033452712007-05-06T10:15:00.000-05:002007-05-06T10:15:00.000-05:00Dear Anon 12: Thank you for pointing out that exce...Dear Anon 12: Thank you for pointing out that exception, but you miss the trend if you focus on the counterexample. Can you match the following results to the following papers?<BR/><BR/>1. Resolution of the Poincare Conjecture.<BR/>2. Unsolvability of Diophantine equations.<BR/>3. Incompleteness Theorem<BR/><BR/>a. The entropy formula for the Ricci flow and its geometric applications.<BR/>b. The connection between Hilbertâ€™s Tenth Problem and systems of equations between words and lengths.<BR/>c. On Formally Undecidable Propositions in Principia Mathematica and Related Systems.<BR/><BR/>As you may know, the matching is 1a, 2b, 3c. My point is that (a) is not "I just won a million dollars," (b) is not "Hilbert was wrong again" and (c) is not "Hilbert's program is smashed."<BR/><BR/>FYI: Of note is that *Agrawal* has publicly stated on many occasions that he agrees with Anon 17, that PRIMES was already solved to everyone's contentment except his own and that of a few theoreticians, not a major result, etc. To my mind, this points to his high quality as a person. Still, I've skimmed hundreds of articles on the arxiv, and perhaps 90% of the ones that have "NP" in the title contain proofs I consider dubious or false.<BR/><BR/>I hope this helps.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29104049451380164582007-05-06T03:37:00.000-05:002007-05-06T03:37:00.000-05:00I see; you mean that they're likely worth looking ...<I>I see; you mean that they're likely worth looking at so long as they aren't titled something like "PRIMES is in P" or "RL is in SC"...</I><BR/><BR/>These problems (especially the second one) are not in the same status as that of P vs. NP, and even BPP vs. P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43478718838794137572007-05-05T23:12:00.000-05:002007-05-05T23:12:00.000-05:00What's an example of a similar problem that was se...<I>What's an example of a similar problem that was settled recently? How did people react?</I><BR/><BR/>One example of a problem which I can think of is the complexity of primality testing, which Agrawal, Kayal and Saxena showed to be in P. As yes, the paper was indeed titled "Primes is in P" - the first version of the paper, as well as the one published in Annals of Mathematics. And also I don't agree with the viewpoint that "<I>The papers you have to watch out for (the ones that waste your time) have titles like "The Riemann Hypothesis," "P does not Equal NP," etc.</I>", after all "Primes is in P" is indeed a perfect counterexample to this. It was not that the authors of the primality paper did not recognize the importance of their method. Their algorithm uses techniques like automorphism of finite fields, which are quite powerful and can possibly be used to derandomize other randomized algorithms as well. Probably the authors chose this name for the paper since it was a long standing open problem, and they <I>did</I> succeed in successfully solving the problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38781152672357284022007-05-05T21:43:00.000-05:002007-05-05T21:43:00.000-05:00Why don't those people publish their work in peer-...Why don't those people publish their work in peer-reviewed journals?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71424731526652073192007-05-05T20:07:00.000-05:002007-05-05T20:07:00.000-05:00I'm vaguely surprised de Branges and his resolving...I'm vaguely surprised de Branges and his resolving the Bieberbach Conjecture haven't come up yet.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63520644004015375032007-05-05T18:17:00.000-05:002007-05-05T18:17:00.000-05:00What's an example of a similar problem that was se...What's an example of a similar problem that was settled recently? How did people react?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56874421286604694522007-05-05T17:12:00.000-05:002007-05-05T17:12:00.000-05:00The papers you have to watch out for (the ones tha...<I>The papers you have to watch out for (the ones that waste your time) have titles like "The Riemann Hypothesis," "P does not Equal NP," etc.</I><BR/><BR/>I see; you mean that they're likely worth looking at so long as they aren't titled something like "PRIMES is in P" or "RL is in SC"...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70936756000242025662007-05-05T16:17:00.000-05:002007-05-05T16:17:00.000-05:00I would read papers by any of those guys, on any t...I would read papers by any of those guys, on any topic, period. There's a point not yet addressed, though, which is this: such a paper by a top mathematician would almost certainly not "claim to solve P/NP" as a major point of the title or abstract. The paper would be about a new methodology of approaching problems, prove some major theorems, and the nonrelativized separation of complexity classes would fall out of those theorems as a corollary. The papers you have to watch out for (the ones that waste your time) have titles like "The Riemann Hypothesis," "P does not Equal NP," etc. This is because those authors are blinded by their hope for fame and cannot see the importance of method.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43183767989696726152007-05-05T11:48:00.000-05:002007-05-05T11:48:00.000-05:00Yargh, too many negatives. You'd have to be some s...Yargh, too many negatives. You'd have to be some sort of idiot to think what I said (being the exact opposite of what I meant), thus my response to anon2. :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40229767108310841582007-05-05T10:05:00.000-05:002007-05-05T10:05:00.000-05:00... would you believe a paper by Bill Gasorch clai...... would you believe a paper by Bill Gasorch claiming to prove a n^{\Omega(1)} communication lower bound for the intersection function in the k-party NOF model?Anonymousnoreply@blogger.com