I don't have much to say on this one yet, but it's too important to stay silent on. Someone is claiming to have proved that P ≠ NP, which wouldn't be new but for the fact that the claimant is actually a credible computer scientist, such that Stephen Cook is saying it may be a correct proof. Since not everyone here is a complexity-head, let me spell out the significance of that: Cook was one of the people behind the Cook-Levin Theorem, which established the existence of NP-complete problems. Without Cook, then, the P vs. NP problem would be much less relevant, so his opinion on the matter should carry no small amount of weight. Of course, this is a science, so that can't be the last word-- hence the question mark in the title. It'll be interesting to see what light the morning brings to this one.
Many others have written on the issue, including: R. J. Lipton, Dave Bacon and Joe Fitzsimmons.
No comments:
Post a Comment