typodupeerror

## Claimed Proof That P != NP457

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."
This discussion has been archived. No new comments can be posted.

## Claimed Proof That P != NP

• #### Re:Well, duh (Score:1, Interesting)

on Sunday August 08, 2010 @05:37PM (#33183750)
Well, perhaps N=H=1?
• #### What would the impacts of this be for cryptography (Score:4, Interesting)

on Sunday August 08, 2010 @05:40PM (#33183770)

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)

on Sunday August 08, 2010 @05:46PM (#33183820)
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify. So, if the paper is true, then it doesn't really change a whole lot, except that now we know that some day there isn't going to be a trivial solution. I guess its good for cryptography.
• #### Not Only Time But Several Disciplines (Score:5, Interesting)

<eldavojohn.gmail@com> on Sunday August 08, 2010 @05:49PM (#33183838) Journal

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)

<hardburn@NoSPAm.wumpus-cave.net> on Sunday August 08, 2010 @05:54PM (#33183876)

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)

by Anonymous Coward on Sunday August 08, 2010 @06:08PM (#33183960)

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)

on Sunday August 08, 2010 @06:14PM (#33184002) Homepage

A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku.

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)

on Sunday August 08, 2010 @06:22PM (#33184054) Homepage Journal

Pictures, er, I mean, peer review, or it didn't happen.

• #### Not in arXiv? (Score:5, Interesting)

on Sunday August 08, 2010 @06:37PM (#33184154)

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)

<michael.maraistN ... .com ['gma' in g> on Sunday August 08, 2010 @06:40PM (#33184176) Homepage
Don't think this is what it means. Look at FFT (logarithmic optimization to a quadratic problem). P = NP as I understand it means that ALL NP problems have a corresponding P solution. You just have to think hard enough to find it. Proving that there are classes of NP that have no P just suggests certain crytographic algorithms MIGHT be NP. But it doesn't prove it (unless it was one of the particularly proven NP classes in this or some other paper). And even if this paper includes RSA / ECC, etc. That doesn't mean someone even more clever 30 years from now finds a flaw or special case where this isn't true and thus finds a P cracking tool.
• #### Proof by example? (Score:2, Interesting)

by Anonymous Coward on Sunday August 08, 2010 @06:43PM (#33184188)

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)

by Anonymous Coward on Sunday August 08, 2010 @06:55PM (#33184298)

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)

on Sunday August 08, 2010 @07:04PM (#33184372)
well, he also treats replica symmetry breaking in relation to the kSAT problem (in the hamiltonian fomulation is really just Ising on a random graph) so I would say he knows his shit... If there is a mistake surely is not a trivial one.
• #### Re:Well, duh (Score:5, Interesting)

on Sunday August 08, 2010 @07:43PM (#33184608) Homepage

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)

on Sunday August 08, 2010 @09:04PM (#33185054)
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.
• #### Re:Wouldn't P=NP be a paradox anyway? (Score:5, Interesting)

on Sunday August 08, 2010 @10:34PM (#33185532)

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 Sunday August 08, 2010 @11:09PM (#33185682)
IMO, The P vs NP is fundamentally more tricky than other famous theorems/conjectures (like FLT), because on some level it is a statement about mathematics itself. The assumption that P != NP on some level implies that the finding mathematical proofs is difficult. This means that if P!=NP it may be even more difficult to prove that P!=NP. It has been shown that assuming one-way functions exist (this would imply P!=NP easily enough) that a certain type of proof called "natural proofs" can never be used to separate P from NP.

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)

on Monday August 09, 2010 @12:03AM (#33185888) Homepage

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)

by Anonymous Coward on Monday August 09, 2010 @02:03AM (#33186320)

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)

on Monday August 09, 2010 @03:02AM (#33186490)
Well, Scott Aaronson has written: "If Vinay Deolalikar is awarded the \$1,000,000 Clay Millennium Prize for his proof of PNP, then I, Scott Aaronson, will personally supplement his prize by the amount of \$200,000.

"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)

<arancaytar.ilyaran@gmail.com> on Monday August 09, 2010 @04:09AM (#33186710) Homepage

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)

on Monday August 09, 2010 @05:47AM (#33187010) Journal

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)

on Monday August 09, 2010 @06:35AM (#33187114)

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:

1. 1. The logic LFP(FO) only captures P on ordered structures; that is structures that have a built in total ordering relation.
2. 2. Any sentence that describes a problem in LFP(FO) must be order-invariant ; that is it must work for any possible ordering of the vertices in the underlying graph/structure.

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)

on Monday August 09, 2010 @12:11PM (#33191288)

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

Arithmetic is being able to count up to twenty without taking off your shoes. -- Mickey Mouse

Working...