Hacker News new | past | comments | ask | show | jobs | submit login
Update on Deolalikar’s Proof that P≠NP (rjlipton.wordpress.com)
95 points by RiderOfGiraffes on Aug 11, 2010 | hide | past | favorite | 19 comments



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...


The trolling on that page is disturbing, some of those peeps may be math experts but also lacking self-awareness of their inner caveman. Makes me glad for the type of infighting we have in the software development community. Seems relatively constructive.


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.


Yeah I feel the same, it feels like being included in some real research review process for the first time. It's hard to see how academia works even working for a University(Which I do).


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.


Just as a pedantipoint, there were several Bourbaki groups, their work started in the mid 30s and extended significantly beyond that.

http://planetmath.org/encyclopedia/NicolasBourbaki.html


I didn't know that there was more than one group, thanks. I knew that the contributors changed over time but not that there where several groups.

Either way, their work has been very useful.


"Pedantipoint" sounds like a delicious software parody of Microsoft!


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...


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.


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 guess that this might be a little like Andrew Wiles' Fermat's Last Theorem proof where only a very small group of mathematicians were capable of understanding the whole thing and of verifying its correctness. If that's the case then those who are capable probably don't need much from Deolalikar in way of explanation, they'll be able to read through the whole thing and understand what he's doing, it'll just take time to carefully decide whether each individual step he's making is valid.

That's just my guess of course, I know no more about this than anyone else so maybe the proof is particularly esoteric and it won't be obvious to even experts what he's trying to do.


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


To the public at large, no. But he distributed it to respected CS theorists for exactly this kind of feedback.


s/hypnotizes/hypothesizes/

I'd be interested in a reference for that, as I don't off-hand recall it.


Excuse my English. Wrote wrong and let firefox correct it without giving much attention to the suggestion. Sorry.

From The Robots of Dawn:

"If you died, then, the new science dies with you?"

"I am only a hundred and sixty-five years old. That's metric years, of course, so it is only a hundred and twenty-four of your Earth years, more or less. I am still quite young by Auroran standards and there is no medical reason why my life should be considered even half over. It is not entirely unusual to reach an age of four hundred years--metric years. There is yet plenty of time to teach."

...

"Some of our scientists had accomplished quite a deal in considerably less time."

"Because they have taken advantage of the findings others have made before them and profit from the use they can make of contemporary findings by others. Isn't that so?"

...

"Is not this the case on Aurora and the other Spacer worlds, too?" asked Baley.

"In theory it is; in practice not so much. The pressures in a long-lived society are less. Scientists here have three or three and a half centuries to devote to a problem, so that the thought arises that significant progress may be made in that time by a solitary worker, It becomes possible to feel a kind of intellectual greed--to want to accomplish something on your own, to assume a property right to a particular facet of progress, to be wiling to see the general advance slowed--rather than give up what you conceive to be yours alone. And the general advance is slowed on Spacer worlds as a result, to the point where it is difficult to outpace the work done on Earth, despite our enormous advantages."


No need to apologise - I'm always somewhat humbled by just how well some people speak English as a non-native language.

<snip excerpt>

Ah - I don't have "Robots of Dawn" and it's a long time since I read it. Thank you.


It's strange how I read that as `hypothesizes` first time through, without noticing that it said something completely different...




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: