[FOM] purported proof that P != NP

[Martin Davis]

Ravi  Sarma has called my attention to the 
following 102 page article by Vinay Deolakikar of 
HP Labs that claims to prove that P is not equal to NP.
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

Of course I have no idea whether the proof is 
correct. Below in full is the abstract from the article.

                         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.
Next we introduce ideas from the 1RSB replica symmetry breaking ansatz
of statistical physics. We recollect the 
description of the d1RSB clustered phase
for random k-SAT that arises when the clause density is sufficiently high. In
this phase, an arbitrarily large fraction of all 
variables in cores freeze within
exponentially many clusters in the thermodynamic 
limit, as the clause density is
increased towards the SAT-unSAT threshold for large enough k. The Hamming
distance between a solution that lies in one 
cluster and that in another is O(n).
Next, we encode k-SAT formulae as structures on which FO(LFP) captures
polynomial time. By asking FO(LFP) to extend partial assignments on ensembles
of random k-SAT, we build distributions of solutions. We then construct a
dynamic graphical model on a product space that captures all the information
flows through the various stages of a LFP computation on ensembles of k-SAT
structures. Distributions computed by LFP must satisfy this model. This model
is directed, which allows us to compute factorizations locally and parameterize
using Gibbs potentials on cliques. We then use results from ensembles of factor
graphs of random k-SAT to bound the various information flows in this directed
graphical model. We parametrize the resulting distributions in a manner
that demonstrates that irreducible interactions between covariates — namely,
those that may not be factored any further through conditional independencies
— cannot grow faster than poly(log n) in the LFP computed distributions. This
characterization allows us to analyze the 
behavior of the entire class of polynomial
time algorithms on ensembles simultaneously.
Using the aforementioned limitations of LFP, we demonstrate that a purported
polynomial time solution to k-SAT would result in solution space that
is a mixture of distributions each having an 
exponentially smaller parametrization
than is consistent with the highly constrained d1RSB phases of k-SAT. We
show that this would contradict the behavior exhibited by the solution space in
the d1RSB phase. This corresponds to the intuitive picture provided by physics
about the emergence of extensive (meaning O(n)) long-range correlations between
variables in this phase and also explains the empirical observation that
all known polynomial time algorithms break down in this phase.
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.