Wednesday, August 18, 2010

Complexity theory update

I was asked in comments about the claimed P != NP proof I posted about last week. This NYT article has a reasonable summary of current opinion. Basically the "proof" appears to have some serious problems. Unfortunately the author may have trouble accepting this verdict.

As for what a proof would mean, the bare fact alone would not change much since many people already assume it is true. However it is likely a valid proof would depend on much greater insight into the theory computation than we currently have.

1 comment:

  1. Hi James,

    I ended up using your proof of the bound on the number of little disks contained in the big disk. It was definitely the clearest and most straight-forward.

    What's your email address? I'll cite you as a personal communication, and send you a copy of the paper, if you're interested.

    Email me at heebie dot geebie at gmail.

    Thanks for the help!