[Previous entry: "Gazelle"] [Next entry: "Chrome"]

08/09/2010: "To P or not to P"

According to Vinay Deolalikar, a Principal Research Scientist at HP Labs: P != NP.

Our work shows that every polynomial time algorithm must fail to produce solutions to large enough problem instances of k-SAT in the d1RSB phase. This shows that polynomial time algorithms are not capable of solving NP-complete problems in their hard phases, and demonstrates the separation of P from NP.

Probably. If correct then this is Really Big News. The proof has not been peer-reviewed, but the consensus seems to be that this is a plausible approach, and definitely not a crank.