Slashdot Mirror
No P = NP Proof After All
00_NOP writes "Internet commerce seems safe for now as Russian computer scientist Vladimir Romanov has conceded that his previously published solution to the '3 SAT' problem of boolean algebra does not work. If his solution did work it would have shown that many problems thought to be unsolvable with conventional computers — including decrypting your HTTPS encoded credit card number — would have been solvable in polynominal time. Romanov, who is very far from the sort of crank who normally claims to have proved P = NP or the opposite, is not giving up though..."
Seriously? On Slashdot? People still value the pursuit of knowledge over here. I am sure your grandfather can understand that.
Proof = No Proof
Solving this problem would save energy on the hundreds of thousands of NSA computers that are currently decrypting all of your e-mail and Skype conversations.
"I assumed blithely that there were no elves out there in the darkness"
Car analogy: P=NP - it's like everyone has always thought the supermarket was on the other side of the ocean, but it turns out that it's just a short drive down the street. The street may be flooded though.
Need proof that faster is better? Look at your computer. Now, Look at the computers of the 1960s. See?
All the stuff you do on a computer is the product of a collection of mathematical algorithms and instructions called programs.
One way to make programs faster is to make the algorithms faster... Remember, "faster is better", Grandpa? Grandpa?
(He's asleep, I'll just tiptoe out...)
Basically works like this...
Encryption works by performing a calculation that is easy to perform one way, but very difficult to perform in reverse. It's more than just a subjective "easy" and "very difficult" though -- there are ways to measure how hard a problem is to solve. Encryption works because we're pretty sure of this distinction between "easy" and "very hard".
If P = NP, then we were wrong, and there really wasn't a distinction. This means all encryption is now broken, because it is just as easy to decrypt messages as it is to encrypt them.
However, most people believe P != NP. But we haven't proved it yet, mathematically, so people are always a little nervous about the topic.
You can think of P as "easy problems", and NP as "hard problems". If P = NP, then easy = hard, and encryption is broken. If P != NP, then encryption is safe.
In your requested layman's terms:
Proving that P=NP would prove that mathematically "hard" problems can be solved "easily." Encryption algorithms are designed around the fact that these hard problems can't be solved quickly by a computer. If P=NP, all modern encryption fails, which means most Internet commerce comes grinding to a halt until another solution can be found.
All NP-complete problems (the "hard" problems mentioned above) derived from the 3-SAT problem, so if 3-SAT were proven to be easily solvable (3-SAT is in P), all NP-complete problems are easily solvable.
This is just one real world application of this problem.
Basically the idea of P=NP is summed up in this question: For any problem where it is easy and quick to verify if a potential solution is correct or not, is it also possible to find the solution in the same timeframe?
In compsci anywhere you have to brute force something, right now the answer is "No" but if it turns out to be true it would have the potential to make crypto useless (since crypto relies on N being a very large number, large enough to where it's not worth it to spend NP time breaking the encryption, but where P allows for realtime encryption/decryption.
I read a car example somewhere, probably slashdot. OK so if you have misplaced your car keys, this is a P!=NP problem. It's easy to confirm whether or not you have found your keys at any point in the search, but finding the keys themselves likely will require looking through all possible locations where they could be.
A possible P=NP variant would be if you had a buzzer attached to the keys triggered to make noise when you clap, then you just clap and walk to the buzzing. No wasted effort searching, P=NP (or at least, as close as you can get).
"unsolvable with conventional computers"
They're not unsolvable, they're infeasible. There's an important difference.
You can solve TSP for 1 million cities if you're willing to wait a few billion years, but the fact that you're waiting a few billion years makes it infeasible.
There are tons of problems which are NP hard. So if we solve one, solving these problems will be feasible.
Timetabling - Making timetables automatically.
Resource Distribution - (Similar to timetabling) - which can sort out how limited resources should be utilised for maximum efficiency
Bin Packing - Which will make compression algorithms and sorting your favourite stuff into optical disks more efficient
TSP - Which can get the optimal route between a number of locations - the shipping/transport industry will love this
Protein Folding - Is also NP hard, which means that the biochemical and medical industry gets a significant boost
(etc)...
It'll also totally ruin cryptography.
Are you taking lessons from BadAnalogyGuy?
Life is a great ride, the vehicle doesn't matter
I'm sorry... When in the history of human existance has more people been pulled up from poverty than the past decade?
China, India, the many smaller countries in Asia, the burgeoning middle class in Africa... You see only what is 3 feet in front of you, ignoring everything else.
- These characters were randomly selected.
That just keeps getting funnier every time it's posted (Which is about 30 times in any P =? NP story.)
Seriously, what is with people thinking "if I can not understand it fuck it" these days? How arrogant have we become?
1 word: Reagan. He's the one who started all this nonsense about how it's a bad thing to be educated and intelligent. It made his hick supporters "feel bad" so now they lash out at the "intelligencia".
Not bad for a troll.
Anti-intellectualism in American Life, by Richard Hofstadter published in ... 1963. Not 1988. In fact Hofstadter was dead by '70.
"‘the more learned and witty you bee, the more fit to act for Satan will you bee" John Cotton 1642 in Boston USA
Its across the political spectrum, not just a republican thing.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
(since crypto relies on N being a very large number, large enough to where it's not worth it to spend NP time breaking the encryption, but where P allows for realtime encryption/decryption.)
If by "N" you mean the "N" in "NP", then I think you've got it wrong. The N is not a number, it stands for "non-deterministic", meaning that problems in NP can by solved by non-deterministic turing machine (which we don't know how to build) in polynomial time (the "P" stands for polynomial). Problems in P can be solved in polynomial time by a regular (deterministic) turing machine.
There are many problems that are too hard for humans to solve. We may be able to give a good guess at the answer, but to answer them correctly we must use a computer. The development of the computer and the research that has determined how to solve problems on a computer has brought about lots of good things. We can analyze medical images for cancer, launch satellites into space, fly around the world, and talk to anyone we want whenever we want. However, there is yet another set of problems that too hard even for computers to solve. Much like us, computers may be able to give a good guess at the answer, but they cannot answer them correctly. Research into P=NP is there to let us determine the nature of these problems. If P=NP, it means our computers can solve these problems, even if not on today's machines. If P!=NP, it means that our computers (of today) won't ever really be able to solve the problems. In either case, the decision will have enormous impacts on how our governments and corporations invest in research in the future.
I have a question on this. Assuming an algorithm was found for the 3-SAT problem, in polynomial time, and therefore proves that P=NP, how does that actually get us any closer to an actual algorithm for factoring large numbers in polynomial time, which is would be a completely different algorithm. I realize that we might know that such an algorithm is possible, but how does knowing something is possible make the problem any easier to solve? For now, we aren't sure that it's impossible, so we might as well assume it's possible, and therefor try to solve the problem. But the people working on these problem pretty much assume it's possible. So to repeat the question. How is knowing P=NP any different from assuming P=NP when you're trying to find an algorithm for solving these really hard problems? Can all NP problems can be solved with the same algorithm, or a variation thereof?
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
I read a car example somewhere, probably slashdot. OK so if you have misplaced your car keys, this is a P!=NP problem. It's easy to confirm whether or not you have found your keys at any point in the search, but finding the keys themselves likely will require looking through all possible locations where they could be.
Terrible example because your "NP" example is inherently a polynomial time problem, so you've got it exactly backwards. Doesn't matter how many dimensions your universe has, if it takes one time unit to search one unit cell, then inherently the total time required to search any given region can only increase as a polynomial as the region scales linearly. So searching for car keys is very strictly a polynomial time problem and scales somewhere between power of 2 and power of 3.
Want a NP problem for an old person, whip out ye olden times interstate road atlas (or if the interstate is too modern for them, try railroad timetable). Ask them to find the fastest route to visit all their friends and relatives and note how the effort required is pretty easy at low digits and gets terrifyingly difficult once you have a couple hundred, to the point where whim or guess -n- check is the best solution. Now thats something that does not scale polynomially.
One widely held, and completely wrong, belief about P != NP is that if a poly solution exists for currently non-poly problems, it'll be a simple click of a mouse to instantly solve all poly problems, which is pretty ignorant. What if the poly time solution has a constant C factor that is a multiple of the age of the universe? Or if the "easy" squared coefficient numerically equals a mere google to the power of a google to the power of a google? Its very interesting mathematically, and as the answer to a trivia contest type question, but it does not necessarily have to have any real world impact at all.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
Next the Slashdot story will be used as a Reliable Source on Wikipedia.
This. How is GP even a real question? Could we have given your 89yo grand father a "sincere 'down-to-earth' answer" to the "what is quantum theory" question? Oh, he did not understand? Never mind quantum cryptography, then. Never mind research into prime factorisation.
Seriously, what is with people thinking "if I can not understand it fuck it" these days? How arrogant have we become?
There's a whole profession dedicated to decoding things like this and summarizing them into easy to understand tidbits we call "NEWS ARTICLES". There are probably very few people who understand the science being done at CERN yet a large number of average joes have some idea what is being researched there due to this mysterious "NEWS ARTICLE" phenomenon. Hey, I think I'll go check out one of these "NEWS ARTICLE" websites.. perhaps slashdot.org. You may want to rethink things if you think the person you replied to is the person who's being arrogant in this discussion.
This is just wrong. Both prime factorization and discrete log, have polynomial size certificates and are therefore in NP. While none of the problems are know to be NP complete (and as you say, we suspect they are not). Proving that P=NP will still show that there exists polynomial time solutions to both problems.
Prime factorization is in NP (proof is just about as trivial as they come) and therefore if P=NP, there must exist a polynomial time algorithm for prime factorization. Who gives a fuck if factorization is NP complete or not, that doesn't matter in the slightest. I suggest you learn what NP complete means, as a start.
ASCII stupid question, get a stupid ANSI
You're arguing the wrong way. Factoring and other problems related to crypto aren't believed to be NP-complete, but they are known to be in NP. Thus, a proof that P equals NP implies that integers can be factored in polynomial time, which would allow to break cryptosystems efficiently. (cf. http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof)
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
Also there is no guarantee that a P=NP solution must be feasible. There may exist a polynomial solution to cracking AES, BUT that specific problem may result in polynomial coefficients that are so unimaginably large as to require lots of Knuths uparrow notation to express numerically, making it a meaningless victory.
Sample dialogue: "The good news is its poly, in fact not only poly, but linear, in fact not only linear but coefficient of one, so if we double the key length then we only double the search time. The bad news is we're talking about doubling a trillion times the lifetime of the universe assuming every atom in the universe did an op every Planck time. Other than that, no problemo, because P = NP."
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
Every story under Slashdot lately has some asshole griping about the inadequacy of the story subject.
Hey, adequacy police assholes: don't take it so fucking seriously. And stop taking yourselves so fucking seriously. This is a place to hang out and discuss random topics of nerd interest. That's it. That's all this place is. We're not compiling the text to Bible 2.0. Yet you attack the adequacy of story subjects as if you were some sort of religious fundamentalist and we were insulting your religion.
Get the fuck over yourselves.
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
Mod this up, and mod GP -1, plain wrong.
Who gives a fuck if factorization is NP complete or not, that doesn't matter in the slightest.
Nitpick: If P=NP, then factorisation, or any other problem in NP, is NP complete.
Of course I also got the P NEQ NP one just in case...
--
Marc A. Lepage
Software Developer
It's been proven that all NP problems are actually the same problem. That is, it is possible to transform any NP problem into any other NP problem in polynomial time. So, if you come up with an algorithm that can solve the 3-SAT problem in poly time, it is relatively easy to come up with a polynomial time algorithm to turn the traveling salesman problem into a 3-SAT problem.