As a young professor, I wrote a grant proposal and took it to a senior theory professor for comments. He told me to take out the line "The ultimate goal of computational complexity is to settle the P versus NP problem." He agreed with the line, he just said that if we make these claims to the NSF then what happens after someone proves P different from NP? Nothing left to fund in complexity.
There was precedence here. In the 70s and 80s algebraists had the great goal of classifying all the finite simple groups. Once they were done, then what? Other examples are sending a man to the moon in the 60's or having a computer that beats the best human chess player.
Having an ultimate goal can be very motivating but quite limiting if that goal is actually reached. Luckily for us the P versus NP problem is a goal which will not likely be reached for a very long time.
P neq NP is just the FIRST STEP in computational complexity. (If P=NP,
ReplyDeletethen we're in trouble.)
Russell Impagliazzo
As Daniel Barrett once wrote, "If you said P is NP tonight, there would still be papers left to write..."
DeleteFor Fermat's Last Theorem solving it did not begin more research
ReplyDelete(I don't think)
For Szemeredi's theorem, solving it lead to more research.
Godels Inc theorem lead to more research.
The general question is- when a big open problem is solved does it
create a field or kill a field or both? Depends on the question.
One could look at all of Hilberts questions that were solved and see
if the solution created or killed (or whatnot) a field. (A good topic
for a blog--- but sounds too hard for me.)
Bill --- Wiles's proof of FLT absolutely did stimulate more research, notably, it led to the proof of the Taniyama–Shimura–Weil conjecture. It was an important development for the Langlands Program which is very much ongoing work. See http://en.wikipedia.org/wiki/Modularity_theorem
ReplyDeleteAs we all know, Hilbert's great objective was to provide provably complete and consistent axiomatic foundations to mathematics. And we all now appreciate that Hilbert's (seemingly reasonable) objective was unachievable.
ReplyDeleteThe lesson-learned is that a reasonable broader objective for 21st century complexity theory is to seek broader and more various foundations for it, within which issues associated to completeness and consistency can be assessed with greater confidence than in the 20th century.
The past decade has witnessed a burgeoning of constructivist mathematical enterprises — HoTT for example — that provide concrete frameworks for crafting broader foundations for 21st century complexity theory.
After all, neither young nor old complexity theory researchers, nor the practical STEM enterprises that rely upon advances in complexity, are well advised to focus upon objectives that (in judgment of Lance and many eminent researchers) "will not likely be reached for a very long time" … objectives that (as Hilbert and Gödel teach us) may be out of reach forever.
Craig Venter sounds an practical note regarding complexity-related end-game objectives in this recent Business Week interview Craig Venter on the Hail Mary Genome:
ReplyDelete----------------
Q Can you explain what the Hail Mary genome is and where we are with it?
A "It’s funny that that term got out there. We’re trying to design a basic life form—the minimal criteria for life. It’s very hard to do it because roughly 10 percent of the genes are of completely unknown function. All we know is if we take them out of the cell, the cell dies. So we’re dealing with the limitations of biology. If we start with this minimal synthetic cell that we’re designing and building now, you could recapitulate all biology by adding components to that cell. In theory, we could eventually get to humans by adding enough components to that genome."
Q Last year you made it sound like it was about to happen.
A "It’s what the whole history of this field has been. I have been sure we’re about to solve all the problems, and next year people will say, “Where is it?” We have not done it yet. If we had, I probably wouldn’t tell you. But I wouldn’t lie."
----------------
So what is the irreducible (Kolmogorov?) complexity of a DNA-based living organism, given complete freedom in synthetic organism design? Venter promised that his research would deliver a concrete upper bound … but it has proven far harder than anticipated to deliver upon this promise.
"Luckily for us the P versus NP problem is a goal which will not likely be reached for a very long time."
ReplyDeleteI would become very happen if somebody settled P-vs-NP, the Riemann hypothesis, etc. Wouldn't you?
Nice comment. And to be honest, i would not have expected such a statement from a leading tcs researcher...
DeleteWhoa! So expecting such statements from a leading tcs researcher is also an NP problem? We do live in a non-determinant universe, do we not? And even rule bound complexity theory is in that non-determinant universe. If we lived in a determinant universe then we would be able to reliably expect such statements. As I've suggested before, at the risk of sounding recursive, solving the P=NP problem is probably an NP problem. You would expect that in a non-determinant universe. Of course I'm not implying that it cannot be solved.
DeleteI am completely with Russell Impagliazzo: P vs. NP is just ONE of the things to be done. Neither of the two answers will "close" the field. The P-NP question is good to motivate the research for "foreigners" (NSF and others). But I often wonder why we put this P-NP question also as our "real flag". None of the (two) answers to this question will answer MAIN questions like "is multiplication harder than addition?", "does matrix multiplication indeed requires more than n^2 operations?", etc. Even if P=NP, we can have a growth from n to n^{billion} when going from NP to P. Neither Shannon, nor Kolmogorov, nor Lupanov would be happy when seeing this "advertised complexity theory", sorry Lance ...
ReplyDeleteI think that when Lance says "solve P vs NP", he means also "and related complexity questions". I would take this to include both uniform and non-uniform complexity, both average case and worst case, both deterministic and randomized (and quantum), both time and space (and parallel time) and do all of the above with reasonably close explicit lower bounds and upper bounds. Many of us expect all of these to follow from whatever techniques suffice to solve the narrow definition P and NP, but if that is not the case, then clearly we want the wide definition rather than the narrow one.
ReplyDeleteI for one would be quite happy if P vs NP (in the wide definition) was solved and the whole field is 'finished'. This is a 'happy end', and scientific fields often have 'ends' and then science moves to other open questions.
Solving P vs NP will not be the end for computer complexity, it will be a new start. Actually I think the P=NP magical automatically solving everything algorithm is some kind of fantasm, a myth. The solution of N=NP may, more realistically, comes in the form of 1 or 2 new fundamental number theory theorems implying new maths reasoning possibilities, opening doors we don't even know about.
ReplyDeleteA new vision where computer complexity specialists and all the maths community will desperately be needed to solve all NP problems one by one using hours of our brains. I don't believe in magic, at all.
What are "related" complexity questions: NP vs coNP? P vs NC? Solvability of natural problems in quasilinear time?
ReplyDeleteThe P vs NP question is the biggest prize out there but it would be surprising if the techniques that solve it automatically translate to every important complexity problem. More likely, as Russell suggests, it opens up many more directions to explore.
1) Gee, we don't even know the asy complexity of mult and
ReplyDeletethats been open since the Rhind pap. (1650 BC).
2) While I am sure that Lance and most people would be delighted
if P vs NP is solved there may be some sort of let down.
I know a prof who told me that the day he GOT Tenure was sad
since after all of that effort the question finally becomes
OKAY, NOW WHAT? I am happy to say that prof DID answer that question
and has done well, but there is that moment when you pause to think
about it.
1) Gee, we don't even know the asy complexity of mult and
ReplyDeletethats been open since the Rhind pap. (1650 BC).
2) While I am sure that Lance and most people would be delighted
if P vs NP is solved there may be some sort of let down.
I know a prof who told me that the day he GOT Tenure was sad
since after all of that effort the question finally becomes
OKAY, NOW WHAT? I am happy to say that prof DID answer that question
and has done well, but there is that moment when you pause to think
about it.
As a mathematical problem, the resolution of P vs. NP would most certainly be a part of a developed and quite deep mathematical theory. As such, it would indeed not be the end of "complexity theory", as it would be a starting point of a new, further developed, mathematical theory. (Somewhat, like the resolution of continuum hypothesis is far from being the end of set theory.)
ReplyDeleteOn the other hand, as Noam states, when viewing P vs. NP as a question about the nature of efficient computation, the resolution of P vs. NP could probably be the ending of a the theory of computational complexity.
Since I think of ToC as mathematics, I subscribe to the first viewpoint.
Actually, Lance is right when saying that "Having an ultimate goal can be very motivating but quite limiting if that goal is actually reached." As some dangerous consequences of having an "ultimate goal" I see:
ReplyDelete(1) The problem P=NP sounds something like Einstein's E=MC^2, very attractive.
(2) Lots of "proofs/disproofs" -- a consequence of (1) -- which does not contribute to our field being accepted by others as a serious enough one.
(3) Huge lack of motivation for young people to attack "less ambitious" problems, (to prove ANY non-trivial lower bound, in ANY non-trivial model) -- the most annoying consequence.
(4) After P!=NP will be finally proved, the authorities (like NSF) can be indeed "convinced" that that's was with Comp. Complexity ...
This is why -- especially because of (3) -- I am rather reserved with stating "ultimate goals". We could perhaps state them as "most urgent" or "most annoying" or "methodological" goals. Micro-world is not less complex than the universe.
Unfortunately P vs NP has finally been resolved:"P=NP iff P!=NP". If you don't believe it, just ask Luca Trevisan and Boaz Barak about my recent (third) JACM submission.
ReplyDeleteBest,
Rafee Kamouna.
wow, haven't seen this guy post his claims in a while, like almost three years I think
DeleteBy the vigor of their ideals, by the stability of their perceptions. By the vigor of their concepts, by the resoluteness of their outlooks.
ReplyDeleteBest,
Rafee Kamouna.
Q.E.D. ...
ReplyDeleteI forgot to add to (1) "and + 1 mln price" ... will we have Grigori Jakowlewitsch Perelman in TCS?
Grigori Jakowlewitsch Perelman believes he can control the universe, not only TCS.
ReplyDeletebest,
Rafee Kamouna.