Sunday, August 8, 2010

Big news in complexity theory?

An HP researcher, Vinay_Deolalikar , is claiming to have proved that P != NP. This is of course a major result if correct. I would guess the odds are it isn't but an expert thinks it is worth taking seriously. I glanced through the preliminary version of the paper. It goes well beyond my superficial knowledge of complexity theory so I will defer to more expert opinion as to correctness. I expect this will be forthcoming fairly quickly.


  1. Thanks for this news. I know barely enough to understand that this is big news if true. Have you heard any more on this (he said lazily:-)?

    I also wonder whether the result per se (as opposed to any new techniques, linkages, etc. which may have been employed in its proof) would change much, given that everyone seems(?) to be assuming its truth already.

  2. I got a little un-lazy and checked out the update at

    which has enough nontechnical content to glean the general state of things even though I can't follow any of the math.