Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] The Humbling Power of P v NP

Expand Messages
  • Lance
    [Note from Bill: He now has an on-line list of papers who still need reviewers] Noam Nisan, back in grad school in the 80 s made the following
    Message 1 of 1 , Oct 21, 2009
    • 0 Attachment
      [Note from Bill: He now has an on-line list of papers who still need reviewers]

      Noam Nisan, back in grad school in the 80's made the following suggestion:
      Everyone theorist should try to prove P = NP and P ≠ NP early in their career to understand why the problem is so difficult to solve.
      So go ahead and find a polynomial-time algorithm to 3-color graphs. Show that clique can't be solved by small circuits. Not because you will succeed but because you will fail. No matter what teeth you sink into P vs NP, the problem will bite back. Think you solved it. Even better. Not because you did but because when you truly understand why your proof has failed you will have achieved enlightenment.

      You will understand that computation is a nasty beast. Very hard to tame, to see what it can't do. Nearly as hard to control, to use it to solve those hard search problems.

      Watch Tim Gower's multiple personalities try to tackle even simpler lower bounds. The P v NP monster humbles the best of us. And that's what makes the P v NP problem exciting and us just human.



      --
      Posted By Lance to Computational Complexity at 10/21/2009 05:57:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.