Conventional Wisdom and P=NP
Does 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 
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 
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”
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 
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
“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
.
Trackbacks & Pingbacks
- Cook’s Class Contains Pi « Gödel’s Lost Letter and P=NP
- Kolata on Funding Research « Gödel’s Lost Letter and P=NP
- Surprises in Mathematics and Theory « Gödel’s Lost Letter and P=NP
Dick, see my point at http://en.wikipedia.org/wiki/P_%3D_NP_problem. Moshe
This is a very nice Wiki article. Please check it out for another view on P=NP.
Let’s assume the CW is wrong and that P=NP. Where do you think that might put us in Impagliazzo’s “five worlds”?
As Vardi’s referenced, there are many fortune hunters on the P-vs-NP problem. But CW dictates us P is not equal to NP since no one has been able to find a polynomial-time algorithm for any of more than 3000 important NP-complete problems. For example L.J. Stockmeyer (1973) has shown that planar 3-colorability is NP-complete. But let us think about it from the other way round i.e., think non-CW way. Let G be a planar graph and consider two types gadgets g_1 and g_2 where g_1 is a graph consisting two triangles with a common edge and g_2 is a graph consisting two triangles with a common vertex. Let G_1={g_1}_k be the graph consisting serially connected k gadgets of type I and similarly G_2={g_2}_k be the graph consisting serially connected k gadgets of type II, where k>=1. Clearly the graph G_1 plus with an (bridge) edge e_b joining the two degree two vertices of G_1 is 4-colorable. So any planar graph that contains this subgraph i.e., G_1,b= G_1U{e_b} is not three colorable. With a similar argument we can show that serially connected gadgets of type II with a certain cycle C in the planar graph makes the graph chromatic critical. That is G_2,c=G_2 U C.
(see http://www.flickr.com/photos/49058045@N00/188725295/sizes/l/ ).
Now if one can show that the only minimal configurations that makes the planar graph 4-colorable are the subgraphs G_1,b and G_2,c then it would be possible to give a polynomial-time algorithm for 3-colorability of planar graph.
if n =1 it would certainly stand true…I am at a loss when it comes to math…perhaps i have missed something here(the boat)..or did the dude purport to say that this would follow giving any value for n or do p and n have values a layman would not be acquainted with?
peace…actually curious
In this case P and NP are acronyms for “polynomial” and “non-polynomial”, not algebraic symbols. See the wikipedia article mentioned on this thread.
thanks, i read a novel by arthur c. clarke which wove this equation into the plot, thus my interest…
Ouch. NP does *not* mean “non-polynomial”, otherwise the question shouldn’t be too hard to answer, right? Hehe.
P=NP, the CW is obviously wrong. The CW cant always be right; they act as if they’re the living solutions to the Entscheidungsproblem, as if they’re always right….