[math-fun] Vinay Deolalikar claimed proof that P != NP
Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP. Paper at http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf http://www.scribd.com/doc/35539144/pnp12pt Some discussion at http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np... including the comment that "the original email he sent out was to very well known complexity theorists at schools like stanford, berkeley, mit, princeton, etc (cook, sisper, vazirani, donaldson, etc)" Text of his email: 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. Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs -- Forewarned is worth an octopus in the bush.
Assuming for the moment that the proof holds up, what are the implications of P != NP? Kerry Mitchell On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP.
Paper at
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf<http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> http://www.scribd.com/doc/35539144/pnp12pt
Some discussion at
http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np...
including the comment that "the original email he sent out was to very well known complexity theorists at schools like stanford, berkeley, mit, princeton, etc (cook, sisper, vazirani, donaldson, etc)"
Text of his email:
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.
Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs
On 8/9/10, Kerry Mitchell <lkmitch@gmail.com> wrote:
Assuming for the moment that the proof holds up, what are the implications of P != NP?
Kerry Mitchell
The author suddenly becomes rich enough to retire, I seem to recall ... WFL
On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP.
Paper at
http://www.scribd.com/doc/35539144/pnp12pt
Some discussion at
http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np...
including the comment that "the original email he sent out was to very well known complexity theorists at schools like stanford, berkeley, mit, princeton, etc (cook, sisper, vazirani, donaldson, etc)"
Text of his email:
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.
Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A million dollars doesn't go as far as it used to :-( (i.e. the Clay Prize), so just from a financial angle, for a fairly young man, retirement doesn't loom. Anyway, how many mathematician really want to retire (possibly from their formal job, but not from mathematics)? Victor On Mon, Aug 9, 2010 at 12:13 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/9/10, Kerry Mitchell <lkmitch@gmail.com> wrote:
Assuming for the moment that the proof holds up, what are the implications of P != NP?
Kerry Mitchell
The author suddenly becomes rich enough to retire, I seem to recall ... WFL
On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
> Vinay Deolalikar sent out email Friday night with a claimed proof that P != > NP. > > Paper at >
http://www.scribd.com/doc/35539144/pnp12pt > > Some discussion at > > > http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np... > > including the comment that "the original email he sent out was to very well > known complexity theorists at schools like stanford, berkeley, mit, > princeton, etc (cook, sisper, vazirani, donaldson, etc)" > > > Text of his email: > > 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. > > Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs > >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Scott Aaronson wrote a nice, not-too-complexity-theory-techical paper about the implications with soap bubbles, Steiner trees, what can work & what can't in quantum computing, and a number of other things: S Aaronson, "NP-complete Problems and Physical Reality" http://www.scottaaronson.com/papers/npcomplete.pdf
Date: Sun, 8 Aug 2010 19:54:15 -0700 From: Kerry Mitchell <lkmitch@gmail.com>
Assuming for the moment that the proof holds up, what are the implications of P != NP?
On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP.
Paper at
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf<http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> http://www.scribd.com/doc/35539144/pnp12pt
Some discussion at
http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np... -- Steve Rowley <sgr@alum.mit.edu> http://alum.mit.edu/www/sgr/ Skype: sgr000 It is very dark & after 2000. If you continue, you are likely to be eaten by a bleen.
Scott has offered to kick in $200K on top of the Claymath $1M prize if the proof is correct http://scottaaronson.com/blog/?p=456 On Mon, Aug 9, 2010 at 7:21 AM, Steve Rowley <sgr@alum.mit.edu> wrote:
Scott Aaronson wrote a nice, not-too-complexity-theory-techical paper about the implications with soap bubbles, Steiner trees, what can work & what can't in quantum computing, and a number of other things:
S Aaronson, "NP-complete Problems and Physical Reality" http://www.scottaaronson.com/papers/npcomplete.pdf
Date: Sun, 8 Aug 2010 19:54:15 -0700 From: Kerry Mitchell <lkmitch@gmail.com>
Assuming for the moment that the proof holds up, what are the implications of P != NP?
On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber@gmail.com wrote:
Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP.
Paper at
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf<http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> <http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> http://www.scribd.com/doc/35539144/pnp12pt
Some discussion at
http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np... -- Steve Rowley <sgr@alum.mit.edu> http://alum.mit.edu/www/sgr/ Skype: sgr000 It is very dark & after 2000. If you continue, you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://thaneplambeck.typepad.com/
David Singmaster took some pictures of one of the 2 surviving complete 2nd edition 1228 manuscripts by Fibonacci. None of the 1202 first editions have survived. Fibonacci sequence http://www.mathpuzzle.com/FibNosClose.jpg Arabic Numbers http://www.mathpuzzle.com/TPBottomDetailbig.jpg Ed Pegg Jr http://www.mathpuzzle.com/
participants (7)
-
Ed Pegg Jr -
Fred lunnon -
Kerry Mitchell -
Michael Kleber -
Steve Rowley -
Thane Plambeck -
Victor Miller