Vinay Deolalikar | |
---|---|
Born | 1971 (age 52–53) |
Nationality | Indian |
Alma mater | Indian Institute of Technology, Bombay |
Scientific career | |
Fields | Computer Science |
Institutions | HP Labs |
Vinay Deolalikar (born 1971) is an Indian computer scientist and a Principal Research Scientist at the HP Labs, working in the Storage and Information Management Platforms Lab.[1][2] On August 6th 2010, Vinay sent a manuscript to various leading researchers claiming to contain a proof that P ≠ NP, a Clay Mathematics Institute Millennium Prize Problem and one of the most important open problems in mathematics and computer science.[2][3]
Biography
Vinay Deolalikar was born in New Delhi, India. He completed his masters in electrical engineering at the Indian Institute of Technology Bombay in July 1994, and obtained his Ph.D. from the University of Southern California in May 1999.[1]
Vinay Deolalikar has delivered several short series of lectures on introductory material for grad students at the Stanford University mathematics department and has written 12 papers on rational function fields and industrial research.[1]
Vinay Deolalikar is married and has two children.[1]
Career
P ≠ NP
On August 6, 2010, Vinay sent out a manuscript[4] claiming to be the proof to P ≠ NP[5] to various researchers with the following text
Dear Fellow Researchers,
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.
This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.
This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.
Comments and suggestions for improvements to the paper are highly welcomed.
The news was first broken by Greg Baker on his blog.[6] The story made it to Slashdot on August 8, 2010.[7] There is some fairly accessible discussion about the plausibility of the proof on Hacker News,[8] and some more technical discussion on Prof. Richard Lipton's blog.[9] Scott Aaronson "put his money where his mouth isn't" by offering Deolalikar an additional $200,000 if he's "awarded the $1,000,000 Clay Millennium Prize for his proof of P ≠ NP".[10] Aaronson later stated that some journalists had missed the point of his post, and wrote: "let me now state the point as clearly as I can. The point is this: I really, really doubt that Deolalikar’s proof will stand."[10] AOL News and PC World also reported the claim.[11][12]
Deolalikar, along with Joel David Hamkins and Ralf Schindler, had previously proven that for infinite-time Turing machines, a model of hypercomputation describing abstract computers that can carry out computations of infinite length, the analogous class P is properly contained in the intersection of the infinite time versions of NP and Co-NP.[13] The inequality of P and NP for infinite-time TM's had previously (2002) been proved by Ralf Schindler.[14]
On August 9, Richard Lipton and Ken Regan wrote a summary of unresolved issues raised by readers of Deolalikar's paper during the first day of review.[15] Suresh Venkatasubramanian opened a web page for collaborative analysis of Deolalikar's proposed proof, now hosted at the Polymath project wiki.[16]
On August 10, the paper and its description were temporarily removed from Deolalikar's web site.[1] Richard Lipton subsequently wrote (August 10): "we have been communicating with Vinay, who is occupied with revisions to answer queries that have been made—and nothing should be inferred from periodic changes in links and drafts and wording on his HP sites."[17] A new draft and a note saying that the final version will be submitted to journal review were added a day later. On August 11, Lipton published a response from Deolalikar addressing some questions reviewers had raised about the proof.[18]
Status of proof
In the same article that published Deolalikar's response,[18] Lipton wrote "Vinay Deolalikar is standing by his P ≠ NP claim and proof". Lipton also reposted a comment[19] from noted mathematician Terence Tao which Lipton said "best summarized" the consensus of the reviewers. Tao wrote:
- I think there are several levels to the basic question “Is the proof correct?”:
- Does Deolalikar’s proof, after only minor changes, give a proof that P ≠ NP?
- Does Deolalikar’s proof, after major changes, give a proof that P ≠ NP?
- Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?
Tao answered "No" for question #1, citing reasons given in the polymath wiki, and “Probably not, unless substantial new ideas are added" for question #2. However, Tao described question 3 as "still not completely resolved, and still worth pursuing". On August 12, Neil Immerman found an additional "serious hole" in the the proof, connected to an erroneous argument based on finite model theory (Immerman is an expert in that topic) in the first part of the proof.[20], in response to which Tao updated his answers to "No", "No", and "Probably not".[21] New Scientist reported that the proof "seems to be running into trouble".[22]
References
- ^ a b c d "Vinay Deolalikar". HP Labs. Retrieved 2010-08-08.
- ^ a b http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html Jamieson, Alastair (2010) Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP. Daily Telegraph UK, 11 Aug
- ^ August (2010) Print Million dollar maths puzzle sparks row, By Victoria Gill Science reporter, BBC News
- ^ "P ≠ NP" (PDF). Vinay Deolalikar. 2010-08-09. Retrieved 2010-08-09.
- ^ "Q and A on P vs. NP". Eric Stansifer. Retrieved 2010-08-13.
- ^ "P ≠ NP". Greg and Kat’s blog. Retrieved 2010-08-08.
- ^ "Claimed Proof That P != NP". Slashdot. Retrieved 2010-08-08.
- ^ "P ≠ NP". Hacker News. 2010-08-08.
- ^ "A Proof That P Is Not Equal To NP?". Richard Lipton. 2010-08-08.
{{cite web}}
: no-break space character in|title=
at position 31 (help) - ^ a b Aaronson, Scott (2010-08-09). "Putting my money where my mouth isn't".
- ^ "P = NP = WTF?: A Short Guide to Understanding Vinay Deolalikar's Mathematical Breakthrough". AOL. 2010-08-10.
- ^ "HP Researcher Claims to Crack Compsci Complexity Conundrum". PC World. 2010-08-10.
- ^ Deolalikar, Vinay; Hamkins, Joel David; Schindler, Ralf (2005). "P ≠ NP ∩ co-NP for Infinite Time Turing Machines". Journal of Logic and Computation. 15 (5). Oxford University Press: 577–592. doi:10.1093/logcom/exi022. ISSN 0955-792X. Retrieved August 9, 2010.
{{cite journal}}
: Unknown parameter|month=
ignored (help) - ^ Ralf Schindler, P != NP for infinite time Turing machines, Monatshefte für Mathematik 139 (4) (2003), pp.335-340. pdf
- ^ http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/
- ^ http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper
- ^ http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/
- ^ a b http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/
- ^ http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4885
- ^ http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/
- ^ http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comment-5223
- ^ http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html
External links
- Vinay Deolalikar at the Mathematics Genealogy Project
- Biography at HP Labs
- Wiki page clearinghouse about Deolalikar's P ≠ NP paper.