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.
Posted by at
Labels:

2 comments:

  1. AnonymousAugust 16, 2010 at 1:51 PM

    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.

    ReplyDelete
  2. AnonymousAugust 16, 2010 at 2:18 PM

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

    http://webcache.googleusercontent.com/search?q=cache:86bd8ibzNjQJ:rjlipton.wordpress.com/+NP+%22Vinay+Deolalikar%22&cd=2&hl=en&ct=clnk&gl=us

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

    ReplyDelete

Subscribe to: Post Comments (Atom)