Proof proposed for P != NP problem

[Ahknaton]

Paper:

http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

Background:

http://en.wikipedia.org/wiki/P_versus_NP_problem

Commentary:

http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
http://gregbaker.ca/blog/2010/08/07/p-n-np/

[Ahknaton]

Guess what? The singularity isn't going to happen.

[gooddeath]

Very interesting. My professor mentioned this during class today. I can't wait to read the paper myself. Unfortunately, computational complexity theory isn't my focus so much of it is probably over my head, but the P=NP problem does have many implications for cryptographic systems which depend on the complexity of solving a particular problem (like discrete logarithms) for their security.

[Delmac]

I imagine there will be some commentary at the FOM list about this, so I'll keep an eye out there..

[Macrobius]

If true, then it's a decision problem, and we can just Ask Jeeves:

http://www.ask.com/web?q=does+P+equal+NP%3F&search=&qsrc=0&o=10181&l=dir

Which seems a nice recursive way to answer the question....

UPDATED: And here is the must-read wiki on the topic:

http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper

[Ahknaton]

Mathematician blogger bets $200,000 that the proof is invalid:

http://scottaaronson.com/blog/?p=456

[Macrobius]

Mathematician blogger bets $200,000 that the proof is invalid:

http://scottaaronson.com/blog/?p=456

This could be a good chance for small European countries to solve their banking crisis, actually. In Polynomial time, too.

[Macrobius]

Nice 'tourists' guide to the paper, for non-mathematicians. The non-trivial use of phase transitions and stat mech is interesting.

http://www.ugcs.caltech.edu/~stansife/pnp.html

ADDED: I'm plowing through the paper now. A primary inspiration appears to be Statistical Mechanics, and especially the methods mentioned in

http://www.amazon.com/Information-Physics-Computation-Oxford-Graduate/dp/019857083X

I am citing Amazon instead of OUP because they let you browse the Table of Contents and see some text. It will set you back 100 USD or 2/3s that used. Browsing this book will give you a who's who of the proof, and a serious attempt should probably start with the textbook, not the paper that culminates it.

The proof makes critical use of Ising models on random graphs [and especially factor graph methods -- which are, by the way, the core of 'message passing algorithms']. These are becoming increasingly important methods these days.

Ising models / 'spin glasses' (and Potts models, which are a generalization of them) were mentioned in my 'How Magnets work' and 'Stochastic Calculus'. He mentions Percolation Theory in a couple places in the paper as well. I'm sure Renormalization Groups will show up as well, since 'universality' and critical phenomena are what this is about.

The satisfiability problem [how to minimize the number of gates in a logic circuit...] has been around since the 50s at least -- Quine and Putnam both had contributions in this area. It is related to Galois connections (this is how mathematicians conceptualise the essence/substance duality, or syntax/semantics, or quality/quantity) -- and fields on boolean lattices [2^N] for you math types.

For esoteric interest, he relies on the k-SAT problem [satisfiability with k variables], and especially k > 8 case. It is pretty amazing that you have to get that complex before you get the phase transition he's talking about. I'll hazard a wild conjecture that the magic number 8 will prove to do with the central charge in a Coulomb gas [itself related to CFT of anti-de Sitter space fame]. The connection of these to Quantum Gravity is discussed in the final link of the Stochastic Calculus article. Jes' Sayin'. You heard it here first.

I have no idea whether his proof will stand up at this point -- but the methods are intrinsically interesting for researchers and the paper stands in its own right as a review of the field. Factor graphs, markov methods, random field (and lattice) theory, and Gibbs Sampling methods are all becoming very important in computer science.

In fact, I would say the intersection of Statistical Mechanics, Information Theory, and what is left of Neural Nets (Machine Learning and Data Mining) is *the* place to be nowadays, for Applied Math -- like Chaos theory and fractals in the 80s. Personally, I just like to call it 'The Physics of the Internet' and leave it at that. Complex random lattice systems simply show a certain interesting dynamics that allows us to inspect 'quantum' phenomena in a mesoscale lab system.

[Macrobius]

Day 5 summary - and a hectic day it was.

Google docs apparently crumbled under the pressure of hosting the doc.

http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html

Probably every nerd in the Googleplex was trying to read it at once.

The underlying Statistical Physics got clarified by linking to a thesis:

http://arxiv.org/abs/0806.4112v1
http://arxiv.org/abs/0704.1269

The model theoretic objections may well stick at this point, but even if the proof fails, I would consider the airing of the Physics techniques to be useful and interesting. They will have much wider currency now, I think.

The Magisterium responsible for vetting the proof got cranky:

http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4918


I did not call the proof “trash” or any other demeaning name, and I have no disrespect for the author, although I am frustrated with his writing style. I am also
not telling anyone what they should or should not work on.
What I am most concerned with is how we distinguish between “serious” and “non-serious” attempts at famous theorems. The use of the criterion: “famous researchers are spending time on it” or some such leads to a snowball effect. As a researcher in complexity, I should be dropping everything in my life to consider a serious proof that P \neq NP. Is this such a proof? Because others are spending time on it, maybe it is. At least it would be better to waste my time on it than for them to waste theirs…But then we’re all wasting all of our time on (what seems likely to be) a dead end.


Looks like someone woke up in Pessiland (http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html) this morning. Cranky or not, he scores some points later in that post.

Serious discussion continues:

http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/

If it sticks, his announcement sentence will go down in history:


I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.


I hope he didn't mail the NP attachment from work.

Extension of the proof to include Zapf Dingbats at 24pts seems unlikely, except perhaps asymptotically.