Thursday, September 24, 2009

My two cents on P vs NP

There have been several posts on blogs about P vs NP and two expository articles. Is there anything else to add. I'm not sure, but here are my 2 cents.
  1. QUESTION: If it is shown that P &ne NP then how will this affect the real world? ANSWER: The solution will give great insight into computation and thus will ultimately help the real world of algorithms. QUESTION: How do you know this? ANSWER: Um...
  2. QUESTION: If you were told that P vs NP was REALLY SOLVED yesterday and asked to bet which way it went, how would you bet? I would bet P=NP. I actually believe that P&ne NP; however, my believe in the paucity of current techniques for showing P &ne NP is greater than my believe that P&ne NP.


  1. I love the first Question and its Answer.

  2. For Q2, if P vs NP was solved, and it was known to be solved then it must have been P≠NP; only a fool would tell people if they found P=NP.

  3. Golly ... the subtlety of argument (2) compels admiration ... it is an argument that I for one have *never* heard before.

  4. actually luigi finally resolved the problem.

  5. Second argument is incomplete. We also need to know how hard a proof for P=NP supposing P=NP was true.

  6. why would you be a fool to say you found P=NP?

  7. More "will P vs NP be solved" posts? This is getting a bit old ...

  8. " mario said...

    actually luigi finally resolved the problem."

    Someone proved that P=NP in 9 pages? Hmm...

    if anyone can be bothered reading through this, tell us how he made a mistake :P

  9. luigi made no mistake. the most profound comment in his proof of P=NP was "having spent over 2 years to achieve this there are no
    complicated ideas or sophisticated development will, if I'm right how can this result
    has been hidden for so long?"

    and i ask you, the reader, how could it have been deprived of us? finally, the long lasting conjecture (of all times) has been resolved.
    I think we should conclude all these posts by thanking the author for his breakthrough.

  10. Perhaps this has already been addressed somewhere else in the blog, but after reading comments like #4 and #9 above, it would be great if the blog author(s) could comment on the proliferation of so-called proofs for the P vs. NP problem.

    See, for example, the following webpage ( for a number of different "proofs" that P=NP, or P/=NP, or that P vs. NP is undecidable.

    Arguably most of this activity comes from individuals without very deep expertise in theoretical computer science and these proofs are very likely full of errors, but still, is anybody paying attention to this? Checking the proofs? Informing the masses (as well as the authors of these proofs)?

    What is the TCS experts' view of all this activity?

  11. luigi offers a new entry on the list of proof methods given on the site

    .. proof by wikipedia..

    seems to fall at some of the checks listed on

  12. There is one authentic solution to P vs NP as P = NP on this link.This paper was accepted and later retracted from ACM journal Elsevier.