I have not commented much on the alleged P ≠ NP since I was waiting for better informed or more opinionated people to comment first. Now that the dust has somewhat settled here are some views of points of view and some pointers to points of interest.
- The best places to read about the technical details of the problems with the proof are Lipton's Blog Entries: here, here, here, here, here, here and the Wikipedia entry here.
-
Some people are saying that
Scott's post
was nasty. Here is an excerpt from Scott's post:
What's obvious from even a superficial reading is that Deolalikar's manuscript is well-written, and that it discusses the history, background, and difficulties of the P vs. NP question in a competent way. More importantly (and in contrast to 98% of claimed P ≠ NP proofs), even if this attempt fails, it seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterization of NP. I'll leave it to the commenters to debate whether Deolalikar's paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong.
Scott, that is downright nasty! Calling a paper well-written!! Accusing it of having thought-provoking new ideas!! Scott, you are just one Nasty dude!!
More seriously, Scotts offer of $200,000 if the proof is correct (more formally, if he wins the Mil prize) was considered nasty by some. Being skeptical and quantifing your skepticism is not nasty. -
Other posts worth looking at:
- Written pre-Deo, Lance now looks like Nostradamus: So you think you've settled P vs NP. (NOTE- personal triumph- I got the spelling of Nostradamus right on my first try!)
- A pre-Deo post of Scott's on 10 signs a claimed mathematical breakthrough is wrong. Deolalikar passed most of these.
- A post-Deo post of Scott's that was likely inspired by Deo: 8 signs your proof of P ≠ NP is wrong. One of Scott's signs cuts both ways- he says that the use of Descriptive Complexity Theory is one of the signs. He claims (correctly) ... subtle differences in encoding can lead to HUGE differences in computational complexity. Indeed, this was one of the problems with the Deo-Proof. However, I think Descriptive complexity theory is one of the few techniques that has not been proven cannot work. So I take its use as a good sign.
- Lance was on vacation when all of this happened so he posted on it when he got back. He was skeptical from the beginning and he says why. (See here.) People respond by saying that the paper inspired a lot of interesting discussion, and hence... I'm not sure- Lance shouldn't be skeptical? Lance shouldn't say he is skeptical? Lance should phrase his skepticism more politely? I'm not sure what the objection to his post really is.
- Is the proof correct? It looks like there are enough serious flaws that the answer for now is no. By now this is old news.
- I was originally skeptical (see here) since there has been no progress on P vs NP at all so its surprising that there is this much progress so fast. I do not know if this is valid reasoning. Has any serious hard math problem been solved all of a sudden after no progress on it? Has there truly been no progress? We might not know until we solve it in 3000 AD and look back and see which results from 1970-2010 ended up being relevant.
- Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II) either (1) retract the claim, or (2) post a version that fixes ALL of the flaws found and explains the fixes. If he does neither of these two things then he will cease to be a serious researcher.
- It would be impossible to have a version that fixes ALL of the flaws by Thursday Aug 26, 2010. Hence he needs to retract by then. (Some would say sooner. Much sooner. Like... now.)
- Was all of this good for the community? It got some talking and the people who read the proof learned some complexity. If this gets more people interested in the problem, that's got to be a good thing. If some interesting ideas come out of this, even indirectly (e.g., Terry Tao is inspired to read up on finite model theory and comes up with a result of interest) then it will of course be a good thing. However, if more of these proofs come out and the community spends too much time on them, that will be bad.
-
Why did people take this paper so seriously?
- It was in LaTeX!
- It was long!
- It was by a respectable researcher. (More on that later.)
- It used familiar notation.
- It seemed to have some good ideas in. It may still. (More on that later.)
- It was on Slashdot and on Lipton's blog. But this begs the question: why was it on slashdot and why did Lipton take it seriously? Dick- I am not asking this rhetorically- if you read this please leave a comment about why you took it seriously. I am not asking this sarcastically or in any other nasty way. (I know YOU won't think so but other readers might.)
- Others took it seriously. Chicken and egg problem here.
- It had very few of the usual trademarks of papers written by cranks.
- It was a proof in the correct direction (a proof that P=NP would be taken less seriously, though the result, if true, would be more awesome!!!)
- In the age of the web, news travels fast (I know of 3 other serious people claiming to have shown P ≠ NP; however, that was pre-web so they were debunked before it got very far. I'm not quite sure which ones went public so I decline to mention their names.)
- How respectable a researcher is Deolalikar? I do not know any other work that he is done. He is not someone you've heard about as having done excellent work. The fact that some in the community took his work seriously is an excellent sign that our community is not elitist. They took it seriously based on its merits. (The fact that some did not take it seriously is irrelevant.) ADDED LATER: The above was badly written and hence misunderstood. My point is that Deolalikar is not well known to the complexity community and hence the fact that many in the community took his work seriously speaks well of the community (or at least of those people) as not being elitist. Some of us WILL look at ideas from outside of the community.)
- Are there interesting ideas in it? The answer from the latest comments by knowledgeable people on Lipton's blogs seems to be no. Oh well.
-
In the midst of all of this came the DUMBEST comment on a post of mine EVER!!
In a recent
post
I noted that a recent (2007) article on number theory still referred to factoring
as being easy. I meant to imply that this was bad- they should at least acknowledge
the issues involved even if they don't care. One of the comments was
Since when do mathematicians care about the notion of polynomial time?
Note that this is the same week when Gowers and Tao, two Fields Medal winners, are carefully looking over an alleged proof that P ≠ NP. Other mathematicians were looking at it also. The notion that mathematicians do not care about polynomial time is just so 1990's.
Just one remark (I may be should have done last time)
ReplyDeletePeople worked on a "wiki", but it is certainly not "wikipedia" as you write.
Wikipedia is probably the most famous site using a wiki, but a wiki by itself is just a tool.
Now Gasarch is paying his tax to be an apologist of the blog owner.
ReplyDeleteLance and Scott did not make TCS community proud by their recent actions.
Say the truth Gasarch, even if Lance take you out of this blog.
Shame on both of you. Both of you "journalists" should realize that you ceased to be a part of the research community long ago. You were respected as journalists, and unfortunately you suck at this job too.
ReplyDeleteI don't think Deolalikar really NEEDS to do anything, much less by some arbitrary deadline.
ReplyDeleteIf he becomes convinced that the proof is irreparable he will probably announce that. But there is no practical necessity to rush this announcement even if the chances of success are small.
At any rate, I am MUCH impressed by the attitude of Lipton, Regan, Tao, Ryan Williams and others who used their expertise to shed light on the situation and educate the non-specialists as to what was really going on.
I for one agree with everything Bill says here, except that that page is not a Wikipedia page.
ReplyDeleteWhy use this space to insult Vinay's other work? It is published in respectable places, and I had heard of him before this.
ReplyDeleteScott's bet wasn't nasty, but your comments about Vinay sure are.
After this incident and some other recent comment threads on this blog, my overall impression of the TCS community (from an outsider looking in) is that there's a LOT of simmering resentment towards TCS researchers perceived to be "elite".
ReplyDeleteI say this to counter those commenters that say Lance's and Scott's attitudes make the TCS community look bad. Lance and Scott took a perfectly reasonable position. In my view, it's the commenters that are so manifestly resentful of them that they want to tell them what they can and can't do that make the TCS community look bad.
LOL ... plainly, Charles Dickens was writing about the math community's reaction to Vinay's proof:
ReplyDelete"It was the best of times, it was the worst of times; it was the age of wisdom, it was the age of foolishness; it was the epoch of belief, it was the epoch of incredulity; it was the season of Light, it was the season of Darkness; it was the spring of hope, it was the winter of despair; we had everything before us, we had nothing before us; we were all going directly to Heaven, we were all going the other way." --- Charles Dickens, A Tale of Two Cities
Seriously, I'm going to cast my lost with "the best of times" ... on the grounds that the vigor of the STEM community, and the value of its aspirational narratives, and the capabilities of its proof technologies, are each of them at least as valuable as the truth-versus-falsity of Vinay's claimed theorem.
That is why (IMHO) the STEM community has been well-served by this wonderfully instructive and highly entertaining episode.
People are good at making judgments on what is right and what is wrong. It would have deserved an applaud if people had written blogs on joining hands with vinay in helping him fill the gaps, than to put deadlines for the flaw-free-version of the paper.
ReplyDeleteI am not sure if this is really an "elitism" issue.
ReplyDeleteLipton, Regan, Ryan Williams etc. are pretty elite within TCS (pretty well known, multiple times at STOC,FOCS, CCC etc. each). And Gowers and Tao are obviously "elite" mathematicians.
And most of the elite complexity theorists did not make any public comments on this paper, e.g. Arora, Barak, Dinur, Khot etc.
So I don't see how it is accurate to say "people are criticizing Aaronson et. al. only because they hate elites"
Here's a question: Why was this such a big deal, while the (flawed) proof that GI is in P by Friedland attracted relatively little attention from the wider community? Obviously P != NP is a much bigger deal than GI in P, but a proof of the latter would still be a major result, almost on the level of L = SL.
ReplyDeleteOf course Friedland retracted his paper relatively quickly once the error was discovered, but there was still a decent period between his initial post to the arXiv and the final proof.
Q: If Deolalikar had retracted his proof as soon as some of the more glaring errors came to light, would this whole story have attracted nearly as much attention? What if he had written his paper as cogently as Friedland? Or was the firestorm just due to the fact that a very well-regarded theorist (Lipton) publicly wrote about the proof in a positive light?
I thought that http://scottaaronson.com/blog/?p=458 was the post considered "nasty" by some.
ReplyDeletehttp://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/#comment-5647
ReplyDeleteTerence Tao's comments reproduced below (link above) summarizes the "proof" quite well.
Terence Tao
August 15, 2010 9:29 pm
To give a (somewhat artificial) analogy: as I see it now, the paper is like a lengthy blueprint for a revolutionary new car, that somehow combines a high-tech engine with an advanced fuel injection system to get 200 miles to the gallon.
The FO(LFP) objections are like a discovery of serious wiring faults in the engine, but the inventor then claims that one can easily fix this by replacing the engine with another, slightly less sophisticated engine.
The XORSAT and solution space objections are like a discovery that, according to the blueprints, the car would run just as well if the gasoline fuel was replaced with ordinary tap water. As far as I can tell, the response to this seems to be equivalent to “That objection is invalid – everyone knows that cars can’t run on water.”
The pp/ppp objection is like a discovery that the fuel is in fact being sent to a completely different component of the car than the engine.
Lance shouldn't be skeptical? Lance shouldn't say he is skeptical? Lance should phrase his skepticism more politely? I'm not sure what the objection to his post really is.
ReplyDeleteI think most of this could have been avoided if he had started with something like: "I'm going to talk about the D paper in a bit, but first I'd like to say how thrilled I am that complexity theory was mentioned in Forbes, the NYT and Slashdot. Thanks to RJL et al. for a remarkable week." Instead, it came across to me as though he (along with some commenters) had no comprehension of the public relations goldmine the field just stumbled across. And the reason for the goldmine was the high quality of technical conversation, and the great attitude almost everyone displayed. The show wasn't staged; it was a spontaneous demonstration of the community at its best.
Instead of recognizing this, Lance Fortnow states that in retrospect he should have been more negative. Why, pray tell? So the events on Lipton's blog would have been less likely to occur? Can't you see that people who thought those events were a "thing of beauty" or the "Woodstock of TCS" might take offense?
Who cares if the D paper was flawed? Not me. (I posted as much days ago.) A new tool to do science was just "created," because specialists from around the world spent days figuring out how to talk each other's language. That's a big deal. Why spend any time criticizing the D paper, when we all know it's crushed? He could have talked about what was important. He didn't, and, instead, crushed the D paper (and D personally) a bit more, so he's getting pushback.
I don't think we should go into accusations here. As noted in the previous post's comments, there were two groups of people. The first headed by Tao, Gowers and others, dealing with pure mathematical issues.
ReplyDeleteAnd then there was a different group of known people from TCS, some of them commenting on Lipton's blog, that contributed only to the non-scientific part of the story.
This possibly manifests two different mentalities, that of pure mathematics and that of STOC/FOCS-TCS.
But we should not go into personal accusations here. We should just learn from this experience.
I don't know why there is all this discussion about serious Mathematical results. Any serious person knows that there has been no serious work done for over 10 years. Sure there have been plenty of papers written, but like any serious mathematician, I've been able to dismiss them out of hand, as the work of hacks. After all they are not written in Latin, the language that ALL serious academic work is published in. Though I do think it humorously ironic that all the hacks out there have started to discriminate amongst themselves as whether or not they should be taken seriously depending on whether or not they use this thing called TeX, which I of course have never used, and my work is I believe taken quite seriously.
ReplyDelete-Sir Issac Newton.
"How respectable a researcher is Deolalikar? I do not know any other work that he is done. He is not someone you've heard about as having done excellent work."
ReplyDeleteDeolalikar has published in the Journal of Number Theory amongst other things. To be honest I hadn't known about him before this. But I did not know of Gasarch either before he started posting on this blog. Is he a serious researcher ? What exactly has he done ?
One development that comes out this episode is that it is clear that serious complexity related discussion will now move over to the Lipton blog. I for one is not going to return to this site any more for a while.
Whatever the reasons, this proof attempt was pushed out onto the world stage. People with no experience in CS Theory were drawn in to see what was going on, and actually got to watch high level theory work occur. We got to observe the sorts of techniques used in this field to falsify a proof, and the debate around the applications of them.
ReplyDeleteWhen a proof is finally discovered, this may be a minor footnote or an important chapter depending on the ultimate techniques. The event could also be remembered as one of those turning points between traditional research, and research in a networked world.
Even if just by historians, the efforts made to deconstruct the proof in a generally understandable manner will be remembered. I think this is where a lot of the frustration with some participants' behavior comes from. I'm sure you've seen lots of P!=NP attempts over the years, but this is the first time the world wants to hear what you have to say about it. It's not that dismissing Deolalikar as an unremarkable and soon to be non-serious researcher is a wrong-headed opinion, it's just unfortunate that that was the best some people could use a historic event for.
What are you trying to prove? what is bothering you so much?
ReplyDeleteTerry Tao's recent comments are (in effect) a master's course on how to make the most of this episode as an opportunity for STEM teaching, community-building, and outreach.
ReplyDeleteIt Tao's comments (and those of other folks) are this good in the *middle* of the narrative, how good will they be by the *final* episode?
Astonishingly good, one can hope: comments that damp hopes that can prudently be damped, and raise hopes that can reasonably be raised. Tao's comments have balanced these two objectives admirably.
It's clear that one reason—perhaps the main reason—that the world is following this story, is to learn the answer to that question.
That's the common-sense reason why it's a good idea for everyone to put (what they conceive to be) their best foot forward.
As a number theorist my own opinion of the TCS field has somewhat diminished, though increased in other ways. I found out a lot about a number of complexity classes, but also (as I somewhat feared from my interaction with cryptography) that standards of "proof" can be dodgy. I am heartened to know that a number of TCS stalwarts still treat the subject in a proper manner, but the constant "social aspects" of a half-baked paper being the impetus for a new era of grad students enthused about your subject... well, I can't say this is a good thing.
ReplyDeleteAs a mathematician, I agree that once you publically announce a proof, you are morally obligated to withdraw it unless you can fix it within a time frame commensurate to its publicity (like within a few months for an average journal article from 2006 that was just noticed to have a flaw, though the journal in-press will add a few months more). With large publicity, any reasonable sense of a precautionary principle demands you should retract unless you can clear up misgivings (at least to yourself) within a week or two. The famous sci.math message of Wiles was after the main cycle of euphoria, but also was within a respectable amount of time from the time he realized there were problems (from Katz and the review process). Note also his careful phrasing about what he claims, and also that he posts firstmost to address the existent speculation.
http://groups.google.com/group/sci.math/browse_thread/thread/4cac31398651d398/31cf65a01c83339e
I still remember the line from Harold Boas, in the Notices of the AMS, about the work of Goldston and Yildirim (this was the wrong version before interaction with Green and Tao helped them fix their basic correlation condition): "As this issue goes to the printer, there appears to be a problem in the proof... Whatever the ultimate results, I hope the press describes their work as a success story. Their intriguing original idea has all the experts burning the midnight oil to figure out the implications. How many of us can say the same about our research?"
http://www.ams.org/notices/200306/commentary.pdf
Indeed, if all you want is popularity, faddish groupthink will arise - and quickly choke out anything else.
This being said, I don't have any problem with what Lipton and others did, though it gave more credence to the work than it perhaps merited. On the one hand it gave an insight into how there are many false starts in understanding a proof (look at how multiple different "fatal flaws" have been discovered then partially repaired), but OTOH perhaps gives an erring idea about the best way to understand maths --- a week-long crash course with world experts, often talking at a very high level of sophistication, is not always the best way to truly absorb ideas, especially as an individual.
Given the sizable number of blabberers who muse about "social aspects", and by now (post-event) even publically state that these are likely more important the truth/falsity of the proof (or even cross-field interaction, now that statphys distros has been rejected even as a possible), one has to wonder where the future of "science" part of TCS is going, but as I say, I did see some positive signs also.
In short, I liked the science aspects of the week (the hard math), but the social-esque content was the typical drivel and blubber I all too often associated with ivory tower academics (of which I am one, in part).
As a number theorist my own opinion of the TCS field has somewhat diminished, though increased in other ways. I found out a lot about a number of complexity classes, but also (as I somewhat feared from my interaction with cryptography) that standards of "proof" can be dodgy. I am heartened to know that a number of TCS stalwarts still treat the subject in a proper manner, but the constant "social aspects" of a half-baked paper being the impetus for a new era of grad students enthused about your subject... well, I can't say this is a good thing.
ReplyDeleteAs a mathematician, I agree that once you publically announce a proof, you are morally obligated to withdraw it unless you can fix it within a time frame commensurate to its publicity (like within a few months for an average journal article from 2006 that was just noticed to have a flaw, though the journal in-press will add a few months more). With large publicity, any reasonable sense of a precautionary principle demands you should retract unless you can clear up misgivings (at least to yourself) within a week or two. The famous sci.math message of Wiles was after the main cycle of euphoria, but also was within a respectable amount of time from the time he realized there were problems (from Katz and the review process). Note also his careful phrasing about what he claims, and also that he posts firstmost to address the existent speculation.
http://groups.google.com/group/sci.math/browse_thread/thread/4cac31398651d398/31cf65a01c83339e
I still remember the line from Harold Boas, in the Notices of the AMS, about the work of Goldston and Yildirim (this was the wrong version before interaction with Green and Tao helped them fix their basic correlation condition): "As this issue goes to the printer, there appears to be a problem in the proof... Whatever the ultimate results, I hope the press describes their work as a success story. Their intriguing original idea has all the experts burning the midnight oil to figure out the implications. How many of us can say the same about our research?"
http://www.ams.org/notices/200306/commentary.pdf
Indeed, if all you want is popularity, faddish groupthink will arise - and quickly choke out anything else.
This being said, I don't have any problem with what Lipton and others did, though it gave more credence to the work than it perhaps merited. On the one hand it gave an insight into how there are many false starts in understanding a proof (look at how multiple different "fatal flaws" have been discovered then partially repaired), but OTOH perhaps gives an erring idea about the best way to understand maths --- a week-long crash course with world experts, often talking at a very high level of sophistication, is not always the best way to truly absorb ideas, especially as an individual.
Given the sizable number of blabberers who muse about "social aspects", and by now (post-event) even publically state that these are likely more important the truth/falsity of the proof (or even cross-field interaction, now that statphys distros has been rejected even as a possible), one has to wonder where the future of "science" part of TCS is going, but as I say, I did see some positive signs also.
In short, I liked the science aspects of the week (the hard math), but the social-esque content was the typical drivel and blubber I all too often associated with ivory tower academics (of which I am one, in part).
Excellent post, Bill. And Lance's yesterday---am I right to detect a reference to Grandmaster Ken Rogoff's book (with Carmen Reinhart), "This Time is Different"?
ReplyDeleteThe book is about how 800 years of bubbles and busts have been less different than it seems when you look with perspective. And that's an important point to lay forward in regard to this paper. The problem with the harsh comments now is that we don't have the perspective, because some important contextual factors really are new, and (even viewing Terence Tao's great auto analogy quoted by Anon 11:26am above) we still don't know all about the paper. I think the truth is somewhere between Lance's point and a comment I saw saying this was the first robust attempt since Ted Swart's P=NP efforts in the 1980's (I know one other involving different classes). But we need Lance and Bill's points in order to see what we're learning from it.
For the record, Lance relayed a concrete technical point referencing the paper to David Mix Barrington which DMB posted on the first day, and which I led off with when drafting the "Issues" post. If I'd needed to, or if I'd even had the time, I could have gotten more from either. So much else was situational---I'm lucky my wife was finally able to drive again last week. One understanding I'd like to see come out of this is if you criticize---especially personally---make sure you've done your homework, and respectfully engage what the person has already said. Indeed that's why Dick and I laid the word engage out there, and we didn't want to obscure it by adding things there like Bill does here.
Bill ,didnt u also once claim to have solved pvsnp? and ur paper was retracted after 5 months ?
ReplyDeletedont be shy tell us about ur failed attempt.
To second Ken Regan's advice "Be sure you've done your homework", there's a pretty large segment of the STEM community who *do* read their homework.
ReplyDeleteAnd what they read includes extraordinarily strong TCS claims like the following:
----------
Trying to prove P≠NP quickly (has) became the single most important question in all of theoretical computer science and one of the most important in all of mathematics.
... Many of (the most) fundamental problems turn out to be NP-complete. A small sample: finding a DNA sequence that best fits a collection of fragments of the sequence; finding a ground state in the Ising model of phase transitions; finding Nash Equilbriums with specific properties in a number of environments; finding optimal protein threading procedures; determining if a mathematical statement has a short proof.
... And I'm just scratching the surface.
... The P versus NP problem has gone from an interesting problem related to logic to perhaps the most fundamental and important mathematical question of our time, whose importance only grows as computers become more powerful and widespread.
----------
Personally, I think claims like the above are great (they're taken verbatim from Lance's recent Comm. ACM review). And I think the 13 critical points in GASARCH's bog post are great too (every one of GASARCH's points is well-reasoned and cogently expressed).
What many folks would like to see is thoughtful posts that bridge the gap between Lance's aspirational narrative and GASARCH's technical critiques.
And one thing has become abundantly clear: *no* amount of snark can bridge this gap!
Fortunately, many folks have contributed thoughtful posts that are a very good start at bridging the Fortnow-GASARCH gap.
These people are serving as TCS community's lamed-vavniks—without whom TCS would lose its primary justification to exist—and so (IMHO) they have justly earned the appreciation and gratitude of the larger STEM community too.
It goes without saying that we need to be civil in our criticisms. I see that some of these posts lack this. Vinay has every right to take his time and ponder over his proof, and retract it later.
ReplyDelete(if it should happen the above post is duplicated, please feel free to remove either copy ... at my end all that showed up was a server error message)
ReplyDeleteMy statements about Deolalikar were badly written and hence misunderstood.
ReplyDeleteThe point I was trying to make was that he was not well known to the community, but his work was taken seriously by the community, and that speaks well of the community not being elitist. No offense to Deolalikar was intended.
lol to point 13.
ReplyDeleteWhat if sombody just made a
joke or it was a child writing
this. Maybe a stupid comment,
but making such a mockery out
of it, it's no wonder people
writing their comments anonymously.
More seriously, Scotts offer of $200,000 if the proof is correct (more formally, if he wins the Mil prize) was considered nasty by some. Being skeptical and quantifing your skepticism is not nasty.
ReplyDeleteThis "offer" felt 'nasty' (or at least rude) when I read it.
"Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II) either (1) retract the claim, or (2) post a version that fixes ALL of the flaws found and explains the fixes. If he does neither of these two things then he will cease to be a serious researcher."
ReplyDeleteArrogant.
GASARCH point-of-view #7: "Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II) either (1) retract the claim, or (2) post a version that fixes ALL of the flaws found and explains the fixes. If he does neither of these two things then he will cease to be a serious researcher."
ReplyDeleteArguably true ... and it has a fascinating corollary.
---------------------
Corollary to GASARCH #7: Some of STEM's greatest advances were achieved by unserious researchers.
---------------------
http://www.thebigquestions.com/2010/08/16/o-brave-new-world/#comment-10003
ReplyDeleteProof of: “P=NP iff P!=NP” – Syntactic.
ReplyDeleteThe proof is by diagonalization as follows:
NP={L_1,L_2,L_3,…}
L_1={w_11,w_12,w_13,…}
L_2={w_21,w_22,w_23,…}
L_3={w_31,w_32,w_33,…}
Each string w_ij can be written as the Turing machine describing it which can be written as two substrings, the first its input and the second is the computation configurations:
= w_iw_j
Hence we have,
L_1={w_1w_1,w_1w_2,w_1w_3,…}
L_2={w_2w_1,w_2w_2,w_2w_3,…}
L_3={w_3w_1,w_3w_2,w_3w_3,…}
Note that both the diagonal and its complement can easily encode the Kleene-Rosser paradox as:
KR={kk_1,kk_2,kk_3,…}={Not kk_1, Not kk_2, Not kk_3…}
Use the encoding e(kk_i)=w_iw_i and e(Not kk_i) = \bar w_i\bar w_i
You obtain: e(KR) in NP iff e(KR) NOT in NP, of course e(KR) irreducible to SAT iff it is reducible to SAT.
Hence, P=NP iff P!=NP.
This should not be surprising as the lambda calculus is equivalent to Turing machines. By direct encoding of the lambda calculus paradox, you obtain it on Turing machines.
This proof was syntactic, the same result can be reached via independently via semantics.
P.S. submitted to the Theory of Computing Journal 6.5 months ago.
The line of argumentation of Cook's proof of CNF SAT being NP-complete is as follows:
"Let A be a language in NP accepted by a non-deterministic Turing machine M. Fix an input x, we will create a 3CNF formula \phi that will be satisfiable if and only if there is a proper tableau for M and x"
1. Let w be the encoding of the Kleene-Rosser paradox, thus e^-1(w)=Not e^-1(w), where e is an encoding function.
2. M accepts w.
3. SAT is NP-complete, Cook's theorem.
4. There must exists \phi(w):\phi(w) is satisfiable.
5. Then \phi(w) is satisfiable iff M accepts w iff e^-1(w)=Not e^-1(w)
6. M accepts w is "True".
7. Then: \phi(w) is satisfiable iff e^-1(w)=Not e^-1(w) – Logical Contradiction.
8. Then There must be no \phi(w) which is satisfiable.
9. Then SAT is (NOT) NP-complete.
Best,
Rafee Kamouna
In the NYT article the TCS community is described as "insular". This is not accurate but I would say that it is "closely knit" or something along those lines.
ReplyDeleteGreat post Bill.
ReplyDeleteHas anyone who is chastising Bill Gasarch, Lance Fortnow, and Scott Aaronson, and telling them to act more like Terry Tao, Richard Lipton, and Ken Regan, actually read recent statements by Tao, Lipton, and Regan on the matter? Their opinion of Deolalikar seems largely the same, both of the likely value of his scientific contribution, and of his refusal to honestly acknowledge the problems in his proof.
The consensus among all experts, not just those who doubted Deolalikar from the beginning, is clear: the proof is wrong, so unfixably wrong that scientific honor demands that it be retracted. The observations that it was fascinating to behold the collaborative effort to check the proof, or that the media coverage may turn out to help TCS, are true but completely irrelevant to the claim that Deolalikar's proof is wrong, and that his refusal to retract the proof costs him credibility as a scientist. A person acting irresponsibly is not forgiven because his actions have some positive side effects.
To those to say that Bill, Lance, and Scott will discourage others from publishing their P NEQ NP proofs, you appear to have missed the point if you think they have not considered this. There is a right way and a wrong way to announce, check, discuss, and publish any major result, and Deolalikar did it and continues to do it the wrong way, and it appears that the point was explicitly to discourage anyone else from acting this way.
Without doubt, Deolalikar's manuscript can be justly criticized along the following lines: "It is often necessary to guess what he had in mind by interpreting the context. For many results he simply gave no proof at all, and when he endeavored to write down a proof, hardly a single argument does not raise doubts."
ReplyDeleteDoes this place Deolalikar at-risk of ceasing to be a serious researcher?
Historians of mathematics can supply ample grounds to take issue with that assertion.
Perhaps this is a case where (as often happens) the beginning of the narrative supplies insufficient information to reliably predict its end.
It feels good that the community has mostly positive attitude towards the manuscript of Vinay Deolalikar.
ReplyDeleteI would also like to ask you to feel what Vinay is going through. I am proud of him, irrespective of the correctness of his proof. I understand how difficult such moments are.
The community has mostly gained by his actions.
I would also like to ask you to feel what Vinay is going through. I am proud of him, irrespective of the correctness of his proof. I understand how difficult such moments are.
ReplyDeleteI also feel it and understand it. I understand it because I have previously written incorrect proofs. And when I or others found the errors, do you know what I did then? I admitted the error. It sucks and it hurts and it is embarrassing, but it is the honorable thing to do, so I did it. There is nothing wrong with publishing an incorrect proof, and we should be encouraging of those who try for big goals. But when they go for it, we are duty-bound to judge that work solely on its merits, and not on how good it makes the author feel to hear the judgement. If an author is not emotionally prepared to be told, "Here is an error in your proof. It is likely fatal. I'm sorry" then they should not submit.
@Kamal: I totally agree with you.
ReplyDeleteBeing humble is one of the signs of a "big" person. And I am sorry to say Lance, Scott, Gasarch--they haven't exhibited even a little sign of it. I used to admire them and wanted to become like them. And now I am feeling so bad that I am a part of this community. While probably I should not feel that way because the truth probably is that most of the people in our community are great persons--but I just detest to feel that there are people like G, L, S and they still get followers for whatever wrong way they behave.
Who cares if the D paper was flawed? Not me.
ReplyDelete...
I am proud of him, irrespective of the correctness of his proof.
This episode has really brought out the differences between two groups in TCS: those who think that the primary goal of research is to discover what is true and false about the world, and those who think we should ... what? Maintain harmony and avoid conflict and hurt feelings? Tell nice intuitively-plausible (but provably false) stories? I agree the world is a happier place if we all say only nice things about each other's work, but where does truth fit into this?
How did we ever get to the point where respected researchers are defending the idea that it doesn't matter whether the proofs in a theoretical paper are correct, or whether authors admit errors when they are discovered? If we cannot at least agree on that, then what are we being paid for?
Being humble is one of the signs of a "big" person.
ReplyDeleteDeolalikar has publicly claimed to solve the biggest problem in computer science. When presented with multiple fatal errors in his proof, rather than stand tall and publicly admit that his proof is broken (which would have earned him instant and deep respect from the entire community, although not any cash), he has dodged the criticism and stubbornly maintained that he is correct.
I find it difficult even to conceive of behavior that is less humble than that.
As for Gasarch, Fortnow, and Aaronson, I salute them for their courage to say unpopular true things that people need to hear. The "generosity" towards Deolalikar is in fact an insult towards me and anyone else who has ever swallowed their medicine and withdrawn a paper or abandoned a project because it was the honorable thing to do.
Here is what I have learned. When I am asked to review a terrible paper, for the sake of my own career I should consider praising it instead of rejecting it, so as to curry favor with the members of the program committee who value sunny feelings over correctness and truth. I believe that it is my duty to give my honest opinion of a paper in a review. Only after reading the comments here did I learn that by carrying out this duty, I risk sacrificing my reputation with half of the community, who will conclude only that I am "nasty" for making an author feel bad by pointing out errors in the paper and suggesting that these errors discredit the paper.
ReplyDeleteSet aside our lovely loser and his proof, we have another headline...
ReplyDeleteShe is the winner by nourishing on her academic descendant-to-be's dead body... (NYT 3000 in "History of Sciences" section)
Without doubt, Deolalikar's manuscript can be justly criticized along the following lines: "It is often necessary to guess what he had in mind by interpreting the context. For many results he simply gave no proof at all, and when he endeavored to write down a proof, hardly a single argument does not raise doubts."
ReplyDeleteDoes this place Deolalikar at-risk of ceasing to be a serious researcher?
An interesting question, although unrelated to Bill's comment about Deolalikar's status as a serious researcher. What Bill said is that if he wants to be taken seriously, Deolalikar must promptly retract his claim or answer the challenges raised since the paper went public. The judgement of him as a researcher is based not on the contents of his original proof, as you suggest, but on his subsequent behavior when his proof was challenged.
The best way to judge a person's integrity is not on how they handle success, but on how they handle failure. This is when a person's true character shows itself.
Hi Anon 39,
ReplyDeleteI thought my sentence would be clear from the context of the rest of the paragraph. I probably shouldn't have written such a loaded sentence, considering the amount of emotion shown in the comments here.
Of course I care whether the proof is true. What I was trying to communicate was that it was clear almost from the very beginning that the claimed proof wasn't going to fly. Okay, fine, TCSers have known that for days, and even the popular press has been reporting that for days. Yet another flawed attempt is not historically significant, but what happened on the Lipton blog is historically significant. So why talk about something (relatively speaking) insignificant, and ignore what is genuinely important?
I've done big ticket fundraising (in my pre-TCS life), and I believe both Lance and Bill -- people I respect a lot -- squandered a significant opportunity here. It's especially ironic, since Lance is literally the elected representative of the theory community.
For the record, I agree with Anon 37. However, I believe it is possible to tell the truth and be politically capable at the same time.
@anon 42: You will be right, that will be written in history...
ReplyDeleteBill, I think most knew that Vinay's chances of having actually proved this were very small. But, I was still interested in the paper in the hope that some new connections with other areas were revealed that could be used in this field. I think an outside view point is needed every now and then, because too often those within tcs keep ploughing over the same infertile ground.
ReplyDeleteExcellent post! One of the very best I've ever read on the internet! Up until today, I didn't know the definition of a "serious researcher" until I Gasarch's comments:
ReplyDelete"Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II) either (1) retract the claim, or (2) post a version that fixes ALL of the flaws found and explains the fixes. If he does neither of these two things then he will cease to be a serious researcher."
I think Gasarch should either (1) retract his definition of a serious researcher, or (2) publish some STOC and FOCS papers on computational complexity. If Gasarch does neither of these two things then he will cease to be a serious TCS blogger.
But, I was still interested in the paper in the hope that some new connections with other areas were revealed that could be used in this field.
ReplyDeleteWe were all hopeful of this. But unfortunately, "Deolalikar claims that finite model theory + random k-SAT ==> Clay prize" != "finite model theory + random k-SAT ==> anything at all".
If you didn't parse that, it seems to me that there was never a "revelation" that Deolalikar unearthed a new and deep connection between two fields, just his claim that they were connected, together with some proof sketches that turned out to be broken.
I can walk into a library and grab any two books I like and smash them together, but this does not imply the two books have anything to do with each other. There is no insight required to suggest that two fields might be connected. The only real insight comes from rolling up one's sleeves and doing the dirty work of making a formal proof really happen. Deolalikar did not make such a formal proof work; he only claimed to do so.
It is painful to watch so many top researchers demand respect for his attempt, based on nothing but his snake-oil claims that the attempt would work. I feel like I am watching a faith healer dupe a bunch of poor rural families into giving over their money, except that the poor rural families are some of the top TCS researchers in the world.
I think we should stop making assumptions about Vinay, and also about Lance, Scott, Bill or any other.
ReplyDeleteVinay is taking his time, and there does not seem to be any hurry. Nobody is building on top of his work, and his work was not even accepeted to be correct in the first place.
Publishing a paper and finding an error is a different thing, and making a claim which attracted the world's attention is altogether a different ball game. I think Vinay should take all his time to convince himself or demonstrate the value of his approach. Since the claim was not even accepted by the community to be correct (before finding the errors), there is no question of withdrawing the claim (as an analogy, you do not withdraw your rejected papers from a conference, but in case an incorrect paper is accepted then you need to withdraw it as soon as you find the errors).
I did not want to be a part of this thread. But I also did not like that people, while hiding their own names, are saying nasty things about Vinay, Lance, Scott, and Bill.
If you want to say nasty things, while accusing others of saying nasty things, please at least put your names to it.
For me the sequence of actions which took place is exactly how this thing should have happened. Vinay submitted his paper to the program committee consisting of the top researchers in the community. Some people liked it and some did not. It was discovered that the paper was not worth its claim. This is very much the same process as happens in any conference, such as stoc/focs. Some PC members like a paper and some do not. The discussion sometimes get heated. But forgotten after the decisions are made.
"I did not want to be a part of this thread. But I also did not like that people, while hiding their own names, are saying nasty things about Vinay, Lance, Scott, and Bill."
ReplyDeleteKamal, you must not like the Internet much.
@anon42: Her 203x paper was a landmark ground-breaking one!!
ReplyDeleteI respect TCS experts who have said nothing public about Deolalikar's paper. I respect other TCS experts who have expressed skepticism and left it at that. A new P-vs-NP proof claim doesn't in itself oblige anyone to action.
ReplyDeleteMy greatest respect, however, is reserved for the experts who have engaged in an open and constructive exchange of ideas. The immense power of such conversation is clear to me even when I can't understand the technical content. The participants benefit each other, benefit their discipline, and benefit society at large.
I would like to understand why such collaboration is not the norm and why a thing of such beauty should be so rare. One hypothesis is that cooperation between mathematicians is typically accidental and incidental, so much so that when it happened in spades last week, many mathematicians were able to say in all sincerity that it was a waste of time. The assumption seems to be that only finished mathematics should be communicated, while the messy, dynamic process of discovery ought to be silent and private. If I am right that mathematicians believe this, then I am positive they are crippling themselves.
My second hypothesis is that the value of open collaboration becomes clear to those who participate in it. If I remember correctly, Ryan Williams' first contribution to the discussion was to complain that Deolalikar was being taken way too seriously. Shortly after that, however, Williams got over it and became one of the most enthusiastic contributors. To me it appeared that he embraced the conversation as fun and valuable in its own right, Deolalikar be damned. Sometimes it takes being on the inside of a great conversation to know what great personal value that conversation can have for you.
My final hypothesis is that great conversations are a social phenomenon that require social catalysts to happen. The publication of an important, provocative claim is not sufficient to inspire open collaboration. We might have had only scattered sniping and skepticism across the blogosphere, with concrete understanding coalescing painfully slowly over weeks and months, instead of having a well-understood refutation in mere days. The additional catalyst was Dick Lipton's exuberant attitude toward the subject, and fair, respectful, generous attitude towards Deololalikar and everyone contributing to the discussion. Lipton helped facilitate an environment in which contributions would not be pre-judged at all, but rather accepted on merit regardless of the source.
To any experts who don't think that something special happened, and are assiduously insisting that they had a right not to participate in what happened, please don't let me intrude on your thoughtful isolation. You are welcome to do mathematics as you have always done it, and as you deem proper. You aren't hurting anyone. At worst you are missing an opportunity to help yourself but that is entirely your prerogative.
I respect TCS experts who have said nothing public about Deolalikar's paper. I respect other TCS experts who have expressed skepticism and left it at that. A new P-vs-NP proof claim doesn't in itself oblige anyone to action.
ReplyDeleteMy greatest respect, however, is reserved for the experts who have engaged in an open and constructive exchange of ideas. The immense power of such conversation is clear to me even when I can't understand the technical content. The participants benefit each other, benefit their discipline, and benefit society at large.
I would like to understand why such collaboration is not the norm and why a thing of such beauty should be so rare. One hypothesis is that cooperation between mathematicians is typically accidental and incidental, so much so that when it happened in spades last week, many mathematicians were able to say in all sincerity that it was a waste of time. The assumption seems to be that only finished mathematics should be communicated, while the messy, dynamic process of discovery ought to be silent and private. If I am right that mathematicians believe this, then I am positive they are crippling themselves.
My second hypothesis is that the value of open collaboration becomes clear to those who participate in it. If I remember correctly, Ryan Williams' first contribution to the discussion was to complain that Deolalikar was being taken way too seriously. Shortly after that, however, Williams got over it and became one of the most enthusiastic contributors. To me it appeared that he embraced the conversation as fun and valuable in its own right, Deolalikar be damned. Sometimes it takes being on the inside of a great conversation to know what great personal value that conversation can have for you.
My final hypothesis is that great conversations are a social phenomenon that require social catalysts to happen. The publication of an important, provocative claim is not sufficient to inspire open collaboration. We might have had only scattered sniping and skepticism across the blogosphere, with concrete understanding coalescing painfully slowly over weeks and months, instead of having a well-understood refutation in mere days. The additional catalyst was Dick Lipton's exuberant attitude toward the subject, and fair, respectful, generous attitude towards Deololalikar and everyone contributing to the discussion. Lipton helped facilitate an environment in which contributions would not be pre-judged at all, but rather accepted on merit regardless of the source.
ReplyDeleteTo any experts who don't think that something special happened, and are assiduously insisting that they had a right not to participate in what happened, please don't let me intrude on your thoughtful isolation. You are welcome to do mathematics as you have always done it, and as you deem proper. You aren't hurting anyone. At worst you are missing an opportunity to help yourself but that is entirely your prerogative.
Anonymous remarks: This episode has really brought out the differences between two groups in TCS: those who think that the primary goal of research is to discover what is true and false about the world, and those who think we should ... what? Maintain harmony and avoid conflict and hurt feelings? Tell nice intuitively-plausible (but provably false) stories? I agree the world is a happier place if we all say only nice things about each other's work, but where does truth fit into this?
ReplyDeleteThat's easy: truth comes in where Bill Thurston's essay says it does! :)
The classical STEM narratives are mainly deductive and/or inductive and/or aspirational; an outstanding example is the Clay Institute document Interview with Research Fellow Terence Tao (September 2003).
However, although these classical themes undoubtedly will be vital elements of future STEM narratives, there is a growing sense that they are not adequate (in themselves) to the sobering challenges of our 21st century.
A few STEM bloggers have been experimenting with humorous and/or sardonic narratives. Writing "funny" is mighty tough—most folks (including me) have little talent for it—and I think we all enjoy the occasional successes of mathematical humor.
More soberingly, during the past week, the Deolalikar episode has amply demonstrated that writing high-quality sardonicism is far tougher than writing “funny” … requiring Joseph-Heller levels of narrative talent (at a minimum).
IMHO no-one to date has successfully written sardonically about the Deolalikar’s claimed proof (despite numerous attempts) … in fact, no attempt has even come close.
Perhaps more folks need to keep in-mind that (IMHO) Heller’s Catch-22 worked as a masterpiece of sardonicism only because at the end, Orr *did* get to Sweden.
It's not so easy to engineer narratives that can sustain a globe of 10^10 people, of whom 10^7 are professional mathematicians ... in all but the most dystopian futures. And it is precisely the dystopian futures that the STEM community must help to avert.
Although everyone respects the classic STEM narrative of deduction, induction, and aspiration, it must also be acknowledged that the narrative (in North America) is slowly failing ... per-capita STEM enrollments have been falling for two generations.
If humor and sardonicism are not effective remedies to this long, slow STEM decline ... in the face of steadily growing planetary challenges ... then what is?
Let me apologize for my double-post; the server gave me a "too long" error the first time, so I broke it up and reposted without first verifying that my original post failed.
ReplyDeleteLet me apologize also for relying on memory rather than "doing my homework" as Ken Regan would urge me to. It was Russell Impagliazzo who I was remembering, not Ryan Williams. Impagliazzo's first post to Lipton's blog began like this:
"I am somewhat distressed to see so many people spending a lot of time on this. It does not actually look like a serious attempt at P vs. NP to me. It does not seem to have any original ideas[...]"
Later on, however, Impagliazzo made half a dozen constructive posts on Lipton's blog, indicating that he was willing to spend time on the conversation on it long after having declared it a waste of time! He must have been getting enough out of the discussion to make his participation worthwhile.
It seems to me that Fritz Juhnke's posts have made some solid points.
ReplyDeleteLeonid Gurvits' alternate perspective on Michael Nielson's Polymath Wiki is another concrete example ... Gurvits' alternative view has already been of substantial help to our QSE Group in code development.
So perhaps GASARCH's first-posted impression will prove to be essentially right: "I would bet that he [Deolalikar] proved something very interesting, but not P ≠ NP"
Dane Moskov's property testing algorithm was invented in 2010 but its publication was postponed till 203x. Together with some other minor ideas, that paper gave her the second Mil. prize ever awarded. (NYT 3000, History of Sciences)
ReplyDeleteOnly after reading the comments here did I learn that by carrying out this duty, I risk sacrificing my reputation with half of the community, who will conclude only that I am "nasty" for making an author feel bad by pointing out errors in the paper and suggesting that these errors discredit the paper.
ReplyDeleteHow did we ever get to the point where respected researchers are defending the idea that it doesn't matter whether the proofs in a theoretical paper are correct, or whether authors admit errors when they are discovered?
You are wrong. The discussion here is not about "nastiness" or pointing errors, but about non-seriousness. Most of the established TCS persons commenting negatively in public on VD's paper, have done so in a manner that exposed their unseriousness. They have not pointed to a mathematical flaw or to a specific scientific flaw, or have not engaged in a serious discussion on the paper as a social phenomenon, but have opted to write humorous, and gossip-like comments. Since we have other explicit examples (on Lipton's blog) of reactions which were serious and grounded (be it negative or positive), we can conclude that the first group of people have demonstrated a sort of superficiality that is possibly projected to other aspects of their work.
Only after reading the comments here did I learn that by carrying out this duty, I risk sacrificing my reputation with half of the community, who will conclude only that I am "nasty" for making an author feel bad by pointing out errors in the paper and suggesting that these errors discredit the paper.
ReplyDeleteHow did we ever get to the point where respected researchers are defending the idea that it doesn't matter whether the proofs in a theoretical paper are correct, or whether authors admit errors when they are discovered?
You are wrong. The discussion here is not about "nastiness" or pointing errors, but about non-seriousness. Most of the established TCS persons commenting negatively in public on VD's paper, have done so in a manner that exposed their unseriousness. They have not pointed to a mathematical flaw or to a specific scientific flaw, or have not engaged in a serious discussion on the paper as a social phenomenon, but have opted to write humorous, and gossip-like comments. Since we have other explicit examples (on Lipton's blog) of reactions which were serious and grounded (be it negative or positive), we can conclude that the first group of people have demonstrated a sort of superficiality that is possibly projected to other aspects of their work.
hey was this really DON KNUTH LEAVIN COMMENT BEHIND ????
ReplyDeleteCAN SOMEONE CONFIRM ???
DON, ARE U READING THIS ??? PLEASE I AM SO CURIOUS NOW
DON ?
Don Knuth used email from 1975 till 1990. Afterwards, he never used email. Do you expect him to comment on blogs?
ReplyDeleteIt ... was ... Knuth ... !!!
ReplyDelete
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" rather than e.g. topological groups is just the very definition of the field of study.
ReplyDeleteAnd yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth
I don't think that's the way "depth" is understood in phrases such as "deep insight" or "deep
theorem". But anyway with that definition most of combinatorics is not deep either. Does it mean it's easy or a applied
math field? Some "mathematicians" of the older generation seem to think so, in exactly the same
unjustified way you seem to feel about TCS. Do you agree with them?
As a matter of fact, all other things equal, depth for its own sake (in your sense) is 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.
General theories usually arise as generalization of problem-solving techniques developed to answer questions in some field. If beautiful theories are built on the way to tackle the problems (thereby making the field "deeper", I guess), then so much the better, but some fields (e.g. algebra) just lend themselves better to this than others (e.g. combinatorics).
If your main focus of research is proving theorems, then you're a pure mathematician regardless of how "applied" your field is.
ReplyDeleteBut anyway with that definition most of combinatorics is not deep either. Does it mean it's easy or a applied
ReplyDeletemath field? Some "mathematicians" of the older generation seem to think so, in exactly the same
unjustified way you seem to feel about TCS. Do you agree with them?
Actually, the part of combinatorics that is mostly useful in mathematics -- namely algebraic and enumerative combinatorics and connections to representation theory -- is a quite deep subject with roots going back to Schur, Frobenius, Young and others. Mostly, mathematicians think of it as a rather deep subject with connections to almost every other field of pure math.
The part of combinatorics that used mostly in TCS -- namely, Erdos-Turan style extremal combinatorics, is newer and not as deep and with fewer connections so far. But recent work of Tao and Green, Gowers, Bourgain has certainly made it deeper. However, problems that most TCS people deal with it even here is not as deep as the work of these authors.
Regarding mathematical depth, we have Solomon Lefschetz' "If it's just turning the crank, then it's algebra; but if there is an idea present then it's topology."
ReplyDeleteAnd Lefschetz' aphorism can be naturally extended by asserting that if there is a narrative present too, then it is systems engineering.
Here the point is that the design and repurposing of narratives is emerging as *the* central theme of modern systems engineering ... mere technologies, both mathematical and otherwise, being nowadays regarded as means to this larger end.
That is why modern systems engineers take such a keen interest in what Dick Lipton calls the "proof technologies" of modern mathematics; it's because these technologies are fundamental to the construction of both proofs and narratives.
This is why it often takes awhile to appreciate whether a new result and/or technique is deep ... one signifier of mathematical depth being the repurposing of classical mathematical narratives to serve new ends.
Ever-deeper mathematical technologies are creating an ever-expanding domain of proofs and narratives ... just when we need them to address the planetary-scale challenges of the 21st century ... it's fun!
That is how systems engineers view these matters, at any rate.
The proof of P != NP is actually three pages long and known to all serious complexity theorists. You will never publish more than three papers in serious conferences without sending this proof to all of the others who already know it.
ReplyDeleteIf you wish to find the proof, meditate on global maximums. Are they achievable by recursion? Look to the pumping lemma.
And now I've said too much! They are tracing my IP address as you read this...
I don't think it is our responsibility or right to judge whether someone is a "serious" researcher. But we do need to judge whether a particular paper is "serious", and a casual inspection of this paper reveals that it is not, at least not a serious attempt at a proof (as opposed to an announcement of the existence of a proof known only to the author, and a vague outline.)
ReplyDeleteWhenever I start a class, and need to discuss academic honesty, I tell the students that the two currencies of academia are Ideas and Reputation. Dishonesty is taking one currency without giving the other.
Several people have asked whether premature announcements of strategies by mathematicians are valuable or need to be ignored. Actually, many mathematicians and complexity theorists have written excellent papers about failed attempts or approaches they have almost given up on for hard problems. These are acts of generousity, because if any one else later carries out their programs, the original proposers will only get a miniscule fraction of the credit (and certainly, no prize money). So they are giving Ideas without getting Reputation.
Such an act of generosity is quite different from putting forward an unverified claim to a large problem. There, the author is establishing a claim to credit for solving a problem without providing benefit of their knowledge to the community. They are claiming Reputation without providing Ideas. Of course, this frequently backfires...
If Deolalikar renounces claim to a complete proof, and says that anyone can work on making his sketch into a proof, that would change his work to one of generosity. (I am still skeptical of the possibility of completing the sketch, but I would have a good opinion of the author.)
Russell Impagliazzo
On the seventeenth day of August,
ReplyDeleteDeolalikar sent to we
a manuscript that noone could see.
I just read on Lipton's blog that Deolalikar had not wished to go public with the original manuscript, and is sending his revised manuscript for refereeing rather than releasing it publicly. So while I stand by the general principles mentioned in the earlier post, I no longer think it applies to this paper.
ReplyDeleteRussell Impagliazzo
Well-said, Russell Impagliazzo. Too bad your comment is sandwiched between two idiotic ones.
ReplyDeleteIf privacy was Deolalikar's original wish, the entire episode reflects badly on Lipton for orchestrating a painful public evisceration of the proof.
ReplyDeleteIf "courage is grace under pressure" (attributed to Hemingway and many others), then Vinay Deolalikar is faces an exceptionally challenging opportunity to show his mathematical courage.
ReplyDeleteTwo traits in particular may be called-for: humility and patience; these are mighty tough for almost everyone. I wish him well, as IMHO essentially everyone does.
If privacy was Deolalikar's original wish, the entire episode reflects badly on Lipton for orchestrating a painful public evisceration of the proof.
ReplyDeleteLipton got permission from D before posting. Perhaps D gave permission because, by then, the cat was out of the bag. The mystery person here is whoever put the first draft up on Scribe.
Of course posting on Scribe was inappropriate if it was against D wishes. However, D allowed the whole shenanigan at Lipton's blog and posted online his own copy (along with dedications, updates, summaries, etc). Apparently he still thinks his proof can be salvaged.
ReplyDeleteOr perhaps Deo didn't know it would get this out of hand- kind of like when
ReplyDeletevarious agencies took online votes only to have Stephen Colbert win them.
Some people do not realize the impact of the web yet.
Dane Moskov's property testing algorithm was invented in 2010 but its publication was postponed till 203x. Together with some other minor ideas, that paper gave her the second Mil. prize ever awarded. (NYT 3000, History of Sciences)
ReplyDeleteIs this some sort of attempt at linking two of the most controversial topics to be discussed on this blog? Wait, no, that was Dana Moshkovitz.
@Russell Impagliazzo:
ReplyDeletenot quite. ur comment implies that the great proof solved by russian mathematician was just sketch and the patch up work by chinese mathematician yau was actual proof.
this is not a first choice argument that i would have expected from someone deemed to be a first choice researcher
Lance shouldn't say he is skeptical? Lance should phrase his skepticism more politely?
ReplyDeleteNo, he can be skeptical. But the real issue is his comments afterwards, that too based on other people's hard-work, the "I told you so" attitude. There was a comment of Lance to the effect that "He should have been more negative". Why? Just because, after one week some people did hard work and found flaws? What if they hadn't?
How respectable a researcher is Deolalikar? I do not know any other work that he is done.
Oh, well. It looks like you even didn't take care of visiting his home-page where he was hosting his drafts and had there a list of his publications. Btw, visiting VD's homepage was one of the first things Lipton did to find out who this guys is and VD's past-work (on infinite Turing machines) interested Lipton. So, tell us please. Did you really see the paper?
The fact that some in the community took his work seriously is an excellent sign that our community is not elitist.
Referring to Lipton, Tao and others, right?
But this begs the question: why was it on slashdot and why did Lipton take it seriously?
Hmm. On one hand you praise Lipton and say it shows well for the community. And just after that you question why Lipton took it seriously? Is this not a straight contradiction? So, what did you want Lipton to do exactly? And why?
And by the way, Lipton has answered all these questions at many places. For example, see his latest post on CACM blog and also his very first post on the topic. There was a comment by no less that Steve Cook in the forwarded email that said "this looks like a serious attempt", that's why Lipton says he took a notice. Then, Lipton figured out from VD's home page that VD had some publications on the infinite versions of P=NP. And thirdly, Lipton was interested when he saw in VD's paper a link between finite model theory and statistical physics, which Lipton considered as a novel and interesting approach. And he was particularly positive about the use of finite model theory initially, as it had given some nicer results earlier. All this is mentioned in Lipton's posts. It seems that you have not seen Lipton's posts either. So, please tell us, why are you commenting on this topic?
To Russell Frank:
ReplyDeletePerelman was a classic case of generosity. He provided the ideas, but didn't stick around for the recognition. I don't know who ``deseves'' credit for the work, but he didn't want it. Yau et. al. clearly deserve a lot of credit, but it was a little much of them to demand the entire prize. I'm glad I'm not on the committee who had to decide that mess.
Russell Impagliazzo
Ideas are not like a currency. If you give someone money, you have less yourself, whereas if you give someone an idea, you both have it all. What is limited in supply is only recognition. Linking the "currency" of ideas to the currency of reputation has the effect of subordinating the free and open nature of ideas to the limited and stingy nature of academic reputation.
ReplyDeleteFree exchanges which allow ideas to flourish and multiply are inhibited by exaggerated concern for reputation. Someone posted above that there are two kinds of mathematicians; let me agree and describe them differently: There are mathematicians for whom ideas are subordinate to reputation, and mathematicians for whom reputation is subordinate to ideas.
At the risk of pushing a metaphor too far, maybe it's better to say ideas are like stones. They're common, but only a precious few are valuable. The hard work is to search for these valuable ideas among the huge number of common ideas.
ReplyDeleteThere are generous mathematicians, and stingy ones, but most of us are somewhere in the middle. We'd pursue ideas for their own sakes, even without recognition, but that doesn't mean we don't like getting the credit we deserve.
really, almost no one gets anywhere in research pursuing credit rather than wanting answers. But on the other hand, researchers are human, and if you deny yourself or others the human need for a pat on the head for a job well done, you won't get far either.
Russell Impagliazzo
@anon77: ...that deserves brutally fucked...
ReplyDeleteThis guy is a complete crank. Despite the fact that he has been completely exposed and his proof was shown to be a mockery of serious research, he refuses to admit he failed. Sore loser and a typical Indian cheat.
ReplyDeleteDear Blog Owners:
ReplyDeletePlease remove the previous two offensive comments. Rape suggestions and racial insults have no place in academic or any civilized discourse.
And you may delete my comment also after the preceding two have been deleted. Thanks.
Totally agree with #84. Please remove #82-83. Such low things shouldn't have appeared in this blog.
ReplyDeleteI agree: please, REMOVE the comments #82-83, they are stupid and offensive.
ReplyDeletehttp://en.wikipedia.org/wiki/Grigori_Perelman#Withdrawal_from_mathematics
ReplyDeletehttp://en.wikipedia.org/wiki/Grigori_Perelman#Verification
http://www.newyorker.com/archive/2006/08/28/060828fa_fact2?currentPage=all
http://www.doctoryau.com/hamiltonletter.pdf
http://www.wired.com/wired/archive/10.06/wolfram.html
http://www.stephenwolfram.com/interviews/89-scientist/
#82 is right.
ReplyDeleteThis is all pathetic. World should have never bothered with the fraudster and his half baked manuscript.
ReplyDeleteLooks like Deolalikar got scooped:
ReplyDeletehttp://arxiv.org/abs/cs/0607093
I wonder what the community will make of this? Are they "proud of him, irrespective of the correctness of his proof"? Does it "look like a serious attempt"? Is anyone "certainly hopeful"?
These are not serious questions, of course. The answer to these questions is "obviously not", and as Lance pointed out, "the word 'must' is troubling" (as in Lemma 1). But it is crucial that all those who stated confidence in Deolalikar's proof to ask themselves, I mean really, honestly ask themselves, the question, "What is difference between the two attempts, that I took one attempt seriously, to the point of defending it, but not the other attempt?"
Personally, I think it all comes down to the pinstripes.