[Note from Bill: He now has an on-line list of papers who still need reviewers]
Everyone theorist should try to prove P = NP and P ≠ NP early in their career to understand why the problem is so difficult to solve.So go ahead and find a polynomial-time algorithm to 3-color graphs. Show that clique can't be solved by small circuits. Not because you will succeed but because you will fail. No matter what teeth you sink into P vs NP, the problem will bite back. Think you solved it. Even better. Not because you did but because when you truly understand why your proof has failed you will have achieved enlightenment.
You will understand that computation is a nasty beast. Very hard to tame, to see what it can't do. Nearly as hard to control, to use it to solve those hard search problems.
Watch Tim Gower's multiple personalities try to tackle even simpler lower bounds. The P v NP monster humbles the best of us. And that's what makes the P v NP problem exciting and us just human.
Here at the UW I've been attending David Baker's Synthetic Biology Seminar, an experience that suggests the following corollary to Nisan's suggestion:
ReplyDelete"Early in their career every theorist should attend a seminar in which researchers tackle NP-hard problems with polynomial conmputational resources. Not to watch them fail, but to watch them succeed."
The point is a Dick Lipton-esque one: there are genuinely mysterious aspects to the ubiquity of solvable problems in science and mathematics.
This seems (to me) to be much the same thing that Noam Nisan is saying, approached from a different direction.
Sorry. The problems you see tackled successfully are NOT NP-hard. They are tractable subcases of NP-hard problems.
ReplyDeleteI agree that finding out what makes these subcases special IS a good research topic--or better set of research topics, as they are heavily problem-dependent.
As for the "unreasonable effectiveness of polynomial time", at least part of the explanation is that researchers like to work in areas where one gets results, and that the quality of computational results only has to equal that of the experiments.
Janos says: "As for the 'unreasonable effectiveness of polynomial time', at least part of the explanation is that researchers like to work in areas where one gets results..."
ReplyDelete---------------
LOL ... that very phrase 'unreasonable effectiveness of polynomial time' often occurs to me at these synthetic biology seminars!
But your remark is not quite correct about the second part. It is most commonly true in engineering (and in medicine too) that one *isn't* allowed to work in areas where results come easily.
Instead one has to deal with whatever patients walk in the door ... or with an overheating planet with seven billion people on it ... with problems that are always messy and often seemingly intractable.
And yet, polynomial resources very commonly are found to be "unreasonably effective" ... it seems that nature is "subtle but not malicious" in a complexity-theoretic sense that is remarkably general.
Great advice.
ReplyDeleteI spent many long nights as an undergrad with my latest proof of P = NP (or P != NP: depending on the height of snow in Ithaca, I was either optimistic or pessimistic).
However, the resulting neglect of my classes led in part to an interesting grad school application adventure. So I would add one more piece of advice: Try to prove it, but only on weekends. (Or, become a grad student as early as possible, then try to prove it. My classmate Scott Aaronson had the right idea.)
Gee, I thought The Humbling Power of P v NP was a terrific topic ... it is a little bit surprising to rather few posts on it (so far).
ReplyDeletePerhaps a similarly appropriate but more provocative title might have been The Flood-Tide and Ebb-Tide of P v NP.
Here "flood-tide" refers to Grothendieck's famous methaphor of a "rising sea" of abstraction in mathematics. The point being: Isn't it true that we now think about P vs NP at levels of abstraction that were unimagined with the problem was first formulated? And don't these new levels of abstraction (in Colin McLarty's words) help "clear away tangled multitudes of
individually trivial problems, put the hard problems in clear relief and makes their solution possible?"
On the other hand, in practical engineering it generally happens that the individually trivial problems are what is chiefly of interest. Luckily for the engineering community, it is an empirical rule that every flood-tide of mathematical abstraction is followed by an ebb-tide of practical application; the wonderful book by Petkovsek, Wilf and Zeilberger titled A=B is a paradigmatic example of this.
That is why (IMHO) students definitely *should* feel daunted by "the humbling power of P v NP" ... because heck ... just as Lance's post argues ... because modern complexity theory's rising sea of abstraction has focused and amplified this humbling power to an unprecedented degree.
But these same students can await the ebb tide ... and contemplate with optimism and enterprise the immense scope of practical applications that the ebb tide is now revealing.
Here too Grothendieck's letters reveal a penetrating understanding: The question you raise "how can such a formulation lead to computations" doesn't bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand -- and it always turned out that understanding was all that mattered.
A very important point is this: it isn't just the complexity theorists who are raising their level of abstraction to achieve (in Grothendieck's words) a "thorough conceptual understanding of what is going on." Pretty much every discipline in mathematics, science, and engineering is experiencing the same flood-tide of abstraction and ebb-tide of applications.
This rich ebb-and-flood is good news for everyone IMHO ... because (as field ecology teaches us) ... it is inter-tidal zones that support the richest ecologists ... and historically this has been true in math, science, and engineering too.
In summary, ebb-and-flood of modern mathematics makes it perfectly reasonable for students to feel *both* considerable humility *and* tremendous optimism.
I'll not be giving up any time soon.
ReplyDeleteM. Michael Musatov
http://meami.org