Tuesday, August 10, 2010

P != NP

A researcher at HP Labs claims to have proven that P is not equal to NP. If that doesn't make sense, see this explanation from MIT News.

It looks like a credible candidate for a proof because, as Greg notes, Stephen Cook, a Turing award winner and the first person to pose the problem, considers it "serious."

I always thought this was the most interesting Millennium Prize Problem, maybe because it involves theoretical CS, but also because it's the only problem I understand enough to explain to someone else, sort of.

No comments:

Post a Comment