Skip to content

Conventional Wisdom and P=NP

images2

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 P=NP 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 P=NP may be at best guesswork and at worst just plain wrong. Most think that “obviously” P \neq NP, yet I am not so sure. I really think that the P=NP 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” P \neq NP. 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 10^{th}: 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 P=NP. 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

.

35 Comments leave one →
  1. February 28, 2009 8:13 pm

    Dick, see my point at http://en.wikipedia.org/wiki/P_%3D_NP_problem. Moshe

    • rjlipton permalink*
      March 1, 2009 8:30 am

      This is a very nice Wiki article. Please check it out for another view on P=NP.

    • Giorgio Camerani permalink
      February 3, 2011 3:33 pm

      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.”

  2. none permalink
    June 10, 2009 11:36 pm

    Let’s assume the CW is wrong and that P=NP. Where do you think that might put us in Impagliazzo’s “five worlds”?

  3. June 11, 2009 3:21 am

    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.

  4. john guilfoyle permalink
    July 25, 2009 8:36 pm

    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

    • Mogden permalink
      October 13, 2009 11:19 pm

      In this case P and NP are acronyms for “polynomial” and “non-polynomial”, not algebraic symbols. See the wikipedia article mentioned on this thread.

      • john guilfoyle permalink
        November 5, 2009 4:11 pm

        thanks, i read a novel by arthur c. clarke which wove this equation into the plot, thus my interest…

      • Daniel permalink
        November 6, 2009 5:58 am

        Ouch. NP does *not* mean “non-polynomial”, otherwise the question shouldn’t be too hard to answer, right? Hehe.

      • Cory permalink
        April 1, 2010 9:36 pm

        Indeed. That should read “non-deterministic polynomial”

  5. correct wisdom permalink
    August 13, 2009 2:04 pm

    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….

  6. May 19, 2010 10:57 am

    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”.

  7. August 13, 2010 5:43 am

    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.

  8. Miklos permalink
    December 30, 2010 6:44 pm

    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…

  9. leibnizengine permalink
    March 6, 2011 1:52 am

    Is P=NP mathematically true ?

    Please read my proofs:

    http://leibnizengine.wordpress.com/2011/02/23/p-np/

  10. July 28, 2011 9:22 am

    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.

  11. July 31, 2011 4:50 am

    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.

  12. October 13, 2011 4:06 pm

    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.

    • October 15, 2011 2:19 pm

      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.

  13. September 24, 2012 3:05 am

    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

  14. Stephen Gismondi permalink
    October 24, 2012 11:18 am

    Absolutely super! Enjoying this BLOG … all so very interesting & current.

  15. Stephen Gismondi permalink
    October 24, 2012 11:21 am

    Here’s a great place too – if perhaps I missed reading about here. http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

  16. bi1bobaggins permalink
    October 25, 2012 5:00 pm

    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?

    • rjlipton permalink*
      October 26, 2012 9:21 am

      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.

  17. DPM permalink
    June 25, 2013 6:58 am

    Friends,

    See the below given article on unstructured search. You may perhaps enjoy it.

    http://vixra.org/pdf/1306.0193v1.pdf

    DPM

  18. DPM permalink
    June 28, 2013 3:22 am

    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

Trackbacks

  1. Cook’s Class Contains Pi « Gödel’s Lost Letter and P=NP
  2. Kolata on Funding Research « Gödel’s Lost Letter and P=NP
  3. Surprises in Mathematics and Theory « Gödel’s Lost Letter and P=NP
  4. P=NP consequences « Constraints
  5. Giving Some Thanks Around the Globe « Gödel’s Lost Letter and P=NP
  6. P versus NP, universal machines and spherical matrices | Quantum Wittering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,244 other followers

%d bloggers like this: