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 mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.
I was right on the edge of solving it myself.
Not :-)
Your god may be dead, but mine aren't!
I was a afraid he might have left out an important step.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
this is going to create history
For values of N where N != 1
Reviewing just the first hour of video games.
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.
Momento Mori
As far as I know, this is the first very public proof attempt- its likely it will have flaws, but it may pave the way for someone else or further attempts from the same source even if flaws are found.
OH YEAH!!!!!
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
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.
P != NP because it has an N there.
Well, wait, N could be 0 and P could still be zero, so in essence i made nothing from something.
Be right back, building a blackhole machine
It will be awhile before his proof is confirmed but I was hoping that P=NP
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
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.
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
"Deolalikar's result is that "P (does not equal) NP (intersect) co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)"
From http://en.wikipedia.org/wiki/Talk:P_versus_NP_problem#Potential_Solution
While I'll wait until it's gone through peer review, I'm sure this means that news outlets will pick this up and misreport it... it's good PR for HP's research group either way!
Global symbol "$deity" requires explicit package name at line 2. - If only $scripture started "use strict;"
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 with Markov-Gibbs properties (correspondence and equivalence).
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.
My work here is dung.
Of course they're not equal. It is revealed in Futurama episode 2-07.
The C&D letter is in the mail, buster. -Kool-Aid Man
The next time someone at work asks me to do something my response will be "I can't. That's NP."
Short form:if P=NP, crypto is something of a futile effort - that implies that there's a non-brute-force crack to every possible private-key algorythm. I suppose it might still be slow enough for the crypto to be useful, but I woudl expect you would end up needing gigantic keys.
Most everybody assumed that P!=NP, but nobody has been able to prove it.
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.
Not a typewriter
But I thought that was how transistors work!
Is my computer now broken because of this guy?
Showing that P=NP or showing the opposite has none of the practical consequences for anything that are often touted. It matters not in practice if there is some polynomial time algorithm that solves a problem - what matters in practice is only how quickly you can actually solve the problem on a computer. Polynomial time does not mean fast, it does not mean slow. It does correlate weakly with "fast" for many problems of interest, but that is all it does - it does not tell you if an algorithm is fast or not. Even if P=NP there is still the possibility that all polynomial time algorithms that prove this are so slow as to be irrelevant, and even if NP does not equal P, there is still the possibility that there are fast non-polynomial algorithms that solve any problem humans care about in an acceptable time. Thus NP=P is a theoretical question only - and a very important one at that. The completely separate question of solving the interesting NP-complete problems quickly in practice is the problem that actually does have all the consequences that are routinely misattributed to the theoretical P=NP question.
It means we can breathe easy that a lot of crypto out there is now provably secure.
Wrong. It doesn't prove that there is no faster factoring algorithm.
Another good sf story ruined. I was kinda looking forward to the aftereffects of a "P = NP" proof... it's been a dull Sunday.
My analysis said DH would hold even if P=NP.
I had a lower bound on the order of the polynomial for breaking DH and it was something like 256. There's really not much practical difference between n256n for n = 4096. Both are practically intractable.
No. Even if there are found to be integer factorization algorithms theoretically in P, there's still no practical way to crack it. This is all asymptotic complexity (what happens as your key size goes to infinity), which might be important when we start using tebibit symmetric keys, but in the real world the constant coefficients (which are thrown away in asymptotic analysis) would be really high.
Elliptic curve crypto is different though, I think.
If this has appeared somewhere in the other comments, sorry for missing it, but http://xkcd.com/664/ seems oh so appropriate here. (especially the alt text)
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.
I meant asymmetric, which is what RSA is. Symmetric keys are usually exchanged relying on the discrete logarithm problem (RSA problem), not the integer factorization problem.
Doesn't P != NP simply mean that there exist crypto algorithms that are secure, but not necessarily that a particular one is secure?
Well, just because something is in "P" doesn't mean it's trivial. For instance, if you discovered a prime number factorization algorithm that was O(b^100) it would not be useful for an RSA attack.
Also, it's not even known that factoring primes is NP-complete, co-NP, or even P. It's known to be P in a quantum computer (O(b^3), to be precise) and *suspected* to be not P in a Turing machine, but I don't think anyone has proven that.
Now I know you said "in principle, mathematically solvable".. but by that standard RSA is already solvable. It just isn't known to be solvable quickly. P=NP would not change that.
But all of this is moot since the alleged proof is that P!=NP which is what almost everybody assumed already. So the practical impact of this proof would be minimal, but it still would be a milestone in mathematics. At this stage I'd recommend caution though, there have been many "proofs" for P=NP and P!=NP over the years. This one has a pretty decent pedigree, but it's still very early in the review process. It's very possible that a subtle flaw will be found.
I don't know what kind of system scribd is trying to be, but it doesn't work with my browser, and I suspect it isn't the original / most direct link to the paper's preprint / public form. Isn't there just a simple direct PS / PDF / DVI / whatever link so one doesn't have to deal with scribd's brokenness (for me anyway)?
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.
Yeah baby, we can now create an efficient way to break AES256 and decrypt the Wikileaks "insurance" file!
So on about the same day CEO Mark Hurd collected a $53 million severance package from HP's board for either sexually harassing a contractor, or keeping said contractor as a mistress on an HP expense account, HP researcher Deolalikar submitted a paper which might earn him $1 million for proving one of the seven biggest unsolved problems in all of mathematics?
And it's bad for the rest of us the mere mortals who is sweating optimizing some mundane algorithms to allow them run on slow but power-efficient ARMs of today.
Pictures, er, I mean, peer review, or it didn't happen.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
Say this proof is correct, what are the implications and what is the next big problem?
I hope this brings closure to Computer Scientists. But you folks do realize that if P != NP then there is a God, If P = NP then there isn't. In other words, you can't have infinite "free efficiency". If you can do an infinitely complex task in reasonably efficient time then you can hack reality and get to God. God made P != NP so that we're locked in our own universe.
random k-SAT ensembles chosen have a flaw related to k,a factor graph ensemble. the paper is based on a statistical physics model which may also have probs but im unfamiliar with stat phy theory. -37028
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
repeat last 3 lines as many times as you like.
Net result: post is +5 funny but you take major karma hits.
Disclaimer: This was true in the early days of funny = no karma boost. They may have fixed it by now. Personally, I think karma should not contribute to karma except to offset overrated or some similar rating designed to indicate "not as funny as it's currently rated."
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
I thought it was:
P / [ N^(-x) * N^(x)] = P
Tim R.
Say who/wha/where? We are da linuxers, we don no no maths!!
Large integer factorization has not been shown to exist in NP-Complete (it is doubtful it does), it is know to exist in both NP and co-NP, it could exist in P (but it is doubtful) we just don't know. RSA public key crypto depends on the difficulty of factoring very large numbers. Currently there is no known efficient mechanism for determining the factors of a very large number. If P != NP we don't get a whole lot more than we have at the moment because we don't know exactly what complexity class integer factorization lives in. If P == NP then we have a serious problem because that requires there to be an efficient integer factorization algorithm. It is interesting that if P != NP we could very well end up in a situation where there are problems that have no efficient solution (not in P) but are not in the class NP-Complete (the "hardest" of the problems in NP). Integer factorization could very likely fall within this area.
Yeah, in some ways it seems disappointing. But at least everything isn't broken! XD
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
I thought RSA might still be P even if P!=NP because we don't know if integer factorization is NP complete.
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
No, that's wrong.
P, NP and NP-hardness are properties of *classes* of problems, and they say something on how fast (or slowly) the problems in the class get harder as size of the problem increases.
If a class is NP-hard and NP != P then this class is not P, yes. But it may still be easy for any instance under a billion bits, which would make it easy for practical purposes.
So even if ECC is NP-complete (NP and NP-hard, and I'm really not sure if we know that this is the case), and even if TFA is Tantalizingly Fucking Accurate, this alone doesn't prove the security of any specific system. Although, in practice, in the case of ECC, I'm sure you can count on it.
As for RSA, it's not known to be NP-hard, but again this doesn't rule it out as practically a very secure system.
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.
I think it's important to realize that even if they are "unresolved problems" of mathematics, it's not like both answers are equally likely like the flip of a coin. For example the Riemann hypothesis states that all non-trivial zeros of the Riemann zeta function have real part 1/2. It's true for every non-trivial zero we've ever found, but it's not proven true for all the infinitely many zeros. However, outside of mathematics a proof it's true will be met with "yeah, that's what we thought" and a proof it's false with "OMG what's going on here?". Another example is the prime twin conjecture, are there inifinte pairs like (3,5) (5,7) (11,13) (17,19) and so on. There's very good reason to believe it's true but nobody has able to formally prove it. There's a lot of problems today that appear to support the idea that P != NP, and that's what most people believe the answer is. However, stringing together formal proof that it's so is much harder. If this paper turns out to be true, surely it's a great leap for mathematics but it's the answer that doesn't change the world.
Live today, because you never know what tomorrow brings
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.
-Michael
The 'proof' says so right on page 1.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Misplaced hatred. (yes, this is off topic)
H1-B is a good thing for the US, but is sometimes abused by firms who wish to pay very low salaries with no benefits (sometimes practically holding the employee hostage). This behavior is bad for both the visa holder, and for the job market as a whole (supply and demand get skewed).
I apologize for those who cannot follow simple logic. (We'll just need to keep working on them.) The Xenophobes can apologize for themselves.
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
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?
At the time of writing, there are two comments on Greg Baker's blog, congratulating Vinay on making it onto Slashdot. Jeez...he's potentially solved one of (if not) the most important open problem in computing, which could land him a million dollars in prize money...but yeah...well done on making it into that most esteemed of online publications, Slashdot.
Don't you have hedges to trim? We don't do siesta" here in America you lazy sod. Now get back to work before I deport your ass.
Can we please have a formal proof. A proof written in natural language and with a length of a hundred pages almost certainly contains some flaw. Just like a program of more than a few thousand lines of code is certain to contain at least one bug.
But, extending that analogy, there's some problems you can't solve without a few thousand lines of code.
err.. rainbow tables?? Encryption with O(n ^ inf) of all 10 byte input files are pretty much constant to decrypt, even without the decryption key.
And I'm not sure what you're saying with n^1E8 . Consider what it would mean to have such a coefficient. 100 million nested loops?? Where practically speaking are you going to have that kind of coefficient in a polynomial algorithm? (I only bring it up because you mentioned practical).
The practical problem class is factorial or exponential n ^ x, which occur in combinatorial problem sets (meaning with every new element, you have to consider every existing element's permutations or combinations). Most interesting problems live here.
That being said, I've never formally studied P/NP, and personally find it a boring subject (especially given how much face time the subject gets)
-Michael
It's not. Although it might be NP-hard.
Luckily, my cryptographic scheme based on large Busy Beaver numbers remains theoretically sound.
Naah.. Just pass the responsibility over to the hardware guys.. That's what cell phone dudes have been doing for a decade. ;)
-Michael
Are you raving mad?
Of course there will be an error with this proof. Many errors, actually. Most of them irrelevant.
Maybe one of them is not. You know what? It will be caught in peer-review, exactly as it's been happening in the last centuries.
There's a reason noone uses formal proofs in mathematics. They're dull. They're slow. And we trust peer-review (for correctness, anyway).
What would be the use of a proof that no human can understand?
entropy happens
Well, uh.... uh... duh... uh... That's what she said...
It's funny how we don't hear anything from HP for ages, then as soon as there's a sex scandal involving the disgraced CEO, out come all sorts of distractions.
I smell a rat. Okay, I smell 2 rats - Mark Hurd (ex-CEO) and HPs' spin department.
Forgive my ignorance but besides traditional cryptography what does this proof (presuming it's valid) men for the world? What new knowledge will we have? What equations will this simplify? Will if give us a warp drive or what?
If video games influenced behavior the Pac Man generation would be eating pills and running away from their problems.
But the margin is too narrow to contain it.
If you can read this, it means that I bothered to log in.
Well, to be pedantic about it, they've become provably secure in a way we hadn't proven before ;) The possible is always possible, regardless of whether someone has actually done it yet or not...
Just reread the definition of P=NP (been a while).. Guess FFT isn't a good example. There's no P verify and NP answer aspect of the FT.
But then again, traveling salesman problem (minimum path) isn't P to verify as far as I can reason. Though public key encryption probably is. Encrypt/decrypt in P time (matches original input == works?). V.s. crack in NP time.
-Michael
Since his proof is that P!=NP - no implications whatsoever. (If on the other hand he had proved that P=NP there would be theoretical implications but probably no practical impact.)
All my money is invested in P = NP!
How many more years will slashdot have an off-by-one error on your Score in your profile?
P = NP only if N is 1. BS! So therefore for most cases, P != NP. Chew on that, maths.
http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_proof
Consequences of proof
One of the reasons the problem attracts so much attention is the consequences of the answer. A proof that P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP. It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice. The consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.
Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced.
On the other hand, there are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming, and the travelling salesman problem, to name two of the most famous examples. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction are also NP-complete;[15] if these problems were efficiently solvable it could spur considerable advances in biology.
But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook,[4] ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.
Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated - for instance, Fermat's Last Theorem took over three centuries to prove. A method that is guaranteed to find proofs to theorems, should one exist of a "reasonable" size, would essentially end this struggle.
A proof that showed that P NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P NP, much of this focusing of research has already taken place.[16]
Mit der Dummheit kämpfen Götter selbst vergebens
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
That was the only part that I grokked.
I admittedly don't have a deep understanding of what this means, but from skimming the relevant page on Wikipedia (http://en.wikipedia.org/wiki/P_versus_NP_problem), it seems to me that if P=NP were to be proven (contrary to what the research noted in the OP), it will have taken significantly more effort to accomplish than it would be to verify the proof. So that in and of itself suggests P!=NP...and therefore by solving P=NP we would paradoxically also provide proof that P!=NP...or so goes my line of thinking. But I suppose this is just because I just don't have a clue what I'm talking about - is solving P vs. NP is a different category of problem solving in itself?
Was your analysis recorded somewhere in the open so we can take it into consideration?
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Breaking RSA and ECC are very strongly believed to NOT be NP hard. In particular, they are both "easy" enough to be solvable by a quantum computer, but quantum computers are almost certainly not powerful enough to solve NP-hard problems.
But WHO leaked the sex scandal to the press? And WHO just "introduced" the idea about this new proof discovery being linked to the HP scandal? Its impossible for these events to be completely coincidental I'm onto your game Hudson! You probably work for Dell or Apple or HP's Mars competitor, and for one I refuse to be manipulated!.
I'm no mathematician, but the proof in the paper looks very solid (certainly makes sense from a coding point of view). Though the proof is more general, it also pretty much demonstrates that factorization can't be achieved in polynomial time (thus that RSA is indeed secure).
Help! I am a self-aware entity trapped in an abstract function!
Personally, I think karma should not contribute to karma except to offset overrated or some similar rating designed to indicate "not as funny as it's currently rated."
should read:
Personally, I think funny should not contribute to karma except to offset overrated or some similar rating designed to indicate "not as funny as it's currently rated."
Rate original -1 asleepatthewheel
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
If you show P=NP by constructing an algorithm which solves an NP-complete problem in polynomial time, you immediately have a polynomial time algorithm for *any* problem in NP. That's the definition of NP-complete: a language is NP complete if any other language in NP can be reduced to it in polynomial time.
Even if you provide a non-constructive "existence" proof, it turns out you can construct an (incredibly awful!) polynomial time algorithm by, essentially, a brute force simulation of turing machines -- so it's not actually possible to provide a truly non-constructive proof that P=NP.
I was planning on solving that next week. Now I have to figure something else to do. Might as well get drunk.
When N = 1 or P = 0
The point is that if P did = NP, then there wouldn't be any reason to think further about whether RSA is an NP problem. The constants might be huge, but there would clearly exist a poly-time algorithm for solving it. If P != NP as this result claims, then there may not be one, which is what cryptographers hope.
This person is correct. Reward them.
In fact, there is a very famous algorithm that can be used with a quantum computer that factors integers in polynomial time. QP != NP.
" The P = NP question"
As in, is it P = NP, or P != NP?
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
Well it didn't take me long to understand the summary, but I don't think I'll ever understand the actual proof.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Note to self: Buy a 5$ wrench.
I don't mind dating a girl that has been with everybody, as long as she had a good shower afterwards.
yes.
That's not true. There plenty of problems that are outside of both P and NP. And there's always one time pad, which (from a purely mathematical standpoint) is provably impossible to crack.
RSA, at least up until 768 bits if memory serves, is already solveable. At least one instance of it.
But until we have definitive proof about P = NP, or not, all we can do is remove RSA from this class of problems, i.e. it is no longer as "hard" as it once was.
I'm being thick here I guess, but why do we know the required simulation of Turing machines to be in NP=P (given assumption), and not EXPTIME or at least PSPACE?
"They were pure niggers." – Noam Chomsky
World Health Organization?
You are entitled to your own opinions, not your own facts.
We'll know that P != NP if it takes us less time to verify the proof as it took him to generate it.
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.
should be approached with the same level of skepticism as claims to have invented a perpetual motion machine, a room-temperature superconductor, or claims by a politician to stand for hope and change.
well said.
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
What you don't know is that Apple actually owns HP, and they constructed the sex scandal to draw attention away from "Antennagate".
Wish I had mod points today...though I'd have a tough time choosing between "Funny" and "Insightful." :-)
Not to diminish the accomplishment of the proof should it turn out to be valid... it will provide closure to a very well-known problem, but since most people have been operating on the assumption that P < NP already, even in absence of a definitive proof, I guess I find the discovery of a proof to that effect to be a bit... anticlimactic.
File under 'M' for 'Manic ranting'
Because HP does not deserve it.
Advice: on VPS providers
Some interesting posts on the topic
Yes, also one of the worst domain names ever :)
Christ!
Enough with the Scribd links. I want a PDF I can download, not one that requires a Facebook account or Scribd login to get.
http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf
.. or maybe I work for HP and this is our way of creating a disinformation campaign to discredit that this story is an attempt to draw attention away from the scandal? ... in which case this post just takes it one layer deeper.
Isn't the Millennium Prize for showing P=NP and not P!=NP, I'm sure one will have implications for the other but still they are not the same.
OH YEAH!!!!! ....
GCS/GMU/GP/GO d- s: a-- C++++$ U++ P+ L+++ E+ N w--- O+ M+ PS+++ PE-- Y+ PGP t x- R++ tv b+++ DI++ D+++ G+ e++/* h r y++
Hey!
/. !!
We do not accept polish notation or Hungarian math on
.
- aqk
F U
You don't need to simulate the Turing machine. You just need to encode it as a boolean formula. That's part of what Cook's theorem shows; it shows how to encode a non-deterministic Turing machine as a boolean formula with at most a polynomial increase in size. Now that the problem is in a NP-complete form just follow the reductions until you get to the NP-complete algorithm that has a P algorithm. In this way you can solve any NP problem in P time as long as you solve one NP-complete algorithm in P time.
Chris Mesterharm
Crypto requires hard problem that have hard instances that are easy to sample (for example, when we use RSA, it's easy for us to pick a modulus n = p * q that we think is "hard to factor" --- note that I'm not saying anything about factoring vs. NP, just giving an example of "easy to sample"). P != NP says that there are hard problems, but it doesn't say that it's easy to find the instance of those problems that are "hard". It leaves open the possibility that all NP-complete languages have mostly easy instances, and just a few really-hard-to-find hard instances, making them useless for crypto. The definition of polytime is kindof broken in some other senses. For instance, an algorithm that runs in time N^(log log log log log log log log log log log log N); it's not polytime technically, but practically it is fast. You wouldn't want that kind of "superpolynomial" algorithm that works against your NP-hard crypto.
It's natural to think of crypto when talking P vs NP. But this goes far beyond secure codes.
If P != NP, the biggest implication is, there are no shortcuts.
It means we will always have to do things 'the hard way' using our best statistical guesses. There will be no shortcuts to creating software, no immediate access to new knowledge. The encyclopedia galactica will never be realized.
At this point in human evolution, we've always done things the hard way, trial and error, grinding it out one step at a time or just plain blind serendipity. This is the reasoning behind, "it's no big deal if P != NP", because we know nothing else.
The real tragedy is, we will always have to do things the way we've been doing it. The importance of that cannot be overstated. Imagine learning about the most fundamental physics of some distant astronomical body without ever using a telescope, a rocket or probe. That is what P = NP complete would provide us.
We had better hope that P does indeed equal NP, because it's the holy grail of knowledge acquisition and eventually we must have it.
-postholer
A Turing machine has a state (from a finite list of possible states), a table of operations to be performed based on input and state, and an input - nominally considered an infinite tape preloaded with an input string (a series of symbols from a finite set) with the remainder blank. Input symbols can be data or action symbols (data or program). The machine proceeds from its initial state processing operations from its table based upon its state and input until it finds a state that's "Accepting", and halts. A problem is considered soluble by a TM if any potential input, operated upon by the machine in exact accordance with the table can move the state to an "Accepting" state. For the purposes of Turing Machines, operations take 0 time and the machine is immortal. From the beginning these are not presumed to be mechanical or electronic machines, but rather a theoretical human who executes the instructions without any bias or thought to the outcome. Turing Machines are a thought experiment, not physical machines. They are hypothetical. They are, however, widely used in information theory as well as other fields including physics.
/Non Sequitur: Alan Turing was a Brit who confessed to being queer, was chemically castrated and deprived of his security clearance as punishment, and is supposed to have killed himself at 42 with an apple laced with arsenic, a-la Snow White. We'll never know what more he might have given us. Homophobia cost us one of the greatest minds of the 20th century. His work is now considered fundamental to our understanding not only of what computers can do, but of the nature of the universe.
A Deterministic Turing Machine (DTM) is one that has at most one action for a specified state, action symbol and input. A Non-Deterministic Turing Machine (NDTM) may have more than one.
To say that P!=NP is to say that the Non-Deterministic Turing Machine can find an Accepting state that the Deterministic Turing Machine can not.
In the case of a NDTM with more than one potential action to be performed for a specific state and action the Turing Machine (TM) can be considered to clone itself, which each clone performing one of the indicated actions - in essence creating a tree of potential Turing Machines. Alternately the Turing Machine can be assumed to select the action that results in the Accepting state if there is any. AFAICT the potential for input strings to come to the Accepting state on divergent paths is moot as any Accepting state will do, and in the case where divergent "leaf" TMs Accept the input or enter infinite loops, an Accepting TM wins. This isn't an input validation routine: the determination that the input is invalid is an Accepting state.
I haven't read TFA, but I would imagine that the proof for P=NP would involve finding one problem where the non-deterministic machine found a solution that a deterministic machine couldn't. Presumably this involves solutions hidden by infinite loops.
Really, the idea is silly though. It's Garbage In, Garbage Out. If your Turing Machine needs non-determinism it's because it's potentially operating on unknown data or processes and so its state/action table is inadequately defined. This is an abuse of the machine. It results in solutions for problems that are NP, but the only rational course is then to dissect the tape, find the successful branches of potential choices, find the unknowns and rebuild the machine's state/action table to include these potentials. We call this process "the scientific method". To fail at this, the unknown thing that caused the effect must be unknowable. In fact, any such Turing Machine can be redefined to permute across potential state/action/input triplets, or to include the reconciliation of the result to the process, and the question devolves into the halting problem, so the problem becomes the impossibility of iteration against possible out
Help stamp out iliturcy.
i heard a lot of people saying it's a good thing that P != NP as a lot of things that depend on that property, mainly crypto, depend on it. However, if there truly were deterministic polynomial time algorithms for even one NP-complete problem, then all the problems in that class could not only be verified in deterministic polynomial time, but solved in polynomial time! We have so many everyday problems that end up being in NP...imagine if we solve them in deterministic polynomial time. A lot of scheduling problems that we've only been able to solve using sub-optimal methods in a reasonable amount of time could now be solved optimally In other words, let's think beyond just crypto people!
Thanks for the nice explanation. Cook's theorem. Sheesh, I need to review my complexity, if I ever knew it in the first place. :-/
"They were pure niggers." – Noam Chomsky
In paragraph 7 eplace "that are NP" with "That are NP and not P"
Help stamp out iliturcy.
We're inside the looking glass people!
Probably, but in reality people have constructed crypto schemes from slightly stronger assumptions (like existence of trapdoor, one way functions, etc). I don't think anyone has ever created a crypto scheme which would be provably NP-hard to break (ie, an efficient algorithm to break the crypto scheme would yield an efficient algorithm to solve any NP-complete problem). This is an open question. One challenge is that P!=NP says that some problem instances are hard, but for crypto you can't just say that some messages are hard to crack. You have to say that "all encrypted messages" (more realistically all but a "negligible fraction" of encrypted messages) are hard to break.
Indeed, N)on-P)eer-reviewed does not equal P)eer reviewed.
But B)eautifully L)aTeXed trounces peer review.
The practical implications aren't necessarily that big. I mean, there's chances that you find the poof that P = NP and a method to reduce an exponential time algorithm to polynomial time, but it's very likely that the complexity would become something like O(n^100000000...), which, for big enough values (not big from a calculus point of view, but still big in the real world) of n is comparable to O(2^n).
That would still make RSA hard enough to break, but not impossible, sure. However, it would still be breakable in the P != NP world (ergo, no security algorithm can be completely safe, only up to some point).
...which is what SOME cryptographers hope....
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
Oh man, if you think the politics and backbiting are bad in typical academia, wait until you see an entire computer science department arguing over who gets to have illicit sex in order to set off the proof-generating team.
"This algorithm runs in constant time. Come on, 2,147,483,648 is a constant..."
A simple description is that there are problems where you can quickly figure out that a given solution is correct, but where it takes a very long time to actually find a solution. There's a nice description here: http://www.claymath.org/millennium/P_vs_NP/
I was always vaguely afraid some asshole would prove that the actual problem of proving either P != NP or P = NP was in fact an NP problem.
"The good news is that, if we prove P = NP, it will have turned out to itself be a problem that can simplify to the form that proves P = NP. But if P != NP, we're probably never going to prove it . . ."
Pug
An Invisible Entity of Vast Power whose existence must be taken on faith alone: Liberal Media
The discrete logarithm problem is polynomial-time reducible to the integer factorisation problem.
I'm being thick here I guess, but why do we know the required simulation of Turing machines to be in NP=P (given assumption), and not EXPTIME or at least PSPACE?
The algorithm is: on iteration N, simulate one (more) step on Turing machines 1 through N. Stop when a machine outputs an answer with a formal proof that answer is correct.
If P = NP, then the M'th Turing Machine does this in P(n) steps. It takes P(n)+M iterations before that happens. Each iteration takes M+i steps, so the run time is O(P(n)^2), which is polynomial! (note that M is an "exponentially large" constant, so this approach wouldn't result in a truly usable algorithm.)
Does he at least provide the actual value of N ? Also, did he consider the trivial case where P=0 ?
err.. rainbow tables??
Take exponential time to build the table. Decryption is constant time. In other words, you are doing all the work once for all passwords as opposed to doing the work over and over again for each password, but fundamentally, O(10*98^n) isn't any different than O(98^n) when n is big enough.
Government is not reason; it is not eloquent; it is force. Like fire, it is a dangerous servant and a fearful master.
> 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.
There could still be trivial solutions to some problems we thought were NP, but there won't automatically be a trivial solution to everything; for cryptographic work you'd still need to make sure whatever you're using was really NP and didn't just look really really difficult.
I think the main impact for this will be to make slashdotters shut up about the relation between P and NP once and for all.
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. :-)
I'm a math grad and i want to look into the paper. Why do I have to have a Facebook account to download a pdf or even the txt version?
And no, I also don't like the /. login policy. Back in the days you could go online and post a comment without being treated like a common AC (oh wait...).
Someone know of any other sources to download the paper without a Facebook login?
Keep dreaming.
Even at "Harbor Freight" (read: cheap-ass tools), a $5 wrench won't do much more than let you take the wheels off a model train and pick your nose.
Go for the $10 wrench. ;)
Of course a Nobel Prize (NP) is not just a Prize (P)...
Careful there. "It's not" is an opinion disguised as fact.
Factoring and P are both in NP^CoNP. If this paper is true, then it just rules out P = NP and P = NP^CoNP, which leaves several possible relationships for factoring:
Integer factoring is a sub-exponential problem, although not polynomial. It would be extraordinarily unlikely for RSA to be shown to be NP-hard, since it would prove that NP is easier than most of us thought.
Don't forget: you can make predictions at http://embargolink.com/ and have them made public in the future.
Stephan
http://stephan.sugarmotor.org
"I’m dead serious—and I can afford it about as well as you’d think I can." See his blog.
Papers that claim to prove or disprove P=NP are a dime a dozen. Until this has been peer-reviewed, it's not even worth the effort to look at.
Well, it would be a bit more startling if they claimed to have proof of P=NP, now *that* would be news, essentially making any and all encryption worthless.
Short form:if P=NP, crypto is something of a futile effort - that implies that there's a non-brute-force crack to every possible private-key algorythm. I suppose it might still be slow enough for the crypto to be useful, but I woudl expect you would end up needing gigantic keys.
Not at all true. There is now an algorithm that tests primality in proven polynomial time; the algorithm is far inferior to existing algorithms for all instances that can be solved in any reasonable time. The upper bound for number of calculations is about 2^256: All the matter in the universe, completely converted to energy, would not be enough to power a computer to make 2^256 state changes. Say you have an algorithm cracking an n-bit code in n^32 steps. A 256 bit code would take 256^32 = (2^8)^32 = 2^256 steps - impossible to crack.
Obviously P must be EQUAL to NP! Otherwise, a person could construct a riddle which is is easy to create, but not possible to solve in any way before the Universe's lifetime expires. If the person shoots self or is killed after creating the riddle, that means an amount of information (i.e. the solution of the riddle) is effectively lost.
This runs contrary to physics, where even black holes, which otherwise trap the lightest light and electromagnetic radiation, must release information falling into the event horizon in order to prevent destruction of the Universe. Infomation is released via electron-positron pair generation according to the discovery made by Stephen Hawking.
Scott Aaronson listed ten signs a mathematical breakthrough is wrong.
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.
What would be the use of a proof that no human can understand?
Well, you can break the proof down into lemmas (think of them as "modules"). And you can relate those formally proved lemmas to your natural language version of the proof. You might even be able to re-use those lemmas in other proofs.
Peer review is nice. But we can make an analogy with software: open-source code is also "peer-reviewed" in a certain way, and we know for certain that open-source code is not error-free, even after many years of "reviewing".
There's a reason noone uses formal proofs in mathematics. They're dull. They're slow.
This is personal. Proofs in natural language can also be dull and slow, especially if they take up a hundred pages. So why not make it a little more dull. At least verification will be a lot faster, and a lot more certain.
If Pandora's box is destined to be opened, *I* want to be the one to open it.
The trouble is, every time someone actually proves P=NP, the NSA arranges them a little accident and the paperwork all gets "lost in the post".
Oh come on, this is one of the greatest open problems ever in mathematics, and everyone in complexity theory is aware that new "proofs" reguarding the P vs NP problem come out every month or so. It is one of the most common open problems that people try to solve. In fact, a common "practice" job or training for early grad students in the field is to find the errors in these proofs. Note I say find the errors, not determine if they have errors. They always have errors. Look here for what the scientists in the field tend to think about p vs np proofs. http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html
...because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
Hold the best orgy ever?
Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.
So in order to view the PDF, I have to wait for a Flash or similar webapp to load, then view it in a tiny frame inside the browser, and then if I want to download it, "Log in with Facebook" or "Create an Account"?
Come on. Scribd sucks, it has always sucked, and it shouldn't ever be used to post serious links that get to the front page of Slashdot.
Now I'll read this, although sadly I don't have the knowledge to understand half of it... if the P != NP problem has really been solved that would be a real breakthrough! :)
I think this is a more useful link:
* http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
Latest entries (see bottom of page):
* In December 2009, Ari Blinder proved that P is not equal to NP
* In April 2010, Lizhi Du proved that P=NP
* In May 2010, Changlin Wan proved that P=NP
* In June 2010, Carlos Barron-Romero established P=NP
* In July 2010, Mikhail Katkov established P=NP
The paper of this slashdot discussion is presently mentioned at the top of the page.
Stephan
http://stephan.sugarmotor.org
Apparently cracking proteins is NP-hard as well. We all knew deep down that P!=NP, but we all secretly hoped it wouldn't. There are so many interesting NP-hard problems around... if only.
"QP" doesn't mean what you think it means: it actually means "quasi-polynomial time" (basically, worse than polynomial but better than exponential, with nothing to do with "quantum").
I think you mean BQP (bounded-error quantum polynomial time), which is the class that contains Shor's algorithm (the one you mentioned that factors integers in polynomial time).
BQP != NP is actually still unproven (but most people believe it -- if false, quantum computers would be way too powerful). Even BQP != P is unproven (but also mostly believed -- if false, it would render quantum computers largely useless, and would be surprising from what we know about Physics).
As a side note, the direct quantum analog of P is actually EQP (exact quantum polynomial time, i.e., quantum algorithms that run in polynomial time and are right with probability 1). EQP is not known to contain many interesting problems (the only one I know is Deutsch-Jozsa, which is mostly useless), so most quantum algorithms you'll likely hear about are in BQP. BQP is actually the quantum analog of BPP (bounded-error probabilistic polynomial time, which is increasingly believed to be equal to P, especially after "primes in P" -- but there are still problems in BPP that are not known to be in P). BQP, on the other hand, is not largely believed to be equal to EQP.
The basic proof scheme uses classical reductio ad absurdum, making the proof a non-constructive one. Even if it holds, then, we may still face the situation that a P (P-time, P-space) solution for an NP-compete problem can be proven not to not exist, without actually yielding the solution in P.
Looks like we got this computation...
*puts on sunglasses* ...Cracked.
Proving P!=NP to distract from a scandal would be amazing. *Claiming* to have proven P!=NP to distract from a scandal, on the other hand, is easy. The paper has not gotten any peer review yet and they're already issuing press releases? Smells fishy.
No, that's wrong on many levels.
First of all, cryptography doesn't, in general, rely on an assumption that P!=NP.
P!=NP is related to public key cryptography, but not in a simple way. Public key cryptosystems relying on NP hard problems have failed because NP hardness isn't a guarantee that problem instances are hard to solve. On the other hand, current public key cryptosystems rely on factoring, which isn't even known to be NP complete. P=NP would result in polynomial algorithms for factoring, but not necessarily in a way that would break public key systems in any real way.
And that's another problem with P/NP considerations: (1) they are worst case complexity classes, and (2) the degree of P is not limited. As a result, problems in P may be impossibly hard to solve, while many instances of an NP hard problem may be easy to solve--too many to let you construct a good crypto system.
There is one thing which really surprise me: Page 44 (so 47 of the pdf http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf) he gives a “succ” relations, but he stated before that he does not want any order. And he certainly can obtain an order with the succ relation and the least fixed point. And it is well known that you can compose LFP to obtain only one LFP, hence if it’s proof works, it should also works over structures with an order ! I do not state that it means that the proof is false, but if this works, it also implyes what look like to be a really strange corollary into finite model theory, because it would use a kind of locality which does not take care about the orders relation. (At least that is what I understand of it but it may also be because this small part is really close to what was my current research)
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).
Factoring is an NP problem : guess the bits and fail if they don't multiply to give what you want. It is also unlikely to be NP-complete as there are sub-exponential algorithms for it (it it were NP-Complete then quasi-P = NP).
More to the point, if P = NP, then there are polynomial algorithms for breaking symmetric key ciphers and hashes as well. Then again, polynomial time != implementable in reasonable time.
This guy is so out of it. Any texter knows NP means "No Problem". I guess "P" is "Problem". P may be hard for him, but NP - no problem!
CUL8R
It might be, depending on the value of n and how much time n=1 would take. Not everything needs to scale well; sometimes you just need the fastest possible algorithm to, say, sort a mostly-sorted 100-element array.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
Even for hypothesis which everyone believes to be true, the proof will still change things. For example (IIRC), if the generalized Riemann hypothesis is true, there is an known non-probabilistic algorithm to check whether a number is a prime in polynomial time. Of course, until the hypothesis is proven, you would be stupid to use that algorithm, so the proof would be a big deal (for small values of "a big deal").
P!=NP is a know result, where N = (P-1)!
Slashdot, fix the reply notifications... You won't get away with it...
It's brute-forcable but not solvable. Big factorization (which is the crux of RSA -- finding the integer factors of a giant number) is still expoential, it's just that computers have gotten much much faster, so it's possible to brute-force those keys in a "finite" amount of time.
"solvable" in this context would be someone found a polynomial time to factorize the number. But, I don't think factorization is in NP, so it may be a moot point. (I think it's EXPTIME, but it's been a while)
-Bucky
No.
Many cryptoalgorithms depends on some hard to reverse operations. But for example we know (for now) that discrete logarithm is hard, but we do not know if it is in NP-hard at all!
Symmetric cryptography will be unaffected as I understand.
But yes, having P=NP, will make asymetric cryptography impossible.
[inception]BWOOOOM[/inception]
And still even if this algorithms will land in P. It still raises question, will it be n^100 ? Or maybe 10^100000 n^3 ? This will mean asymetric crypto is quite secure.
Now you're just humiliating him. I thought that you were talking about something in the lines of the four-colouring theorem.
If he did his work right the proof of each individual lemma is a trivial thing; only their connection is non-trivial. And this is where lies the beauty and ingenuity of his proof. To murder it with formal language is... unthinkable. And to require formal language side by side with natural language you're doubting his and his peers' competence.
You seem to take issue with the fact the only a few enlightened souls can check the proof; it is sad indeed. If it were a formal proof anyone who knew the first thing about computers could verify it.
But there's no way around it. If you (or I) would just check it with a computer, nothing of value would be gained; the interest is not so much in the result, but in the techniques used in the proof, and you wouldn't learn that.
For example, in Perelman's famous result he perfected a very powerful tool (the Ricci flow), that is being widely used in other areas of mathematics.
entropy happens
HP: "You know how fuckin' easy this is to me? This is a joke! (crumples proof) And I'm sorry you can't do this. I really am. 'Cause if you could I wouldn't be forced to watch you fumble around and fuck it up." HP: "Do you like Apples?"
But the factorization problem leads to a solution to the discrete log problem, using Shor's algorithm in the quantum world.
It is not my intention to humiliate anybody.
I am just not so much interested in reading a hundred pages when I am not sure if the end-result is correct. Even if there are numerous other valuable theoretical points made in this article. I'd rather run a automatic verification tool, and then decide if I'd read the article. I have faith in peer-review up to a certain point; it is not something which is infallible. I can easily imagine some future slashdot article with a headline "P != NP proof found to be incorrect", or even "P == NP after all". Also, imagine the waste of brain-power if researchers wrongly assume "P != NP", and start developing new theories from thereon.
Also, given this 100 page document, I'm totally in the dark about what other pieces of literature are necessary to grasp the proof. With such a large proof, it is easy to end up in a "dependency nightmare". With a formal proof, at least I can get a quick overview of dependencies.
Again, no offense to the author of the proof. This has in fact little to do with this particular case, just with the way in which science works in general.
If Pandora's box is destined to be opened, *I* want to be the one to open it.
That fishy smell, it's from the sex scandal.
R.J. Lipton discusses his initial reaction to the proof in his blog:
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
Proving that there are classes of NP that have no P just suggests certain crytographic algorithms MIGHT be NP.
Not a CS person here, but I know enough to nitpick. A problem that is in NP does not imply it is "hard". In fact, all the "easy" problems that are in P (eg. binary search, etc.) are also in NP. A more valid (but admittedly clumsy) restatement would be:
Proving that there are decision problems in NP that are not in P just suggests certain cryptographic algorithms MIGHT not be in P (or "MIGHT be 'hard'").
By the way, a lot of the crypto related problems are suspected to be in http://en.wikipedia.org/wiki/BQP
Don't quote me on this.
Wait, there's a sex scandal involving Carly Fiorina?
Oh, never mind, the OTHER disgraced CEO.
But then again, traveling salesman problem (minimum path) isn't P to verify as far as I can reason.
TSP is a NP-hard problem, as it is at least as hard as any problem in NP. The NP complete problem embedded in TSP is finding a Hamiltonian path.
I was taking complexity at UofT with Cook, he actually is a brilliant teacher AFAIC, he made this stuff seem easy.
You can't handle the truth.
It means we can breathe easy that a lot of crypto out there is now provably secure.
Wrong. It only means that the crypto based on NP-Complete problems are provably secure on classical computers.
Fact #1: RSA and many other crypto algorithms are not based on NP-Complete problems.
Fact #2: While no sane person will bet that Quantum computers can efficiently solve NPC problems, this has yet to be proven.
Fact #3: P!=NP does not imply that it will be easy to make crypto systems out of NP Complete problems. In fact (AFAIK) the reason why most crypto is based on weaker problems (eg. Integer Factorization) instead of NPC problems is because a random instance of an NPC problem can be easy to solve or approximate (for example, imagine a travelling salesman on a graph that resembles a linked list). Proving a crypto scheme secure probably involves having to prove that EVERY instance of the problem generated by the scheme is (very likely) hard enough that computers wouldn't be able to solve in reasonable time. This may actually be harder than proving P!=NP itself.
Don't quote me on this.
Whether integer factorization has been shown NP-hard isn't the question here; the question is whether it's been shown to be in P (i.e., there is a polynomial-time algorithm). We know factorization is in NP somewhere, since it's easy to check a proposed factorization. (Checking if it's a prime factorization is a bit more work, but checking that a number is composite is certainly in NP, and if P=NP the complement of a problem in NP is in NP, which means then in P.)
Therefore, if P=NP, there is a polynomial-time algorithm to get the prime factorization of a large integer, and that is significant. It is true that proving P!=NP doesn't give us any new information on the problem.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
As it turns out, our current method of public key cryptography has not been proven to be in NP, so even if it turns out that P != NP it is still possible for a polynomial time algorithm that breaks our cryptography system to exist.
Believe it or not there are many more time-complexity classes than P and NP. It's just that there are many NP problems that we want to be able to solve quickly, so this was made an important problem. Lastly, showing that P != NP only proves that there is no polynomial time algorithm that can solve an NP problem on classical computers. There's still the possibility of a non-classical computer that can solve it in polynomial time, or of a probabilistic algorithm (one that might solve it with some bounded probability) that can solve an NP problem in polynomial time.
Downloading the paper requires facebook login? Are you kidding me?! This is just a very elaborate scam to acquire new facebook members isn't it?
Factoring is an NP problem : guess the bits and fail if they don't multiply to give what you want. It is also unlikely to be NP-complete as there are sub-exponential algorithms for it (it it were NP-Complete then quasi-P = NP).
Yes, good point!
More to the point, if P = NP, then there are polynomial algorithms for breaking symmetric key ciphers and hashes as well. Then again, polynomial time != implementable in reasonable time.
It means that strong one-way functions don't exist, ergo all of the theoretical, complexity-theoretic results which are predicated around the existence of these functions go poof. There's still always the possibility of finding problems that are very, very hard to solve.
I didn't see this elsewhere in the comments.
Here is a link to the paper off of Dr. Deolalikar's official website at HP. It appears to be rather slow, but is loading eventually.
... is that shitty smell also from the sex scandal?
If I find a flaw, will it mean that P = NP ? :))))
Some "fast" (4 years!) peer reviews give us "99%-mathematical-certainty" for famous theorems: http://en.wikipedia.org/wiki/Kepler_conjecture . Really useful and non-dull.
Well, that's not quite true. The security in RSA is based on the difficulty of factoring. Just because we don't have a polynomial-time deterministic factoring algorithm doesn't mean that there can't be one; a proof would be required to assert such a thing, and unfortunately we don't have one. Now, we DO know that a non deterministic computer (quantum computer) can solve factoring problems in polynomial time (actually VERY good time), so if only we can build a large enough quantum computer, RSA will be trivial to break. So, this paper doesn't say ANYTHING about RSA. But what we know is that we need to find either a proof of the difficulty of factoring, or a polynomial time factoring algorithm for a deterministic computer.
Please take some time to read about Quadratic Sieves and Number Field Sieves ... these are both polynomial time algorithms used to perform integer factorization, and are no way related to "brute forcing".
Symmetric keys are exchanged using asymmetric algorithms, either based on discrete logs or integer factorization.
RSA is the integer factorization problem, the discrete log problem has implications with Diffie hellman, another asymmetric algorithm.
Symmetric algorithms are not based on either of these, they are based on the property of diffusion. Essentially randomize the data over a small enough field that its impossible to pull it apart. For stream ciphers it becomes a seed the value into random.
If this proof holds up there is no difference than what we already assume and believe. We work under the assumption that P!=NP, as such this would not change anything. We could not further add problems into NP space because the book has already allowed to do it. W cannot show that it would be a hard problem if this held up, but if P did equal NP, then we could show it was an easy one.
Isn't something like y=x^2 a one-way function? Given the input x you can always arrive at the same y, but given y you cannot always arrive at the same x.
VinayDeolalikar has a direct link to his most recently updated version of his paper, "P is not equal to NP". 6th August, 2010 on his personal page on HP Labs' website.
Hey, you can take it any which way you want.
Are you an expert in complexity theory? Or even a mathematician of any kind? If not, sorry, but this proof wasn't meant for your consumption and it'd be ridiculous to expect the author or anyone else to go through several years of work proving it formally in order for you to verify its correctness to your satisfaction. If you want that, you should pay for it to be done; no one else is going to do so because no one cares.
Le français vous intéresse?
Isn't something like y=x^2 a one-way function? Given the input x you can always arrive at the same y, but given y you cannot always arrive at the same x.
No, it is not. You can compute each of the roots of y in polynomial time. One of the uses of one-way functions is a cryptographic hash. Let's say you have a table of passwords for every user in the system. You don't want to keep passwords in the clear or even encrypted; nobody should have access to your password who is not the owner. Then you can keep hashes of passwords. If you provide correct password, its hash should coincide with the hash in the table. However, for a good hash, nobody should be able to come up with any preimage, i.e. a password that the system will consider legitimate, because it has the same hash as your password. Of course, this is about average case complexity; if I know that your favorite passwords are "slashdot" and "CmdrTaco", I can just try them and see if the system lets me in.
Do you know the movie "wag the dog"? Similar story.
The running time for GNFS is:
O( EXP[ (CONSTANT_GREATER_THAN_ONE) * (log n)^(1/3) * (loglog n)^{2/3) ] )
Which is certainly not polynomial. But isn't quite exponential.
My bad, I'm usually loose with terminology (I work on a particle accelerator, i'm used to having to dumb things down to get the bigger points across to people who wouldn't understand the nuances)
I have 3 thoughts:
1) GGP implied factorization is solved. I wouldn't count a super-polynomial algorithm as 'solving' the problem. In the context of RSA, I'd count "solved" as it would be within the reach of the average person to break a code. (for instance, substitution cyphers are "solved")
2) I thought that factorization wasn't in NP, but I forgot that you can formulate it as a decision tree, so I was wrong on that.
3) From a practical aspect, knowing P = NP wouldn't be useful right away. The complexity of the solution could still be ridiculous even if it's in P.
-Bucky
It does not. The proof is based on the structural properties of SAT and how they contradict the predicted properties of a P problem.
then there wouldn't be any reason to think further about whether RSA is an NP problem.
Clearly it's the NP-hardness of any problem, rather than the NP membership, that makes it useful for security applications.
By way of example, add-and-compare (given integers x, y and z, answer "is x + y <= z") is in P and thus in NP. But since it's in P (and since we all learn an efficient algorithm in school), it would be somewhat foolish to base any kind of security on the assumption that an adversary cannot add numbers.
Also, every NP problem reduces to the halting problem, so it must be NP-hard (reduction: "for every candidate solution: if it works: return it; endfor; hang"). But, as the halting problem is undecidable, it is unlikely to enter into the picture as an attack on a cryptosystem as the cryptosystem is not likely to go near "halting territory" (i.e. involve that as a part of the encryption or decryption process, or anything attackable by a halting-decider); at least not in my experience (I'm a ph.d. student in cryptography).
Note that to the best accuracy ability of my memory, there is cryptography with only polynomial "advantage": encryption and decryption takes time O(n), breaking takes time O(n^2); this is provable without any unproven assumptions (such as the hardness of factoring or discrete logarithms). As long as the best known factoring algorithm takes superpolynomial (but subexponential) time, I prefer that; but if it breaks down, there is somewhere to retreat to. Presumably, that area is open to much low-hanging further research fruits.
Seeing the story now, I posted my solution on my web site: www.Pratowski.com. I thought about this (in 2008, when I first heard about the problem) and wrote the answer in a 3-page Word document, then didn't know where to publish it. My simple argument is this: The things we call "non-deterministic polynomial type" problems are really human problems that can be solved with human insight and not mere calculation. I provide several examples: the words we have to type to get a Slashdot account, being able to read any mixed up words immediately, Navajo code talk, and more. The P-NP issue can help us to clarify what humans can do better and what computers can do better. Thanks for reading this. Please let me know what you think. -Ed Pratowski
Actually, it's because we all think you live under a bridge.