A Stimulus Package for P=NP
Should we spend money on p=np
Dick Karp started all of this. He is, of course, a Turing award winner for this famous work on the P=NP question. He has also won just about every award possible: he recently (2008) was one of the laureates awarded the prestigious Kyoto Prize by the Inamori Foundation.
While Cook proved the first basic theorem about SAT, I believe that one could argue that Dick’s work was essential to get the “balling rolling”. His contribution was in setting up the problem in a clean way, in naming it in a beautiful way, and in showing that it had applications well beyond logic and complexity theory. However, do not get me wrong, Cook contribution was immensely important. In a later post I would like to go over how the community initially reacted to Cook’s and Karp’s work back in the early 1970’s.
Today I would like to suggest that the government (NSF?) should fund a major project on P=NP, with the goal of accelerating the discovery of a solution. The reason I mention Dick is that he and I do not agree on this issue. I have had many conversations over the years with him on this topic: should we fund research expressly to attempt to solve P=NP? I believe that we should. Dick does not.
I am curious what you may think, so please let me know. I do not want to give our views now. I would prefer to hear your thoughts first: so please post a comment or send me an email. Given the huge amounts of money being spend by Washington these days, how could a few tens of millions of dollars not be a good investment to get people to work hard on this problem?