On Friday, August 6, Vinay Deolalikar sent me and 21 of my closest frinds an email entitled "Proof announcement: P is not equal to NP". I took a quick look and white it did look better that most P/NP proof attempts (in the sense that Deolalikar doesn't make up his own notation), I spotted the following line in his write-up:
Distributions computed by LFP must satisfy this model.Many P versus NP attempts work by claiming that a polynomial-time algorithm must act a certain way forgetting that an algorithm can completely ignore any semantic meaning in the problem. Since LFP is just a fancy way of saying "polynomial-time algorithm", it looked like Deolalikar fell into the same trap. So I filed the paper into my Why Me? folder as I have with many many others and figured that was the end of that.
As you readers all know, on Sunday the 8th the paper was slashdotted and Lipton, impressed that Deolalikar worked on infinite Turing machines (whatever they are), posted on the proof saying he was "certainly hopeful". People then flooded with me with emails, tweets and instant messages asking me about the paper.
I read over Lipton's post and took another look at the paper and still didn't see the semantic approach outlined in the paper as a viable attack on the P versus NP problem. At this point I knew people I trust would look over the paper carefully so I wouldn't have too. I couldn't keep completely quiet so I tweeted
Much ado about an unverified proof. The word "must" is troubling. I'll let others check it carefully.In retrospect I should have been more negative. Kudos to Scott for taking a strong and risky stance.
The emails kept coming but I remembered my vacation message was still active and I didn't have to answer them. I went to Santa Fe and didn't check email until I returned.
There are two camps in our community on Deolalikar's paper. Those of us who saw Deolalikar's paper as just another in a long series of bad attempts at P v NP and wondering what all the fuss was about. And those who thought Deolalikar hit upon a new proof paradigm and despite the numerous problems, big and small, with the paper still hold hope something important will come out of it.
Deolalikar at this point should retract his P ≠ NP claim until he can address all these issues. In an email Deolalikar sent out to the gang of 22 on Friday the 13th, he restates his claim and overview of the proof and says he "fixed the issues in the finite model theory portion of the proof". He promises a revised version on his homepage in a couple of days.
Deolalikar is following the script, currently at stage 5 of the 12 stage process. Stage 6 will happen sooner than he expects.
Well, for me the discussion was very interesting and enjoyable - so I am glad Lipton,Regan, Tao et. al. were willing to take some time and look at the "proof."
ReplyDeleteThis is a pretty disappointing post of Lance. Sure, Vinay's paper was sloppy and the attempt is not serious. But that said, the discussion on Lipton's blog, Gowers posts, and Terry Tao comments and analysis are highly interesting. As well as other remarks by H. Friedman, Neil Immerman, Ryan Williams, Anuj Dawar and more.
ReplyDeleteAlso, to say bad things about the paper, _in retrospect_ after one week, when fatal flaws were already discovered, is a bit suspicious.
I think that the behavior of people like Tao and Gowers who dedicated their efforts to analyze possible flaws, despite the fact that the paper is written badly (and letting aside matters of gossip and sociology), just demonstrates their serious, honest, and dedicated professional attitude to pure science and knowledge. They set a role model for the TCS community.
I have both positive and negative opinions on the social aspects. Obviously some people have come down hard on either side. The dichotomy is often between "results based" and "ideas based" boffins. Those who have seen too many pies in the sky are less likely to be involved in trying to figure out what is salvagable.
ReplyDeleteAs a number theorist, I can remember no less than 3 "quality" attacks on the Riemann hypothesis about a decade ago. One was Connes (Fields Medalist), and his trace formula with a dynamical system on the primes. Another less-known was Lapidus, with his fractal strings. A third was Deninger with his cohomological formalism. All of them are still going to some degree, though none of them is much discussed outside cherished circles. Then there was Li's criterion, work of Balazard, Baez-Duarte, and more, but none ever touched the beyond the surface, and to an outsider would just be a pile of rejected ideas (at this point) which maybe contributed to understanding -- but maybe just attired the subject with extra inessential baggage. My guess is that this is the direction this will take, but I have no clue really.
An "advantage" P vs NP has is that it is younger than RH, and so there is less of a sense of "I have a new idea -- let's see how I can apply it to make an RH equivalent!"
Whatever, the merits/demerits of Deolaikar's the reaction of people can be categorized into two camps.
ReplyDeleteThe traditional -- so called complexity people -- such as Fortnow and Aaronson has been competing with each other in the nastiness quotient. Mathematicians such as Tao, Gowers, Gurvits, and others -- while not at all convinced of the correctness, has treated the attempt with courtsey, respect and professionalism and have expressed the hope that some good would come out of this attempt even if it fails to generate even a single new result. The irony is that the latter group has a incomparably stronger research record in mathematics than the former -- and if all that the "proof" does, or has already succeeded in doing, is to simulate this latter group to work on the P/NP problem seriously, then it is already a big benefit for mathematics as a whole. In any case, the chances that the P/NP problem if solved will be solved by people outside the STOC/FOCS community (to which Fortnow and Aaronson belongs) seems to be a pretty good bet to me -- though for the sake of minimum scientific decency, I will of course not bet any money on it.
I think that the behavior of people like Tao and Gowers who dedicated their efforts to analyze possible flaws, despite the fact that the paper is written badly (and letting aside matters of gossip and sociology), just demonstrates their serious, honest, and dedicated professional attitude to pure science and knowledge. They set a role model for the TCS community.
ReplyDeleteI agree with this. What most struck me about the way Tao and Gowers write was their tone of humble optimism. Complexity theorists have often come across to me as elitist and jaded.
I think the success of Lipton's blog can be largely attributed to his constant posing of open problems, and willingness to consider half-baked ideas. This place, by contrast, has turned into the Complexity Tavern, where people who know it all stop by anonymously to knock back a few and complain about the job someone else just got.
Barriers II is right around the corner, and my guess is that, because of everything that just happened, people will be much more excited and upbeat than they were at Barriers I. If not, well, then we don't deserve to be funded. Why should anyone else believe that we are doing something cool if we don't believe it ourselves?
Anonymous #1: "Well, for me the discussion was very interesting and enjoyable - so I am glad Lipton, Regan, Tao et. al. were willing to take some time and look at the "proof."
ReplyDeleteAnonymous #2: "What most struck me about the way Tao and Gowers write was their tone of humble optimism."
Anonymous #3: "Mathematicians such as Tao, Gowers, Gurvits, and others ...have treated the attempt with courtesey, respect and professionalism and have expressed the hope that some good would come out of this attempt even if it fails to generate even a single new result."
Anonymous #4: "I think the success of Lipton's blog can be largely attributed to his constant posing of open problems, and willingness to consider half-baked ideas."
-------------
I dunno who "anonymous" is ... but definitely I agree with their opinions!
In North American at least, the overall STEM enterprise has endured a two-generation decline, and perhaps the associated stresses help explain why individual reactions to this episode has been so markedly variable?
The best posts on this topic (and there have been many of them) amount to a sustaining narrative that—in the mathematical realm at least—helps to create what ecologists call 'critical habitat' for younger members of the gobal STEM enterprise.
This habitat IMHO is exceedingly valuable, just as "anonymous" asserts! :)
The tone of this post (as well as that of related posts
ReplyDeletein Scot Aaronson's blog) indicates that in the future
people who think that they have a serious proof or even a proof idea about difficult complexity questions -- should choose with much more care whom they initially send their manuscripts to. Many TCS researchers (perhaps because of their proximity to engineering-type disciplines) seems overtly aggressive and dismissive -- a trait that seems quite out of place when dealing with difficult mathematical questions, where mistakes are treated with understanding (and indeed often considered valuable). (Just count the number of number theory texts that refer to Kummer's mistaken proof of unique factorization in number fields and subsequent development of ideal theory in algebraic number theory). This humble approach to mathematics seems to have been almost completely obliterated in theoretical CS. Perhaps, it is time for researchers interested in the purely mathematical areas of TCS to form their own community in a true sense, with a mathematical culture in dealing with proofs, publications etc., and let the others pursue their perfectly legitimate but not as mathematical interests separately. Just some food for thought.
Mathematicians such as Tao, Gowers, Gurvits, and others -- while not at all convinced of the correctness, has treated the attempt with courtsey, respect and professionalism and have expressed the hope that some good would come out of this attempt even if it fails to generate even a single new result.
ReplyDeleteI'm guessing this has a lot to do with how many crackpot proofs of P!=NP the TCS people have seen before. I can imagine that getting them all the time slowly wears down one's patience.
It is, I guess, also true that most pure mathematicians, even great ones, are fairly humble folk. There are a exceptions of course.
All of us apply filters to decide what to spend time on, and every filter has a threshold that tells us what we can ignore reasonably safely. Fortnow's and Aaronson's thresholds happened to be a bit higher for this particular subject than Lipton's or Tao's or Gowers's. I don't see that as a problem at all (especially considering that it now looks like Fortnow's and Aaronson's filters avoided a time-consuming false positive).
ReplyDeleteAnd honestly, the tone of Terry Tao's most recent comments is much closer to those of Fortnow's and Aaronson's. He doesn't seem to think there's anything salvageable there anymore.
And let me add to my 1:57 comment above: I personally had roughly the same reaction as Lance and Scott, not because I'm a theorist, but because I have a [bad] habit of picking and choosing different techniques from different areas and applying them together with a fairly shallow understanding of each one. It seemed pretty clear to me that that's more or less what this paper was doing, and my own experience with how well that usually works told me how likely this paper was to be true.
ReplyDeleteFortnow's and Aaronson's thresholds happened to be a bit higher for this particular subject than Lipton's or Tao's or Gowers's.
ReplyDeleteWhile Tao reached his conclusion after a lengthy (and public) rumination about the document, Fortnow and Aaronson apparently dismissed it outright (without even a hint where they suspected the problems lie). This generates a justified suspicion that their publicly expressed extremely quick reaction was not based on purely scientific grounds. It is very likely that future P/NP proofs will rely on mathematics which only "humble pure mathematicians" will have access to, and we will be spared this kind of unprofessional behavior.
Anonymous said: It is very likely that future P/NP proofs will rely on mathematics which only "humble pure mathematicians" will have access to ...
ReplyDeleteOuch ... that's unfortunate if true ... historically, such a criterion would have excluded some mighty famous proofs and (just as important) proof technologies.
Florin Diacu's article The solution of the n-body problem (1996) gives some interesting examples.
@Anon #11: While Scott unfortunately did not state his reasons in his first post on the subject (though he did elaborate on them in his subsequent posts), Lance did give a hint as to where the trouble may lie (see his tweet on the subject which refers to a particular point in Lipton's first post on the subject, specifically the sentence "He then argues if P=NP, then by the above theorem it must follow that SAT has certain structural properties."
ReplyDeleteRight. It's fortnow's fault that the Dealolikar proof is wrong and he was able to see it immediately. It's Fortnows fault that Dealolikar has a sketch instead of a well written claim. It's Fortnows fault that Dealolikar made it public before checking with experts.
ReplyDeleteI thinks it is Fortnow's right to focus on whatever he chooses and in fact discourage proof attempts of this sort.
Last anon, we are not talking about "faults". We are discussing the different mentality of two groups of people, as manifested by two different reactions to the paper.
ReplyDeleteI thinks it is Fortnow's right to focus on whatever he chooses and in fact discourage proof attempts of this sort.
ReplyDeleteIt is of course Fortnow's right to express himself in any way he pleases. However, to say that he is right to "discourage proof attempts of this sort" is of couse quite absurd, especially its not so clear to me that Fortnow himself has contributed (mathemtically speaking) anything useful towards resolution of this problem.
The objection raised by many is mostly to the "tone of insult" that that was apparent in Fortnow and Aaronson;'s early reactions -- more-or-less, implying that the proof lacked pedigree (idea-wise as well as author-wise) and hence wrong. In contrast, the reactions of Tao et al. while no less critical, was scholarly and the tone was civil. The contrast couldn't be clearer.
Last anon. There are not two different groups. There is only one group that has the deep understanding to check the proof in a few hours. A few people from this group spent those hours and perhaps they already regret it.
ReplyDeleteThe rest of the people (incl me) love watching the drama and throwing away their time commenting in blogs but they are not in a position to understand.
There is nothing wrong to let other people check a proof if you think it lacks the "pedigree".
ReplyDeleteAlso by proof attempt of this sort I mean a 100 page for one of the most important problems where the mistakes are apparent after a couple of days.
There is only one group that has the deep understanding to check the proof in a few hours.
ReplyDeleteActually, notwithstanding all the hoopla created by TCS people about the so called "barriers", our knowledge about the P vs NP problem is not particularly deep --
I am guessing many competent graduate students probably know as much as there is to know about the current state of knowledge about it. This also means that any future solution will not owe much (past perhaps the problem statement) to any prior work.
To Anon#8:
ReplyDeleteYou said "I'm guessing this has a lot to do with how many crackpot proofs of P!=NP the TCS people have seen before. I can imagine that getting them all the time slowly wears down one's patience."
I am actually curious to know how many "proofs" of P!=NP from serious researchers have been there. Have there really been a lot?! Could it be that everyone thinks that it is a hard problem, but not that many have really worked on it recently?
Last anon. There are not two different groups. There is only one group that has the deep understanding to check the proof in a few hours.
ReplyDeleteNo. There is the group of bloggers and commenters within TCS, that have dedicated their time to dismiss the proof, without having to think in any meaningful way about the mathematics involved, but just looking superficially for certain "indications framing" the paper.
And on the other side, there is a completely different group of people, from pure mathematics, but also from TCS, including possibly grad students, and postdocs, who thought seriously on the mathematical details, attempting to characterize the proof strategy in a precise way, trying to learn from and react to educated comments from Tao and others. Writing and reading the wiki dedicated to the analysis. Understanding what are the problems in the FO(LFP) characterization; and then concentrating on the the property of "polylog parametrizability" of distributions and their projections, etc.
Now, I agree that the paper is not written in a serious manner, and was probably doomed from the start. But, the reaction of the second group, is the reaction that one expects from scientists and intellectuals. Because they aim first and foremost at understanding. And not achieving. And even if the paper is bad, they feel joy, and even obligation, to "crack" the puzzle. This is typical to many mathematicians, and scientists. And this should be a model for TCS.
Because they aim first and foremost at understanding. And not achieving.
ReplyDeleteVery well said. There is unhealthy competition in TCS
to obtain "results". From this point of view making it to STOC/FOCS becomes almost the goal of research. One notices periodic gandiose announcements of "results of the latest STOC/FOCS acceptances" as if they signify great progess. Yes, I am aware of all the "filtering", "time-efficiency" arguments. Somehow, the pure mathematicians who grapple with problems several orders of magnitude deeper, seem to have no shortage of time
(viz. Tao and Gower's commentaries on this problem and others) and they seem to need no filtering.
@Anon 21
ReplyDeleteThat's a very naive perspective. The reality is that there's only so many hours in the day, and prioritization is a very real and important part of a scientists job. If intellectuals spent all of their time knocking down obviously flawed attempts, there'd be no time left for them to actually make contributions. This is one of the reasons that theoreticians are likely to ignore proofs attempts at famous problems if they don't "look" right. There are important ways of structuring a proof such as Deolalikar's that makes it easier to get to the heart of the argument and analyze what's going on. If someone isn't willing to put forth the effort to put their work in this form, it's quite acceptable to dismiss it until they do.
The reality is that there's only so many hours in the day, and prioritization is a very real and important part of a scientists job.
ReplyDeleteThis is inconsistent with the facts. Some of those who publicly dismissed the paper, can waste hours and days in blogging about banal and trivial things. It's not that they dedicate their thoughts to a higher degree of knowledge. They just feel more comfortable with other sorts of activities than with dedicating their spare time to analyzing and discussing the proof attempt (though it is a failed one).
It seems that many TCS people have an ax to grind towards establishment. For them VD and his proof are their heroes.
ReplyDeleteHowever they fail to see that VD not only could not prove P/NP but could not check his own proof which proved to be easy (checking that is). This could be fun if it remains in the realm of blogosphere and graduate student problem-cracking fun. However, when the whole community plus media is involved it becomes an example to avoid.
That's a very naive perspective.
ReplyDeleteThe empirical data do not support you. Over on the Lipton blog, there are hundreds of comments, by some of the top minds in the world, and also by newcomers who say things like: "Certainly the discussion has made me very interested in complexity theory (so much so that I’m introducing everyone I know to it)." The only times over 100 comments appear on this blog are when the subject is the job market, STOC/FOCS, Israel or China. And when was the last time anyone, newcomer or oldtimer, posted something so positive here?
The reason for the difference is this: Lipton (and Tao) consider exposition on the internet to be a fundamental part of their scientific output -- they are both publishing books that are collections of their blog posts. The co-director of this blog stepped back from blogging in order to write his own book on the P/NP problem. It's a fundamentally different approach to this medium, and seeing a flawed proof as a waste of time instead of a teaching tool is a different approach as well.
I'm not trying to say Lance Fortnow is "wrong," to be clear. He was on vacation and the proof was broken. But calling Lipton, Regan, Gowers, Tao, or anyone who contributed to the wiki "naive" is really missing the point.
To all those who somehow think that researchers who have better things to do should be wasting their time on yet another faulty proof that P is not equal to NP, could you please suggest which of the 59 proofs (OK, that includes proofs that P is equal to NP) that are listed here are worthy of the same consideration?
ReplyDeleteWhile general discussions of questions such as "Does descriptive complexity offer any tools which might lead to separations of complexity classes?" or "Can we use distributional properties of the space of witnesses to reason about the hardness of the corresponding decision problem?" might be interesting and useful TCS blog fare, I think that this would all be more helpful without the attendant hype. In my opinion, some people who should have known better (and I don't mean members of the "pure math pantheon" who got dragged into this mess) decided to go with the hype and started a public discussion of the "proof" when it would have served the community better if they had taken some time to look seriously at the paper before discussing it in public. By then it was too late.
But it's looking more and more like Lance's and Scott's reactions were justified -- the proof seems to be unsalvageable, and Deolalikar doesn't seem interested in figuring out which, if any, parts of it are worthwhile. I wonder if the people going at their throats are committing an ironically similar error as most P != NP provers -- just because you can't see how they correctly dismissed the proof so quickly, doesn't mean they were wrong to do so.
ReplyDeleteBut it's looking more and more like Lance's and Scott's reactions were justified
ReplyDeleteIn retrospect, that is! The real work of finding out actual flaws was done painstakingly by Tao and others. Tao asked three questions when he started finding the flaws. First was whether any minor change can fix the proof. Second was whether major changes can fix the proof. The third was, whether the strategy is useful in having a later proof (don't forget that the strategy in the proof was what interested Lipton in the first place). And Tao answered all the questions with proper reasoning and understanding. For Scott and Lance, it was like "The proof will not work", which is fine considering they were on vacation and appreciate their intuition and risky behavior (Scott). But the point is they did not have any idea (or inclination or time) to ask and answer questions Tao asked. But now, we have "We told you so..." which is of no consequence. That does not mean that Lance and Scott should (or can) do what Tao does, but that's what makes Tao different than Scott and Lance.
I find the series of comments here completely surprising. We're talking about two men that are out, traveling, on vacation. Both of whom said as much in the days/weeks prior to the proof being disseminated. Then there's this massive generalization to the entire TCS vs pure math communities based on the behaviors of just two individuals on vacation.
ReplyDeleteI'm really left scratching my head here.
Computational complexity guys may be tired of getting erroneous P!= NP papers. I can sympathize, but don't paint Terry Tao as a babe in the woods. His web page says "...I receive a large number of submissions regarding either famous open problems (e.g. Riemann hypothesis, Goldbach conjecture, Navier-Stokes regularity, twin prime conjecture, etc.), or famous theorems (Fermat's last theorem, Four-color theorem, Cantor's theorem, Goedel's theorem, etc.)."
ReplyDeleteThe suggestion by FrenzyList of any parallel between the current episode and the work of Alain Connes is beyond bizarre...
I couldn't agree more with posts 4 and 5. The divide between the respectful and academically serious responses of Tao and Gowers and what can only be described as mean and petty comments of some of the supposedly leading TCS professors has been highly conspicuous. One might be tempted to think that the former are interested in the truth and the progress of human knowledge where the latter are interested in only themselves.
ReplyDeleteThis discussion partly concerns an aesthetic question: In academic criticism, what is the appropriate proportion of "snarkiness"?
ReplyDeleteToo little "snarkiness", and academia becomes bland ... too much "snarkiness", and academia becomes unpalatable.
Undoubtedly tastes differ, and undoubtedly strict uniformity is both unachievable and undesirable ... and this diversity is OK.
Moreover, most folks agree that snarkiness toward students is just plain wrong.
But once a person's life as a researcher has begun, it's a fact of life that some amount snarkiness comes to everyone, and we all just have to deal with it.
As for the right amount of snarkiness to dish out ... that's what everyone has to decide for themselves.
And uhh ... what exactly is snarkiness? Well, in practice it's pretty easy to recognize, even if logically it's not easy to define ... perhaps other folks can suggest definitions.
"But once a person's life as a researcher has begun, it's a fact of life that some amount snarkiness comes to everyone, and we all just have to deal with it."
ReplyDeleteThis is the classic journalists' defence. "It's not my fault that I destroyed your life to increase circulation of my newspaper, that's the sort of thing that happens in the modern world."
The fact that something happens commonly is not a comment on whether it should happen or not or whether people who do it are acting decently.
ReplyDeleteDeolalikar is following the script, currently at stage 5 of the 12 stage process. Stage 6 will happen sooner than he expects.
I do not really know what "snarkiness" is supposed to mean, but sentences like the one above in the original post have no place in an academic discourse This is also precisely the type of remark that was entirely missing in posts by Tao and Gowers, but seem to be present in every post by Fortnow and Aaronson on this topic. Ultimately, it boils down to the prevailing culture in pure mathematics, as opposed to CS, as many have already pointed out.
It's clear to everyone (IMHO) that a relatively small amount of snarkiness can greatly affect the palatability of mathematical discourse.
ReplyDeleteFor me, the outer boundary of good taste is illuminated by Joseph L. Doob's AMS dismissive review of Claude Shannon's A mathematical theory of communication (1949): "[Shannon's] discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author's mathematical intentions are honorable."
With the help of hindsight, we can appreciate that Doob's assertion—although certainly memorable, arguably true, and possibly even well-intended—wasn't particularly helpful to the mathematics community.
I reflect on this example whenever I am tempted (as everyone is) to speak or write a snarky comment.
Then there's this massive generalization to the entire TCS vs pure math communities based on the behaviors of just two individuals on vacation.
ReplyDeleteNo, there were also gossip-like comments by few other "top" CS theorists on Lipton's blog. We're not talking about specific two persons here.
I find it hilarious that TCS people are being cast as the "arrogant" ones, while math folks are supposed to be humble and open. I wonder how many of the commenters have actually spent time in a math department - talking to the algebraic geometers, for example... People like Gowers and Tao are striking exceptions.
ReplyDeleteYes but can the algebraic geometricians use the web? ;)
ReplyDeletethere were also gossip-like comments by few other "top" CS theorists on Lipton's blog
ReplyDeleteTo be fair, Neil Immerman, Ken Regan and Lipton himself adhered to the level expected in an academic discussion. But I agree that there were undesirable comments by several others which crossed the boundaries of "mathematical culture".
Neither Lance nor Scott are top CS theoreticians. They are CS journalists, and that too of the type of spread sensationalism. If Scott gets a tenure at MIT that will be because MIT needs a journalist.
ReplyDeleteBy the level of sensationlism in these posts, one can say that they these two, especially Scott, could fit at a top news agency. May be that is what Scott should do to succeed better in his professional life.
I wonder how many of the commenters have actually spent time in a math department - talking to the algebraic geometers, for example...
ReplyDeleteI have.
Mathematicians (most of them in my experience) are in fact quite friendly and helpful provided you approach them with the right attitude. The problems that most TCS people go to mathematicians for help involve questions that have been in all likelihood studied in much more generality by someone ages ago (even if the particular statement one would like to have has not been stated and proved). So the main problem is understanding the theory and applying it to the specific situation. Mathematicians tend to get annoyed when such matters are then blown up and published with bombastic claims. Most mathematicians would perhaps consider the typical mathematical content of the top FOCS/STOC paper as an honest day's labor, but would not dream of making a paper out of it. This causes the friction which some TCS people interpret as "arrogance".
To be fair, Neil Immerman, Ken Regan and Lipton himself adhered to the level expected in an academic discussion.
ReplyDeleteOf course. I wasn't talking about them.
Somehow, the pure mathematicians who grapple with problems several orders of magnitude deeper, seem to have no shortage of time "
ReplyDeleteCare to elaborate? The questiones tackled in TCS and the work done are every bit as deep and hard as in any other area of pure math.
On the other hand, I don't understand the criticisms. A glance at the paper shows that it's not a seriously written paper, just some vage ideas stapled together with no proper definitions and proofs. Of course it is a wortwhile task to try to see if any of the ideas can be salvaged, but the fact still remains that the hype over this paper was unjustified. It was clear from the outset that it would not lead to a correct proof without major work.
In any case, the chances that the P/NP problem if solved will be solved by people outside the STOC/FOCS community (to which Fortnow and Aaronson belongs) seems to be a pretty good bet to me
This is again nonsense, you seem to think as if the people in other areas of math were smarter, which is far from the truth. Sure, Tao and Gowers have been awarded Field medals and are insanely smart, but there are also incredibly bright people active in TCS.
Completely agree with anonymous 21.
ReplyDeleteThe posts and discussions at Lipton's blog were a pinnacle of complexity theory being discussed on the web. People were actually debating ideas and learning and educating each other about finite model theory, the space of solutions of random k-SAT, "polylog parametrizability", how to write better proofs, the future of peer review and many more interesting tangents.
Meanwhile Aaronson was noticeably rude and dismissive, adding little of substance to the discussion but apparently having plenty of time to post several posts and dozens and dozens of comments defending his "bet."
At least Fortnow had the decency to stay quiet until it was all over.
ReplyDeleteMost mathematicians would perhaps consider the typical mathematical content of the top FOCS/STOC paper as an honest day's labor
This is an example of astonishing arrogance. You might be an algebraic geometrer (so what), but clearly have no idea what you're taling about. Claiming that a FOCS/STOC paper is an day's labour is totally absurd.
Unless "most mathematicians" simply means "top-rate mathematicians", you're not making any sense. An average mathematician most probably woudln't be able to get a paper at STOC after several months'
worth of research, even having the right background. I suggest you learn some TCS before writing
such bullshit, some of the most beautiful pure mathematics is there, and it is in no way easier.
If anything it's harder, in the sense that problems solved in more abstract areas of math have
comparively trivial proofs (e.g. theorems in algebraic geometry are usually much simpler to prove, once their meaning have been deciphered, than in number theory or combinatorics).
ReplyDeleteCare to elaborate? The questiones tackled in TCS and the work done are every bit as deep and hard as in any other area of pure math.
Elabortion. I am in complete agreement with your statement. However, unlike pure mathematicians who actually grapple with their problems at hand making tiny, painful but at least positive progress, most (not all) TCS experts seem to veer off into "profitable" areas such as economics, markets and what not, and seem to use the deep problems in the field that you refer to, merely for cheap sensationalism (for generating funding perhaps).
Thats the major difference in my opinion.
The problems that most TCS people go to mathematicians for help involve questions that have been in all likelihood studied in much more generality by someone ages ago
ReplyDeleteThis is ridiculous. Do you have an example? Even if this is true, it means nothing that a healthy exchange of ideas from different
areas is helpful to solve problems. If you are an algebraic geometer and somehow need to solve a problem in number theory, tell it to a
number theorists and solves it right away, does it mean whatever work you're doing is trivial? This
is the same. Surely if you came up with an algorithmic or tcs-flavoured problem in your research,
CS people would solve it much more easily, due to different backgrounds. So what?
theorems in algebraic geometry are usually much simpler to prove, once their meaning have been deciphered,
ReplyDeleteEver try to read Hironaka's proof of resolution of singularities or for that matter the EGA and SGA. Actually, the typical reading list for a graduate student in algebraic geometry has more mathematical depth and content (not to mention current research) than all STOC/FOCS proceedings taken together. Moreover, the anon comment was referring to the "mathematical content" of the papers. Most FOCS/STOC papers have zero math content -- a few (probably less than 5%) have a positive amount. But outside a few outstanding examples most of them will get a very short shift in a (general) math journal of any repute. Just try submitting such a paper if you do not believe me.
ReplyDeleteAn average mathematician most probably woudln't be able to get a paper at STOC after several months'
worth of research, even having the right background.
This is a completely pointless debate. Most authors of
STOC/FOCS papers do not consider themselves as mathematicians (most of them are not even in math departments). Similarly, for most mathematicians writing STOC/FOCS papers will seem a pointless exercise. Aside from questions of relevance and recognition, mathematicians write their papers when they think they have something substantial to say (not because a deadline is looming). Of the tiny fraction of FOCS/STOC that are relevant to mathematics, the quality is uneven. Some are publishable in good math journals, the others are not -- but this should not be a measure of quality of these conferences or papers presented there in the first place.
Actually, the typical reading list for a graduate student in algebraic geometry has more mathematical depth and content (not to mention current research) than all STOC/FOCS proceedings taken together.
ReplyDeleteI'm sure I could conjure more hyperbole than anyone else in the entire history of the human race could ever match and that will ever come in the future even if the universe lasts for an infinite amount of time if I tried too.
If anything it's harder, in the sense that problems solved in more abstract areas of math have
ReplyDeletecomparively trivial proofs (e.g. theorems in algebraic geometry are usually much simpler to prove, once their meaning have been deciphered, than in number theory or combinatorics).
I think the problem is that a typical TCS grad student (say) approaches problems of considerable mathematical difficulty without an adequate training in core mathematics (algebra, geometry, analysis, topolgy etc.). This puts him or her at a disadvantage compared to someone who has a sound undergraduate/graduate training in math. The subsequent struggle and often re-discovery of many mathematical concepts that happens is exemplary effort, but the mathematical advance made is not commensurable to the effort expended. At the same time it might look that mathematical research is comparatively easier -- but this is made possible because of the considerable background baggage that mathematicians carry with them all the time.
If Noga Alon and Terry Tao see it worthwhile to publish in FOCS and STOC, I don't see how the opinions of various anonymice (including myself) has any bearing on the matter.
ReplyDelete
ReplyDeleteIf Noga Alon and Terry Tao see it worthwhile to publish in FOCS and STOC,
They do, as do several other mathematicians. But I doubt that they think of their FOCS/STOC papers as central to their research. In fact, mathematics departments typically do not count FOCS/STOC papers as publications (for purposes of annual evaluations, tenure etc.) .
I agree that a few FOCS/STOC conference presentations adds a bit of jazz to a math cv (perhaps not so much as perhaps a PNAS or Nature publication but a little nevertheless) -- but they are certainly not treated equivalent to publication in a math journal.
@Aaron Sterling
ReplyDelete"The empirical data do not support you."
Or maybe you didn't actually understand what I was saying.
"But calling Lipton, Regan, Gowers, Tao, or anyone who contributed to the wiki "naive" is really missing the point."
Yup. You clearly didn't read my statement for the purpose of understanding. You read it with intent. To claim I called any of those people "naive" is REALLY missing the point, not to mention simply wrong. Re-read the post then re-read Anon #9.
Well, for me the discussion was very interesting and enjoyable - so I am glad Lipton,Regan, Tao et. al. were willing to take some time and look at the "proof."
ReplyDeleteEveryone reads with intent, and preconceptions, Anon. If we're miscommunicating, I apologize for my side of it. I just observed a beautiful scientific week, and played a (very) small role in it. I'm in a great mood, even though I think the recent posts and comments here are kinda clueless. I wouldn't want to argue with you, even if I knew your real name. Going forward, I hope my own work can be as high quality as what I just witnessed, and I wish you the very best.
ReplyDelete"While Tao reached his conclusion after a lengthy (and public) rumination about the document, Fortnow and Aaronson apparently dismissed it outright (without even a hint where they suspected the problems lie). This generates a justified suspicion that their publicly expressed extremely quick reaction was not based on purely scientific grounds. It is very likely that future P/NP proofs will rely on mathematics which only "humble pure mathematicians" will have access to, and we will be spared this kind of unprofessional behavior."
ReplyDeleteFortnow and Aaronson aren't even in Tao's league either.
Honestly, if Terrence Tao is humble, everyone should be
@blah
ReplyDeleteThey still are several leagues higher than most of us. And certainly high enough to be allowed to have their own way of deciding how serious a proof of the major conjecture in their area of expertise has to be taken.
My irritation of point 13 still stands, though. I wondered if if my reaction to it was inapropiate. But
come on, why making fun of an anonymos internet comment? And no, it wasn't my comment :-)
Oh, my previous comment was meant to
ReplyDeleteappear in "My last post on the alleged P NE NP paper". Got a bit cofused, i'm not used to those
frequent updates of most computerscience blogs since last week ;-)
Why do people think that Vinay is reading all the discussion and hence is aware of the errors found? It may also be that he has gotten trillion emails and decided to stop checking them while working on the manuscript.
ReplyDeleteI just think that people should be given time. Perhaps he was on vacations short time after sending the manuscript :)
Actually, the typical reading list for a graduate student in algebraic geometry has more mathematical depth and content (not to mention current research) than all STOC/FOCS proceedings taken together.
ReplyDeleteHow can people write such bullshit?
It may require more background to start doing research in algebraic geometry, but that's about it. An average paper in algebraic geometry is no harder than an average TCS paper. And what do you mean by "depth" here?
Most FOCS/STOC papers have zero math content
I'm at a loss to understand what this may mean, since TCS is just another branch of pure math, so of course every paper proving something in the area has positive math content.
ReplyDeleteTCS is just another branch of pure math
Neither (most) TCS researchers, nor pure mathematicians will agree with this statement. Just ask around. In any case, if it were true then most TCS researchers would have had jobs in math departments. Moreover, most TCS researchers do not follow standard mathematical practices for publication either -- their practices are more closely aligned to engineering disciplines.
Most STOC/FOCS papers have very little to do with mathematics -- they use mathematical formalism, but so do most engineering disciplines. There are a
small subset of papers in these proceedings that has mathematical content, but most don't in any real sense.
And yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth. A somewhat arbitrary and rough measure of depth is the number of years it takes a graduate student to study before he/she can hope to understand current research. By this measure algebraic geometry is indeed a much deeper topic (number theory, areas of mathematical logic are probably even deeper). The mathematical parts of TCS are not particularly deep by this measure.
ReplyDeleteNeither (most) TCS researchers, nor pure mathematicians will agree with this statement.
Sure, people might disagree with regard to what extend our efforts should be focused on "real-world"
questions (as opposed to just asking questions "for the fun of it", as in pure math), but no one can deny that the questions complexity tries to understand, such as P vs NP, are purely mathematical questions that are interesting in their own right. True, they have a much different flavour from, say, geometry (they're much more akin to combinatorics), but it's pure math nonetheless.
As for publication habits, what you say is true but each field has its own conventions. As an
example of the opposite one could notice that most engineering disciplines use non-alphabetical author order anyway, whereas TCS sticks to the usual convention within mathematics. (Of course this doesn't indicate anything beyond that).
Most STOC/FOCS papers have very little to do with mathematics -- they use mathematical formalism, but so do most engineering disciplines.
They're all about the mathematics of computation. Apart from the real-world applications these papers may or may not have, these are interesting purely mathematical questions by themselves. And most of
them are not inspired by real-world applications anyway, but as an effort to understand computation,
randomization, etc.
Tell me what difference there is between this and pure (not applied) math. Of course if you define "math" as a list of fields that does not include TCS you can claim that most of TCS is not about math by definition, but this is pretty narrow-minded: the methodology and motivation
(with emphasis in undestanding and mathematical rigour rather than applicability) are the same in TCS as in other areas of math. We study different concepts that other areas, but in a purely mathematical way. On what grounds can one claim that these are not
interesting mathematical problems worthy of study? The fact that "they are about computation" is only a definition of the field of study.
And yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth
I don't think that's what "depth" is understood to mean in phrases such as "deep insight" or "deep
theorem". But anyway, adopting your definition, most of combinatorics is not deep either. Does it mean it's easy or a applied math field?
Number theory was disregarded by many mathematicians for ages, and the same has happened with e.g. combinatorics. The reason being nothing else than the one you seem to advocate, namely that the questions studied have a different feel than questions in other "established" areas of math, or because little background is required to attack them and therefore are lacking in "depth".
Do you agree with them?
As a matter of fact, all other things equal, depth (in your sense) should be a disadvantage. The most beautiful, captivating questions are precisely those
that are easy to state and understand and yet requiere non-obvious insightful ideas to solve, not those that require lots of background just to state.
ReplyDeleteNeither (most) TCS researchers, nor pure mathematicians will agree with this statement.
Sure, people might disagree with regard to what extend our efforts should be focused on "real-world"
questions (as opposed to just asking questions "for the fun of it", as in pure math), but no one can deny that the questions complexity tries to understand, such as P vs NP, are purely mathematical questions that are interesting in their own right. True, they have a much different flavour from, say, geometry (they're much more akin to combinatorics), but it's pure math nonetheless.
As for publication habits, what you say is true but each field has its own conventions. As an
example of the opposite one could notice that most engineering disciplines use non-alphabetical author order anyway, whereas TCS sticks to the usual convention within mathematics. (Of course this doesn't indicate anything beyond that).
Most STOC/FOCS papers have very little to do with mathematics -- they use mathematical formalism, but so do most engineering disciplines.
They're all about the mathematics of computation. Apart from the real-world applications these papers may or may not have, these are interesting purely mathematical questions by themselves. And most of
them are not inspired by real-world applications anyway, but as an effort to understand computation,
randomization, etc.
Tell me what difference there is between this and pure (not applied) math. Of course if you define "math" as a list of fields that does not include TCS you can claim that most of TCS is not about math by definition, but this is pretty narrow-minded: the methodology and motivation
(with emphasis in undestanding and mathematical rigour rather than applicability) are the same in TCS as in other areas of math. We study different concepts that other areas, but in a purely mathematical way. On what grounds can one claim that these are not
interesting mathematical problems worthy of study? The fact that "they are about computation" is only a definition of the field of study.
And yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth
I don't think that's what "depth" is understood to mean in phrases such as "deep insight" or "deep
theorem". But anyway, adopting your definition, most of combinatorics is not deep either. Does it mean it's easy or a applied math field?
Number theory was disregarded by many mathematicians for ages, and the same has happened with e.g. combinatorics. The reason being nothing else than the one you seem to advocate, namely that the questions studied have a different feel than questions in other "established" areas of math, or because little background is required to attack them and therefore are lacking in "depth".
Do you agree with them?
As a matter of fact, all other things equal, depth (in your sense) should be a disadvantage. The most beautiful, captivating questions are precisely those
that are easy to state and understand and yet requiere non-obvious insightful ideas to solve, not those that require lots of background just to state.
Perhaps Tao and Gowers were more circumspect than others because neither Tao nor Gowers is an expert on the problem; at any rate neither has published anything about it.
ReplyDelete