Slashdot Mirror
Claimed Proof That P != NP
morsch writes "Researcher Vinay Deolalikar from HP Labs claims proof that P != NP. The 100-page paper has apparently not been peer-reviewed yet, so feel free to dig in and find some flaws. However, the attempt seems to be quite genuine, and Deolalikar has published papers in the same field in the past. So this may be the real thing. Given that $1M from the Millennium Prize is involved, it will certainly get enough scrutiny. Greg Baker broke the story on his blog, including the email Deolalikar sent around."
I think this is the first time a serious researcher publishes a paper through email. Makes me wonder if he is actually publishing it or just asking for peer-review from his colleagues.
Or maybe he is trying to best Perelman in insanity. After all, even Perelman put the paper in arXiv.
Anyway, about the paper itself; I am a physicist, and he does say correct things about the Ising model and phase transitions. Unfortunately, it is only a small part of his proof that I can grasp. So I think he is dead serious.
Also, nice typography.
entropy happens
when I took a graduate level computer science course on randomized algorithms, our professor put up an 8-10 page proof for a randomized algorithm to solve graph coloring problems. near the end of the proof I raised my hand and noted that my professor had made a mistake transcribing a factor, as he had left out one of the paths in a markov chain. after checking the proof my professor realized that in fact the thesis he was using as an example was incorrect. Since that moment, I havent trusted complex mathematical proofs over 15 pages that havent been around for a large number of years. ... I suppose I should come up with some formula for a trustworthiness factor based on length and duration of time it has held up to scrutiny, but my point being, very very few people are qualified to write or debunk this paper, but everybody should be trying to.
Even if P=NP, polynomial solutions requiring time n^99 consume enough time to be practically infeasible. Thus, even P=NP would not harm cryptography much, if it did not provide very efficient solutions for every NP-hard problem. On the other hand, favorite cryptographic hard problems, such as factoring, are not known to be NP-hard and may well turn out to be solvable in polynomial time, even if P!=NP. Therefore, proof that P!=NP won't have any interesting implications for cryptography unless it contains new ideas that can help in other ways. Neither will proof P=NP unless it includes ideas for fast solutions of interesting problems, such as fast factoring or fast discrete logarithm. Proof of P!=NP may help to solve another interesting problem in cryptography: one-way functions. Right now many results are built on the assumption that such functions exist, but nobody have found a single provable one-way function (easy to compute, infeasible to reverse). A bunch of functions are believed to have this property, but not a single one has been proved difficult to reverse. I would be interested to see if this proof will produce such an animal - a provably one-way function.
Being a researcher in Finite Model Theory (FMT) this paper is very interesting because it uses ideas from that area, i.e. the LFP(FO) bits. Reading through the proof synopsis and scanning the FMT sections there are several potential pitfalls:
It is already known that LFP(FO) on unordered structures is a proper subset of LFP(FO) on order structures, so if the ordering and order-invariant requirements for LFP(FO) = P are not dealt with in the proof, then all the author has done is proof that LFP(FO) on unordered structures is a proper subset of NP. Which is already known.
Another potential problem is in the arguing that all first-order properties are local (Hanf's Theorem) in the presence of ordering, as every vertex is effectively connected to every other vertex (Immerman's proof of LFP(FO) = P requires total ordering of the underlying graph/structure), and hence every vertex is in the radius = 1 neighbourhood of every other vertex.
The crucial step in the proof, appears to be the argument that no LFP(FO) formula can extend a partial solution to k-SAT to a full solution to k-SAT. This is where I'd check the logical steps of the proof, and also make sure that the ordered nature of LFP(FO) structures is correctly considered.
I look forward to seeing this published in a peer-reviewed mathematics journal: I'd recommend to the author the "Journal of the ACM" for this (as it's one of the best journals in the field).