A researcher at the beginning of his career has to please others. In order to receive a Ph.D., get a job and eventually tenure, he has to not only produce good research but research of value to others. The researcher might think that once he gets tenure he can do the research he wants, but by that time he has become so specialized it is impossible to change direction.Looking at economics can give us a glimpse into the near future of computer science as a discipline. Though economics as a field has been around for a very long time, only since the 1950's did economics develop as a rigorous mathematical discipline. This gives economics about a 15-year head start on computer science.
When I started in grad school in the mid-80's, I could follow nearly every talk at the major theory conferences, STOC and FOCS, though I would not have followed any computer science talk which might have been true 10-15 years earlier. These days I can understand the importance of the main results of maybe half of the talks and have actual interest in only a small fraction of these. The growth of specialty conferences such as Complexity, SODA (algorithms), SoCG (Computational Geometry), Crypto, RANDOM/APPROX, COLT (Learning Theory), LICS (Logic in CS), QIP (Quantum) and so on have only increased this divide. We get less and less crossbreeding between these subfields of theory.
On the other hand, some researchers still can and do (with some effort) change research areas in theory and general computer science even after tenure. But in 15 years will we look like economics where a late change in field is difficult to impossible and soon after that like mathematics where it often takes years of graduate school just to understand the major open questions in an area.
As long as P vs. NP remains open, there will be one thing that unites our field.
ReplyDeleteAs long as P vs. NP remains open, there will be one thing that unites our field.Frustration?
ReplyDeleteThis is an interesting idea, Scott. How much of TCS is geared more-or-less directly toward resolving P/NP? Asked another way, if the P/NP Proof From The Book fell to earth tomorrow and was grokked by December, would a grad CS department still consider Theory applications for Autumn 2005? :) And in which subdisciplines?
ReplyDeletePersonally, I can say that I am very interested in theory, but I don't think that P=NP or P!=NP would change that at all. Is this true in general, or is it that I do not understand the research correctly and a solution of P/NP would "sweep the rug out from under my feet"?
Maybe I am crazy, but I find it very sad to consider that the field would fragment upon finding a formal answer to what _might be_ a pretty meaningless question.
One might say that the unsolved Hilbert's problems unite all of math. But they don't, do they ?
ReplyDeleteAlthough the fragmentation of theory CS is something to be regretted, it is also inevitable, and in a way is a success of individual areas at becoming richer and more advanced in their methods/problems/what have you.
Isn't this a natural evolution of theory ? we should mourn the passing of an era, but not to the point where we try to reverse the trend.
Maybe that's why math surveys have become so important. Like in Math, in theory we will have a (mostly) common language, the language of polytime and O() notation, and we will come to rely on surveys and other expository writing to bridge the gaps. It will become harder and harder though to have an impact across disciplines.
What worried me more is the growing learning curve hump between quantum computing the rest of theory CS. that actually seems like a field with a very different base language...
Always glad to start an argument. It's interesting to compare to recursion theory and set theory, which continued long after the main open problems were solved (by Friedberg and Muchnik in the 50's and Cohen in the 60's respectively). As far as I can tell, today these fields lack the kind of compelling narrative that complexity has, which might be why you see people moving from those fields to complexity but not vice versa. Even though most work in complexity has no direct bearing on P vs. NP, still the problem is there, like eerie background music that infuses every conference and workshop with a hint of the eternal.
ReplyDeleteSpeaking personally, if the P!=NP Proof From The Book fell to earth, and were already mined to show that NP is not in P/poly, NP is not in BQP, factoring is not in P, etc., I would probably switch fields to the foundations of quantum mechanics, which contains some of the only scientific mysteries deeper than P vs. NP. But as my grandmother might say, "oy gevult, that we should have such problems!"
"As long as P vs. NP remains open, there will be one thing that unites our field." Heh. Spoken like a true blue-blooded member of the STOC/FOCS dynasty.
ReplyDeleteMost of the broader theoretical computer science community (SODA/SOCG/ALENEX/LICS/COLT/PODS/WAFR...) has about as much interest in P-vs-NP as any well-educated computer scientist or mathematician. We know what the question means, and we're happy to use it to boggle student minds ("You can win a million dollars by solving Tetris!"), but it has nothing whatsoever to do with our actual research interests. Just like Fermat's Last Theorem, the Poincare conjecture, and the four-color theorem, a huge body of intellectual effort has grown out of P-vs-NP, but by now the majority of that effort is completely unrelated to the original question.
This is a GOOD thing.
P vs NP is an important problem. May be a very important problem but what's so deep about it?
ReplyDeleteA deep problem is one that explains a lot
of phenomenon in nature. So formulation of NP-Completeness was deep. But, how is P vs NP deep??
See, if you are getting obsessed by P vs NP its not because it is deep but its because you find it important! You are coming not from the perspective of interest but from your 'ego'. Andrew Wiles solved Fermat's last theorem - in what way
did it change the field of math? I suspect not. Go with what you find interesting rather then what you consider important...
SV