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
- 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
- P=NP consequences « Constraints
- Giving Some Thanks Around the Globe « Gödel’s Lost Letter and P=NP
- P versus NP, universal machines and spherical matrices | Quantum Wittering
- El ecommerce, resuelta la hipótesis de Riemann | ebusinesshoy
- The different forms of quantum computing skepticism | Windows On Theory
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.
I totally agree with Prof. Vardi point (as well as with Prof. Nerode’s). Let me add one of my favourite quotes, by George Bernard Shaw:
“The reasonable man adapts himself to the world; the unreasonable persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable.”
Excellent quote.
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.
Indeed. That should read “non-deterministic polynomial”
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….
I definitely think this is a good article. I find that myself aswell that people automatically assume that it’s obviously “P != NP” when I see them both just as likely since I find in my research some compelling points to consider “P= NP”.
For me, conventional wisdom (CW) on P vs. NP misses the point. CW, in the minds of most computer scientists, appears to rely on the following justification:
1. Finding a solution to any given problem is obviously fundamentally harder than verifying a given solution to that same problem.
2. Verification of proposed NP-problem solutions can be done in polynomial time.
3. If finding a solution is fundamentally harder than verifying a given one, and verification can be done in polynomial time; then finding a solution to an NP problem must take fundamentally more effort than polynomial time. Therefore NP must be firmly beyond the grasp of any polynomial-time algorithm.
HOWEVER this line of reasoning is potentially wrong. Step 3 makes the fundamental error. We might find, for example, that while verification can be done in low-order-polynomial time, finding one or more solutions might be done in high-order-polynomial time (perhaps also, with a high constant of proportionality.) This would satisfy common sense in that finding a solution would be at least “as hard” as verifying a given solution. But it would contradict CW in that NP would be in P (albeit, residing in a more expensive segment of the P set’s landscape.)
Some arguments in favour of CW appear to ignore the fact that NP is a distinct set of fundamentally equivalent problems, and that in accordance with Gödel’s theorem(s), there are known problems that are fundamentally harder than NP and therefore outside that set. So finding a polynomial-time algorithm for solving NP problems would not violate fundamental general theories of complexity.
I keep wondering if P=NP could be independent of the ZFC axioms, just like the continuum hypothesis. This would mean that a practical implementation of P = NP could not be found, but it would not be possible to prove that they are different either. Very intriguing…
Is P=NP mathematically true ?
Please read my proofs:
http://leibnizengine.wordpress.com/2011/02/23/p-np/
I like this Conventional Wisdom and P=NP Gödel’s Lost Letter and P=NP , enjoyed this one thanks for putting up keep update Conventional Wisdom and P=NP Gödel’s Lost Letter and P=NP.
In your comment, the lost letter seems to be the one between the “G” and the “d” in his surname.
Cheers.
P.
Indeed, that letter sometimes goes missing when WordPress figures our post titles, for example http://rjlipton.wordpress.com/2011/10/31/an-interview-with-kurt-gdel/ :-). Or it becomes an unumlautted o.
Hello Prof. Lipton
I decided to self-publish this and let the general math and computer science communities have an opportunity to read it before submitting it to a journal:
http://www.scribd.com/doc/61288772/The-Art-of-Infinite-Reckoning
I think you will find it interesting. I don’t expect it to be understood for at least 6 months, but hopefully there is a journal interested in publishing it or a revised version of it. All I ask is that it is not immediately dismissed based on preconceived notions of what is possible, as this is a completely new way of representing transfinite number. If you have any questions or comments, as well as corrections, please let me know.
Just to draw your attention to a new algorithm which seems capable to compute the maximum clique of a graph in polynomial time:
http://hal.archives-ouvertes.fr/hal-00625917/en
If this is true, the consequences are known.
As far as I understand, you have an linear algorithm for max-clique but not sure about its correctness. Your method is to decompose the graph from the vertex of highest degree until
no vertices remains, then we re-build the graph computing the maximum clique at
each step, restoring each one of their vertices. In 1975 we have given an similar method by deleting serially minimum vertex degrees from G till to reach a max-clique. Unfortunately our algorithm on some graphs ends up with a r-regular graph. Therefore it would be better to look for an counter-example before to prove the theorem.
Could you please comment on Plotnikov’s recent work:
http://kafcsn.org.ua/lang/en-us/anatoly-d-plotnikov-professor-department-computer-systems-and-networks-east-ukrainian-national-university-solved-the-problem-p-vs-np.html
The paper itself:
thescipub.com/pdf/10.3844/jcssp.2012.1036.1040
Regards,
Borys Biletskyy
Absolutely super! Enjoying this BLOG … all so very interesting & current.
Here’s a great place too – if perhaps I missed reading about here. http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
Any comments on NP vs coNP? I mean the fairly obvious approach is to wonder about existence of poly-sized ‘extra’ information to confirm YES for some coNP-complete problem? Anyone know of active work in this area?
bi1bobaggins,
Great question. I seem to think most attempts are P=NP not the “weaker” NP=co-NP question. The main results are lower bounds on restricted logical systems that can prove tautologies. This results show that in these systems proving a SAT problem is unsatisfiable is hard. The trouble is they are weak systems.
Friends,
See the below given article on unstructured search. You may perhaps enjoy it.
http://vixra.org/pdf/1306.0193v1.pdf
DPM
Dear Friends,
Not only you can search from scrambled list but also you can sort it instantly!
Please have a look at: http://vixra.org/pdf/1306.0193v2.pdf
DPM
The Rutherford quote, as cute as it is, seems to be entirely apocryphal: https://en.wikipedia.org/wiki/Talk:Ernest_Rutherford#Odds_of_1012_to_1.
For those who truly are open minded:
I have my drastically revised version of my work on arxiv.org:
“The Collapse of the Polynomial Hierarchy: NP = P”, http://arxiv.org/abs/0812.1385.
It has become quite long– a total of 57 pages including the appendix.
If anybody has an interest in a Beamer slide presentation, I could email that too.
P = NP problem (proven)
P = NP, in the factorization of all odd number.
See: http://www.ijma.info Vol 6 (9) 2015
Thank you for creating a very attractive blog on math! Much more math deserves it to be in this format. A colleague explained me the Pontrjagin-van_Kampen theorem in harmonic analysis: it was on page around 700 in the second volume of a two volume ‘book’. In black letters hardly noticeable. But of extreme beauty. We need a better entrance to such pearls. Btw, how do I subscribe to your blog … (can’t see a button)?
For polynomial time algorithm for Isomorphism and TSP refer to
http://vixra.org/pdf/1512.0322v1.pdf
and
http://vixra.org/pdf/1304.0002v2.pdf
DPM
Kreisel’s argument to the Davis-Robinson(-Putnam?) approach was even stronger than what you stated: if successful (as it now is) it would prove that there is a universal Diophantine problem, one to which every Diophantine problem could be reduced; “and to number theorists this is very unnatural”.
Please note that the above referenced Isomorphism condition:
http://vixra.org/pdf/1512.0322v1.pdf
is applicable to strongly regular graphs. For other graphs it is not directly applicable and in that case one needs to arrange first the vertices in nonincreasing degree sequence and then label the vertices with labels {1, 2, …., p} and one need to apply transpositions among vertices with same degree for conclusively implying nonisomorphism when we cannot identify next edge labels without disturbing earlier identified edge labels.
DPM
Please refer for Isomorphism algorithm at:
http://vixra.org/pdf/1512.0322v2.pdf
Thanks,
DPM
Is P = NP at least Quantum Mechanically??
Refer to : https://www.researchgate.net/publication/305171576_On_New_Quantum_Search_Algorithms_and_Complexity_of_NP-Complete_problems
DPM
The problem of determining whether a given graph has a fixed-point-free automorphism is NP-complete. We show that it is solvable in polynomial time.
https://www.researchgate.net/publication/379892660_Detecting_whether_a_graph_has_a_fixed-point-free_automorphisms_is_in_polynomial_time