P != NP

Well, someone seems to have finally cracked it.

Vinay Deolalikar claims to have proved that P != NP.  Now, this doesn't quite have the applicational impact as if it turned out that P=NP, but it's a remarkable achievement.  I haven't given the paper a thorough read, and I suspect it'll take some external reading to really digest the guts of it.

Assuming the proof holds up, this is a big deal.

Sure this doesn't have anything to do with speech, or natural language processing.  However, somewhat surprisingly, the proof uses graphical models, statistics, conditional independence and graph ensembles.  So we've got some machine learning ideas being invited to the party.

And, like I said, it's a big deal, so who cares if it's on topic.