In 1961 Kennedy said "this nation should commit itself to achieving the goal, before this decade is out, of landing a man on the Moon and returning him safely to the Earth". In 1969 Neil Armstrong and Buzz Aldrin walked on the moon and returned to earth safely. In the 46 years hence man has gone no further.
Bill Gates founded Microsoft to place "a computer on every desk and in every home". Once he succeeded, Microsoft lost its way. Their current mission takes a different tact "Empower every person and every organization on the planet to achieve more."
In my life I've seen many a moonshot succeed, from a computer chess program that can beat the best humans, the classification of finite simple groups and the proof of Fermat's last theorem. They all seem to end up with a "Now what?". If you have a finite mission, you can only achieve finite things. We often think of moonshots as an amazing challenge but they serve as limits as well.
In computing we have a law that has become a mission, that the power of computing doubles roughly every two years. These improvements have enabled the incredible advances in learning, automation and connectivity that we see today. We keep making better computers because we don't have a limit just a goal of getting better than where we are today.
When I first started writing grant proposals, a senior faculty member chided me for saying "the ultimate goal of computational complexity is prove P ≠ NP". He said that would kill any grant proposals after we did settle the question. While we are in no danger of solving this problem in the near future, eventually we will and I'd hate to see the field whither afterwards.
My favorite mission comes from Star Trek, particularly the TNG version with "Its continuing mission: to explore strange new worlds, to seek out new life and new civilizations, to boldly go where no one has gone before."
I think there is a big difference between the P vs NP problem, and the moonshot. Reaching the moon was proposed as a prestige project, not really as a scientific challenge. We did know what we needed to do, there were several avenues to get there, and it was clear that what was needed was determination and money.
ReplyDeleteIn contrast, the difficulty with attacking P vs NP is that we do not have good strategies to do so. It is not at all clear that throwing money at it would result in progress.
Hamming famously said that "The purpose of computing is insight, not numbers."
It seems hard to imagine that we could settle the question without making major advances in our understanding of what makes problems difficult, the nature of efficient computation, and other problems that are at the core of what Theoretical Computer Science is about. In particular, P vs NP is not THE problem--it is the poster child for a myriad of similar problems, all of them difficult, and, seemingly, all of them are difficult for the (not well understood at all) reasons.So, it is likely that a proof would give us new techniques, and new insights -- which would suggest further questions.
In particular, settling the P vs NP question might well leave many of the other interesting questions open. (Even if P=NP, what about P vs PSPACE? Arthur-Merlin games? etc. Of course, if P is not NP, we have a whole Complexity Zoo to explore....)
The proof of Fermat's last theorem is a really bad example here: of course the pop sci press stopped caring once a proof appeared, but (that bit of) the number theory community got right on with further work on the Langlands programme (FLT being a corollary of Wiles/Wiles-Taylor, which is a part of that). The effect was more or less the exact opposite of 'what now', rather more like 'hey, perhaps we could actually prove some of this big mass of conjectures, let's get to it'.
ReplyDelete