Conventional Wisdom and P=NP
With just five symbols Dick Karp–in 1972–captured one of the deepest and most important questions of all time. When his famous paper first appeared, I believe that no one completely understood the depth and importance of his question. Now over three decades later, we know the central role that plays in our understanding of computation, we know that no viable approach yet exists to solve it, and we know the far reaching consequences of any resolution.
I have been so intrigued by this question, after thinking about it for over three decades, that I decided to start this blog on it. One of the reasons for these posts is that I believe that much of what we believe as a community about may be at best guesswork and at worst just plain wrong. Most think that “obviously” , yet I am not so sure. I really think that the could just as well hold. I think that even experts will enjoy hearing my contrary thoughts on the problem, while they may disagree with what I say, I hope that they will find it interesting.
I will often label something as CW or “conventional wisdom.” I hate to use special “notation”, but it seemed better to use CW then to repeat the phrase “conventional wisdom” over and over. I do not mean to use this in too negative a way. Well it is negative, but do not take it as too negative. Hopefully, these posts will raise issues about CW, and these issues will cause you to re-examine whether or not “obviously” . Mostly I hope to get you to think about the problem.
A further word on CW. I have read about many of the solutions to famous open problems in mathematics, and the CW for them was often wrong. For example, consider Hilbert’s : the undecidability of Diophantine equations. As eminent a logician as Georg Kreisel voiced the opinion that the Davis-Robinson approach would fail because it was trying to prove too much. He noted that their approach would prove more than undecidability, but would also prove that the problem was equivalent to the halting problem. He thought this might be false, but Yuri Matiyasevich proved him wrong.
As another, more recent example, consider the resolution of the Poincare Conjecture. While most believed the conjecture was true, many still doubted the conjecture. For years some eminent topologists worked on trying to find counter-examples; some even wrote a program that searched for them. Of course Grigori Perelman proved the doubters wrong: there are no counterexamples. The point is that CW can be wrong. The whole thrust of these posts is to raise issues about . I hope that these issues interest you. Please enjoy the posts.
“You should never bet against anything in science at odds of more than about 10-12 to 1 against”. Ernest Rutherford, the winner of the Nobel Prize in Physics in 1908