The story goes that Andrew Wiles dreamt of proving Fermat's last theorem when he was a kid. No surprise since all of us math-loving kids dreamed of solving this famous problem. We certainly talked about it much longer than the more important Fermat's Little Theorem which already had a proof. Now my kids have never heard of Fermat's last theorem. Why should they? Nothing there left to dream there.
It is the challenges that inspire. It was much more interesting to go to the moon in the 60's than it is today. Computational complexity is blessed with such a great challenge, one of extreme theoretical and practical importance, that brings needed attention to our small domain.
My CACM article on P v. NP has proven very popular in great part because of the excitement of the unknown. In that article I wrote "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not." For much as I'd like to see a proof that P ≠ NP, I would also hate to lose that mystique. Who would read an article on the status of P v. NP if the status was "proven 15 years ago"?
Let me note one correction in the article pointed out by Andrew Appel: It was Armin Haken, and not his father Wolfgang, that showed that there are no short resolutions proofs for the pigeon hole principle.
Update: Eric Allender has his own A Status Report on the P versus NP Question appearing in the Advances in Computing series. We should have coordinated titles.
Fermat's Last Theorem had
ReplyDeleteALOT going for it before it was solved:
(1) Open,
(2) can be stated to the layperson,
(3) the myth that Fermat knew a proof -- the
``too big to fit in the margin'' notion sounds so
mysterious,
(4) Cash prize for it.
P vs NP has (1) and (4).
(2) partially- depends on the layperson. (3) not at all.
Even for ones OWN open problems it can be sad when they are solved since you were hoping to have it be a LONG STANDING OPEN PROBLEM!
Fermats last theorem used to be what people would point to for an open problem in math.
What will they point to now? Goldbach's conjecture is pretty good
since you can tell it to a layperson and even do alot of examples.
As for the (3) aspect, isn't there a lost notebook of Gödel containing a sketch of a proof, to which he cryptically refers in one of his letters?
ReplyDeleteP vs NP can be stated to a layperson, though maybe not precisely. Yet all those mathematical clarifications take only away from the question (is polynomial time really the right notion and similar concerns.) People will understand the notion of efficiency without a mathematical underpinning.
ReplyDeleteThat said, the philosophical appeal of P vs NP cannot even be compared to Fermat's last theorem. Come one, no one cared about that question as such.
If only some Russian mathematician in the 70's would have given a talk about P not being NP at the academy (doubtlessly under a title that would not make you guess subject of talk), and then vanished forever, we might have some mystery left, maybe even better than Fermat's rather cheesy attempt.
Thanks for writing the CACM article. As a recent admit to the UW CSE department, the primer on P v NP was greatly appreciated.
ReplyDeletep vs np definitely does not have (2)
ReplyDeleteIt is not necessary that everyone think alike---it is not even desirable!---but IMHO Lance's article nicely summarizes many cogent reasons for regarding P vs NP is the greatest open problem ...
ReplyDeleteThe nearest thing to a heterodox opinion that I came away with from Lance's article, was an equal admiration for upper-bound and lower-bound complexity theorems ... because we are similarly likely to make (what Lance's article calls) "inspiring and mind-boggling" discoveries in exploring both avenues.
I wrote "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not ."
ReplyDelete...and everything was going great in that article until that sentence, whereupon I cringed.
Given the relevance, as your article points out, of PvsNP research and its cousins to matters as serious as national security, it's just irresponsible to finish the article by saying sth like that.
Why is Lance harping on this P/NP thing? If you don't have new things to blog, just don't blog that day.
ReplyDeletehaha last anon is funny.
ReplyDeletebut lance i am disappointed by the fact that you didnt even reference your advisor`s work (as in his conference article) on PvsNP in both of your current papers.
ReplyDeleteI'm wondering just exactly what problem will be solved if the P vs. NP problem will be solved? What I mean by that is what will become impossible or possible that we didn't already know was impossible or possible? It would seem that solving the P vs. NP question wouldn't tell us anything that we didn't already know outside of that one relationship. It that is the case, the question is of little importance. It it is an important puzzle to solve, then why is it important? By stating its importance, a clue might be given that could help solve the problem, if it can be solved.
ReplyDeleteIn defense of Lance's choice of topic, the question of P =?= NP is (IMHO) an ever-green question ... in the sense that the set of problems known to be in "P" is ever-expanding ... and the set of problems in "NP" is ever-expanding.
ReplyDeletePretty much any thinking person sees that a train-wreck is coming soon ... a train-wreck not of mathematics, but of expectations! :)
I was thinking of this when I attended a meeting of David Baker's group yesterday. The Baker group does compuzyme design ... you know ... designing large biological molecules from scratch?
This biomolecular design problem is of course formally in NP ... the Baker group's toolset (both computational and experimental) obviously is in P ... so the task looks hopeless prima facie from the viewpoint of naive complexity theory ... and yet tremendous progress has been made in recent years.
The rate of progress in synthetic biology is roughly the product of (1) the number of target applications, (2) the number of starting homologues, (3) the number of design variants of each homologue, (4) the rate at which the variants can be simulated (in Rosetta), (5) the accuracy with which the dynamics of the variants can be simulated, and (6) the rate at which the variants can be (physically) synthesized, and (7) the rate at which the structure of the variants can be validated by experimental observation, and (8) the rate at which the variants can be experimentally tested for biological activity.
Now, it is evident that each of the preceding factors can be improved by 1-2 orders of magnitude ... "by developments of which we can already foresee the character, the caliber, and the duration" (in von Neumann's excellent phrase) ... and so we are looking at the arrival of a world (pretty soon!) in which the capabilities of synthetic biology are enhanced by an overall factor of 10^8--10^16.
Of course, this is "only" a polynomial factor ... but it is a rather *big* polynomial factor, isn't it? ... it is (for example) the difference between creating one family-supporting job, and creating family-supporting jobs on a planetary scale.
In this world, the set {"P"} and the set {"NP"} are going to adjoin one-another more closely than ever before ... and I agree 100% with Lance that we are guaranteed to learn a lot from this!
This is what was meant in an earlier post when I asserted that three meetings this summer had "changed the world" ... these meetings being FOMMS, the Kavli/Cornell Conference on Molecular Imaging, and the ACS symposia on Conformational Biology (Rob Tycko's talk in particular).
Nature magazine ran a series of articles in 2008 titled "Meetings that changed the world" ... the meetings that Nature selected were mainly meetings of program managers ... the meetings mentioned above were more like the Pocono Conference or Shelter Grove ... meetings attended mainly by scientists ... at which the world was changed mainly by the emergence of new horizons and a shared sense of new potentialities.
I think Lance's post---and this whole Computational Complexity blog---contribute very substantially to this thrilling sense of "new horizons and new potentialities" ... for which I am very thankful.
Rahul, I never heard of Gödel working on FLT. He did do some work on the independence of the continuum hypothesis, that was found in his notes after his death, but experts examined what he had and while it was interesting, it didn't get anywhere near far enough to say that he anticipated Cohen's proof.
ReplyDelete