Claimed Proof That P != NP 457
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."
Re:Well, duh (Score:1, Interesting)
What would the impacts of this be for cryptography (Score:4, Interesting)
What would the impacts of this be for cryptography?
from a theoretical point of view at least?
I was under the impression that a lot of cryptography was based upon the hope that P!=NP and while in practice this wouldn't change much about anyone acts it might have an impact on how people think about the old cryptology vs cryptanalysis race.
Re:What would the impacts of this be for cryptogra (Score:5, Interesting)
Not Only Time But Several Disciplines (Score:5, Interesting)
At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.
You can read section one (the introduction) and get a high level walk through of what he's doing. Just be prepared to have a requisite in the following to make it through that:
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.
My computer science, math and statistics are still fairly sharp but the physics and graph theory are a bit much. Indeed this will take a while to digest. If he hasn't made a mistake in something like bridging together least fixed point logic and functions [wikipedia.org] with Markov-Gibbs properties (correspondence and equivalence) [ia.ac.cn].
On the one hand it seems this will take a general expert in the math related sciences to verify but on the other you would think that -- like with the E8 and Lie groups -- this sort of proof would require a rather large unified theory to be able to reduce the N=NP? problem down to a provable situation. I'm no expert and it's been three or four years since I've even been in academia but even the subsections of this paper are noteworthy if they are true. It could be we're looking at something that jumps so far ahead like the famous papers of Turing and Shannon.
Re:What would the impacts of this be for cryptogra (Score:4, Interesting)
Practically, not much. It means we can breathe easy that a lot of crypto out there is now provably secure. It's been long considered likely that P != NP, because a lot of NP-complete problems are very old and nobody has gotten very far in solving them, and the extra focus in the last 40 years in breaking public key crypto hasn't produced much more progress on the problem. It was just the nagging issue of nailing down a proof.
A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku. The contrary proof doesn't have many huge implications, though.
Re:What would the impacts of this be for cryptogra (Score:1, Interesting)
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure.
Wrong.
1. Polynomials can sill be really big. n^100000000 is in P, but an O(n^100000000) algorithm would not be practical.
2. There are complexity classes above NP which are provably not equivalent to P.
Re:What would the impacts of this be for cryptogra (Score:3, Interesting)
If I were a cryptographer, I'd be positively itching for someone to break RSA. A 30 year old univerally-used secure cryptosystem means no job. :)
In a world where no crypto is really secure, everyone hires their own cryptographer to build a custom cryptosystem. Let's see Bletchley Park mathematicians try to cleverly crack gigabytes of junk encrypted data when the keys wouldn't fit in all the notebooks required to fill their entire building floor to ceiling.
Pictures .... or it didn't happen (Score:2, Interesting)
Pictures, er, I mean, peer review, or it didn't happen.
Not in arXiv? (Score:5, Interesting)
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.
Re:What would the impacts of this be for cryptogra (Score:4, Interesting)
Proof by example? (Score:2, Interesting)
I recall reading that Minesweeper was an NP complete, or at least NP Hard problem. Doesn't P mean that a solution is computable is a reasonable time? If that's the case, then P!=NP by minesweeper.
Imagine you're almost done with a game of Minesweeper. 5 mines left. Your grid looks like this:
+----
| * * 2
| * * 3
| * * 2
| 2 2 1
Now, obviously each of the blocks on the outside, four of them, are mines. Which leaves two that you have no information about and can't _GET_ any information about. Which of the remaining two blocks is a mine?...
Would this be an example of P != NP, assuming Minesweeper is NP?
Re:Not Only Time But Several Disciplines (Score:5, Interesting)
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.
Re:Not in arXiv? (Score:5, Interesting)
Re:Well, duh (Score:5, Interesting)
If "non-deterministic polynomial time" is an actual "algorithmic complexity class' then so is my "anomalous quantum field" which generally intersects with a "temporal phase disturbance."
So apparently if something sounds technical and you don't know what it is you assume it is nonsense? Non-deterministic polynomial time http://en.wikipedia.org/wiki/NP_(complexity) [wikipedia.org] is a concept is theoretical computer science. The idea is that a set of problems is in NP if when there is a "yes" answer to an example there is a short proof of the answer (where short means the length of the proof and checking its validity is bounded by a polynomial function of the length of the input). For example, the problem "is a given integer n composite?" is in NP because if the answer is yes, one can prove this quickly by simply giving a non-trivial divisor. The other relevant class is P, which are the set of problems which can be answered within time bounded by a polynomial function of the input. One of the great unsolved mathematical problems of our time is whether P equals NP. Roughly speaking, the question asks whether there exist problems which are hard to solve but where solutions can be checked quickly.
Re:What would the impacts of this be for cryptogra (Score:5, Interesting)
Re:Wouldn't P=NP be a paradox anyway? (Score:5, Interesting)
I think you are misunderstanding what the P=NP question means... and I don't blame you. The question itself is very "meta", but it is not self-referencing as you believe.
P is a set of questions (YES/NO questions) that can be answered easily. NP is another set of questions, that may or may not be easy to answer, but when you see the answer (YES/NO) and a proof for the answer, you can easily check if the proof is correct. But the question "P=NP?" doesn't belong to either of the sets. If P=NP, then all problems that are easily "verifiable" are also easily "solvable", and if P!=NP, then there are problems easily verifiable but hard to solve. But, as the question "P=NP?" doesn't belong to P or NP, there is no paradox.
That's an over simplification, of course. For instance, "easy" in the previous paragraph actually means "solvable in polynomial time by a deterministic turing machine", and "not easy" would be "solvable in polynomial time by a non-deterministic turing machine", and there is the widespread confusion about "NP" meaning "Non-P" instead of "P in a Non-deterministic machine". The wikipedia article is really good, but unfortunately, much too formal to understand without previous knowledge. I hope I helped a bit.
Re:this is going to create history (Score:4, Interesting)
On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.
The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.
NP != P, but BL P (Score:3, Interesting)
Indeed, N)on-P)eer-reviewed does not equal P)eer reviewed.
But B)eautifully L)aTeXed trounces peer review.
Re:What would the impacts of this be for cryptogra (Score:3, Interesting)
Currently the best factoring algorithm is GNFS, which can factor in exp( ( n * log^2(n) )^(1/3) ). However, that's still exponential because it's greater than exp(n^(1/3)).
The paper claims a deterministic time lower bound for the hardest problems in NP^CoNP at exp( log^k(n) ). I'm sure this paper will spur research into algorithms with expected runtime of exp ( log^k(n) ), and that should quickly give us a faster factoring algorithm.
On a personal note: I developed a SAT algorithm in 2005, and my rudimentary analysis showed that it requires at least exp( log^2(n) ) for NP^CoNP. I never bothered to compute the upper bound because I gave up on it once I realized I couldn't use it to prove a lower bound for NP. However, I may have to dust off the algorithm and solve the upper. This paper gives me hope that it's exp( log^k(n) ), which would give a better result for factoring than GNFS. :-)
MIT prof has strong hunch proof is invalid (Score:4, Interesting)
"I’m dead serious—and I can afford it about as well as you’d think I can." See his blog [scottaaronson.com].
Is this a real paper? (Score:2, Interesting)
Scott Aaronson listed ten signs a mathematical breakthrough is wrong [scottaaronson.com].
The very first sign is whether the authors used the standard technology for scientific publication (TeX/LaTeX). This paper appears to be written in MS freakin' Word. I'm not saying it is impossible for a genius mathematician to be a publication newbie, but consider what is more likely:
1. Someone with no experience in scientific publication independently discovered a proof sought after for decades, which some have conjectured to be not even provable.
2. Somewhere in those hundred pages is an incorrect generalization, a hidden assumption, circular reasoning or one of dozens of other pitfalls a budding computer scientist or mathematician falls into while attempting a complex proof.
Scott Aaronson unfortunately hasn't found the time yet to examine the paper closely, but he does bet 200k against its correctness [scottaaronson.com].
Re:Well, duh (Score:3, Interesting)
However, it seems you could read that page, and still have not a single useable clue.
I have no idea why people say maths is a strong point of Wikipedia. There is no topic whatever on which I have received enlightenment by reading of a Wikipedia page. Indeed, even when it's a result I just want to look for, I can be sure that Wikipedia's going to go off on some tangent about a minor topic some guy's just learnt about in class and felt the need to mention, while the description of the result itself misses out some fundamental assumptions or uses ambiguous language. And, when I'm confronted with a surprisingly succinct paragraph or two, I usually find it's a rewording almost sentence by sentence of another reference. I've got a lot more out of the far more terse but precise Weisstein's Mathworld.
From reading pages (including discussion) where I already understand the topic, it's clear to me that some people sorta understand what's going on and a few have knowledge which far exceeds mine. But it's impossible for a community of 100 contributing primates, maybe a dozen of them sufficiently knowledgeable and two of them also good educators, to produce a well-written summary of any topic. Trying to end up with an article at the readability level of a centrally edited reference with limited, expert authors is engaging in a war of attrition.
Today I'm at the point where, if anyone shows the slightest hint of using information from Wikipedia, I'll immediately send them away and ask them to come back with another reference as basis. While people are beyond the point of actually citing Wikipedia, the problem still exists of people using its convoluted half-truths as a basis for serious discussion.
Potential pitfalls in the Finite Model Theory bits (Score:5, Interesting)
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).
Re:Well, duh (Score:2, Interesting)
I like to mod funny comments underratted for this exact reason. Unless it's just a one-liner, then it's just +1 funny... I figure a joke that took some real thought and composition deserves karma points.
Gets them a +1 and doesn't dilute the funny mod. I tried an insightful on a +4 funny once and it switched to +5 insightful.
Sam