Vinay Deolalikar
P != NP at last?
Whether P (class of problems solvable in polynomial time) is not equal NP (class of problems solvable by a non-deterministic Turing machine in Polynomial time) is probably the most important problem in theoretical computer science, and is among Clay Mathematics Institute Millennium Prize Problems with a million dollar prize. (Wikipedia: P versus NP problem).
Vinay Deolalikar is a Principal Research Scientist at HP Labs who has done important research in various areas of networks. He also has worked on complexity theory, including previous work on infinite versions of the P=NP question. He has just claimed that he has a proof that P is not equal to NP, by using an approach which combines ideas from logic, statistics, graphical models, random ensembles, and statistical physics.
ABSTRACT
We demonstrate the separation of the complexity class NP from its subclass P. Throughout our proof, we observe that the ability to compute a property on structures in polynomial time is intimately related to the statistical notions of conditional independence and sufficient statistics. The presence of conditional independencies manifests in the form of economical parametrizations of the joint distribution of covariates. In order to apply this analysis to the space of solutions of random constraint satisfaction problems, we utilize and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.We begin by introducing the requisite framework of graphical models for a set of interacting variables. We focus on the correspondence between Markov and Gibbs properties for directed and undirected models as reflected in the factorization of their joint distribution, and the number of independent parameters required to specify the distribution.
Next, we build the central contribution of this work. We show that there are fundamental conceptual relationships between polynomial time computation, which is completely captured by the logic FO(LFP) on some classes of structures, and certain directed Markov properties stated in terms of conditional independence and sufficient statistics. In order to demonstrate these relationships, we view a LFP computation as "factoring through" several stages of first order computations, and then utilize the limitations of first order logic. Specifically, we exploit the limitation that first order logic can only express properties in terms of a bounded number of local neighborhoods of the underlying structure.
...
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.
Here is Vinay Deolalikar preliminary paper on P != NP (100+ pages).
A serious discussion of the proof is on R. J Lipton blog.