Update on Deolalikar’s Proof that P≠NP

I think this comment by Aaron Sterling is important:

"I’d like to respond to the tone of a couple anonymous comments.

It is almost irrelevant to me whether the proof, as currently written, is correct. (I expect there to be flaws, perhaps unfixable ones.) What excites me — and, I think, a lot of other people — is the attempt to join together descriptive complexity with statistical physics. The bridge between finite, discrete complexity, and hardness in the continuous world “has to exist,” and the “evidence” for this can be found in everything from the distribution of the primes to the computer simulation of chemical reactions. Despite this, over the last few years, I’ve gotten the impression that researchers in logic and physics tend to be put off by — even scared by — the notations and dialogues of each other. So when someone from “outside” says he’s found a way to connect the two areas, it’s intriguing.

I’ve certainly gained insight into areas I had no clue about whatsoever, until just a couple days ago. It seems to me this whole situation is only partly about trying to understand a proof. Perhaps the more important part is us trying to understand one another."

http://rjlipton.wordpress.com/2010/08/10/update-on-deolalika...

Wow, this was the first time I had some understanding about what's going on, Prof. Lipton's UTC example is just so intuitive. I don't know if this is the common way they use to introduce NP-completeness in CS classes, but it's very easy to understand. And his comment that "If you can show that a new proof can solve weaker questions, even questions that are known, that can be very confidence building." is an excellent glimpse into a mathematicians way of thinking. This is exactly the reason, they are not too fond of brute force proofs (like the Rubik, God's number = 20 proof announced earlier this wee.): it doesn't teach any new mathematical tricks.

However, what excites me even more than a possible proof to P!=NP is the new wiki and blog based open collaborative approach of researchers. Yes, we had instances of this before, but I think this is the first time such an approach is used to analyze a result of this magnitude, and in such short time. Compare and contrast with Wiles' and Perelman's proofs, where the discussions were all in some remote lecture halls and you just heard the final "yes" or "no" response to the proof.

As a layperson who only understands these concepts at a very high level, I'm still fascinated trying to follow along. Just the idea of the insane bodies of work being casually thrown around in these discussions is staggering.

I really like the idea of "proof by wiki" that the author mentions. It had some success with the polymath proof of the Hales-Jewett theorem a while back (https://www.hypios.com/thinking/2010/01/13/massively-collabo...). Along a similar vein, the french group of mathematitions who published together under the pseudonym N. Bourbaki laid down a huge amount of mathematics in the 1930s. Their work became the foundation for much of the rigorous mathematics of the last century.

Of course, no-one ends up with a famous theorem under their name as no one person can claim they proved the theorem. But from the point of view of the mathematics world, it seems like a great idea.

A useful summary update is provided by Terry Tao here: http://rjlipton.wordpress.com/2010/08/10/update-on-deolalika...

There is also an interesting comment on the utility of such discussion here: http://rjlipton.wordpress.com/2010/08/10/update-on-deolalika...

Finally, a general overview with many links can be obtained here: http://michaelnielsen.org/polymath1/index.php?title=Deolalik...

Reading about the wiki and the Group that has formed, it seems to me that things would go a lot smoother if Vinay Deolalikar simply spoke about what he's done. It would be a lot easier to convey the outline of what he's done and answer questions in that format.

Perhaps I'm missing something, but face to face communication will leave a lot fewer people guessing.

Note: I won't even pretend to understand that mathematical discussions, so it's likely that many already understand the gist. It doesn't sound like it though.

I find the intuitive ideas in the paper very stimulating, but they may be false. The paper use a concept "conditional independence" as a way to measure how information flow when applying an algorithm. Visually, you can think any step of your algorithm is a move in a certain graph. You can not visit all solutions, since there are a exponential number of them and they are not related. So is a lovely intuition, but maybe false. If if turns out to be true, I will devote more time to read the paper. In particular, I would like to believe that there exists such a visual representation of any algorithm, as a trajectory in a graph. The comments in that page are stimulating since they open many ideas to explore. Perhaps someone with a lot of time and energy can introduce the appropriate concepts, as we all know, first step seems easy but then all get very complex, so I imagine there is a lot of work for the author in the future.

If it's his work and he want's to remain silent, people shouldn't press much.

Asimov, in robot novels, hypothesizes that the longer life on Spacer worlds lead to less collaboration in scientific research since each researcher has enough time in hand to work on something in detail.

Vinay Deolalikar is 39 years old. Don't rush and give him time to set his own pace. At the end, I believe it was not his decision to release the draft paper to public.

edit: spelling