No P = NP Proof After All 318
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..."
A better heading (Score:3, Funny)
Proof = No Proof
Re: (Score:2)
Well if you prove that A = Not A, you're certainly going to give mathematicians and physicists everywhere a heart attack.
Re: (Score:3)
Not to mention having a bunch of pissed off and confused Objectivists milling about.
Re: (Score:2)
There is the hypothetical subclass of numbers humourously referred to as Heisenberg numbers. By referencing them, their value changes.
Re: (Score:2)
Re: (Score:2)
Prove it! :P
Mistake in Summary (Score:5, Informative)
"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.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
Re: (Score:2)
Computers in the real world (by which I assume you mean personal computers) can easily solve TSP for 10 cities. Maybe even 100. The threshold for feasibility of any NP problem depends on the size of the input. At some point it is feasible for all computers, and at some point it is not feasible even for the biggest computers.
A more precise definition would be "Turing-computable". TSP is computable. The halting problem is not.
Re: (Score:2)
Re: (Score:2)
So if we started doing the calculations today, one day someone would have a better computer or algorithm that would surpass all the work we'd done over years. Not really an incentive to getting on that one! Not to mention the code would have gone through countless hardware and software changes, power loss, etc. over a billion years. I figure someone 10000 years from now would go "hey, what's this computer for?" and the other guy would be like "no idea.. just unplug it".
Re:Mistake in Summary (Score:4, Informative)
http://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability [wikipedia.org]
The term "infeasible" w.r.t. constraint satisfaction problems (like 3-SAT) does not refer to the difficultly of the problem, but rather its result. For instance, an easy SAT problem with no solution would be infeasible.
Re: (Score:2)
I should also point out that some so-called "intractable" problems can be solved fairly quickly. Many 3-SAT problems can be quickly solved by algorithms [wikipedia.org] such as DPLL or WalkSAT. It's just that solving a 3-SAT problem can potentially take exponential time.
Likewise, many problems that are "undecidable" in general, such as the halting problem, can be solved in many common cases. It's just that given any program, any particular algorithm is potentially unable to determine whether it halts or not.
Many people thi
Re: (Score:2)
"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.
And, critically, they're infeasible because the effort scales at higher than polynomial rates as the problem space increases.
Perfectly feasible in 100 ms at 32 bits scales to 100 trillion years at 1024 bits. That kind of thing.
Now its perfectly possible to find a poly solution, that scales polynomially, that is none the less completely infeasible and "has no application". Looking above, a poly solution might exist that cracks 32 bits in a mere 100 trillion trillion years, and scales linear so 1024 bits ta
Re: (Score:3)
You can solve TSP for 1 million cities if you're willing to wait a few billion years
No you can't. You can't solve TSP for 1 million cities before the expected heat death of the universe. You can't even solve TSP for 500 cities before the expected heat death of the universe (assuming you can do less than 10^100 instructions per second).
Re: (Score:2)
You can solve TSP for 1 million cities if you're willing to wait a few billion years
No you can't. You can't solve TSP for 1 million cities before the expected heat death of the universe.
Umm, do you have a proof of that?
Re: (Score:2)
Sure you can. You just can't verify the solution, because P != NP.
But there's nothing that prevents you from guessing the correct solution in a millisecond.
Re: (Score:2)
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.
Are you sure there is enough energy in the whole universe to compute 2^1000000+ instructions? Even if time is not an issue, the laws of thermodynamics may very well be.
Proof.. (Score:2)
Re: (Score:2)
So, it has been proved that it is not possible to prove something we may or may not be able to prove?
No. It's been proven that this one proof is not a complete proof. There may be other proofs which will be proven to be proofs.
Romanov (Score:2)
So... (Score:2)
What is with you adequacy police? (Score:3, Insightful)
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
Re:So... (Score:4, Funny)
Understanding what P, NP and that ilk is (Score:2)
On the same blog, actually:
http://cartesianproduct.wordpress.com/2010/12/29/what-if-p-np/ [wordpress.com]
Yay I can keep my P EQ NP license plate :-) (Score:2)
Of course I also got the P NEQ NP one just in case...
Re:Let me ask a "stupid" question (Score:4, Insightful)
Re:Let me ask a "stupid" question (Score:4, Informative)
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.
Re: (Score:2)
"There's a whole profession dedicated to decoding things like this and summarizing them into easy to understand tidbits we call "NEWS ARTICLES"."
And if you read one of these news articles that happens to be about something you already know about, it turns out that instead of taking the time to understand and summarise them, most journalists just write any old crap that's usually not only wrong but demonstrative of their complete lack of effort to understand the source material.
Re: (Score:2)
that's too smart!
You're one of THEM!
Re: (Score:3, Interesting)
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.
Re: (Score:2)
Republicans like Reagan and Palin and Beck are the flag-bearers for anti-intellectualism in our times.
I'm not disagreeing that they are a tiny little itty bitty subset of the flag bearers, but they seem kinda outnumbered and outgunned by the sports-fans, jocks, sportscasters, religious preachers, Christian creationism activists, intelligent design authors, romance novel writers, tv newsreaders, pretty much the entire pop culture industry from hip hop musicians to movie actors, the entire freaking population of California Lousiana and Mississippi, and american idol viewers.
After all, wasn't Little Wayne and
Re: (Score:2)
Re: (Score:3, Funny)
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.
Re: (Score:2)
Re: (Score:3)
Are you taking lessons from BadAnalogyGuy?
Re: (Score:2)
No way, if he had - the analogy would have been more entertaining.
What happened to BadAnalogyGuy anyway, he seems to be posting as a mere mortal these days - with no bad analogies.
It's like watching a bald eagle take a crap.
Re:Let me ask a "stupid" question (Score:5, Insightful)
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...)
Re: (Score:2)
How is a quad-processor DOS computer on steroids any better than a powersaving 16-core ARM mobile CPU+GPU which you can carry around in the palm of your hand?
No realy...
Re: (Score:2)
Apples to apples. How does that handheld compare to the same-sized handheld of the 1960s?
Re: (Score:2)
Aside from the obvious "What handheld?"-question; powersaving, shaders and RISC?
Re: (Score:2)
Re:Let me ask a "stupid" question (Score:4, Insightful)
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.
Re: (Score:2)
Particularly if you count the number of people pulled out of absolute poverty. That is defined as:
David Gordon's paper, "Indicators of Poverty & Hunger", for the United Nations, further defines absolute poverty as the absence of any two of the following eight basic needs:
While the US and Europe may struggle at the moment, we have not fallen this far. I don't mean to take away from the hardships that many endure right now, but the number of people living without the most basic of needs has been going way, way down. Today we estimate that 1.7 out of 6.9 billion live in absolute poverty, it's still a huge number but 5.2 billion do not.
There's also relative poverty but I care less
Re: (Score:2, Funny)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
in cryptographic terms this would mean cracking encryption or forging a signature in a comparable number of operations (within a few orders of mag
Re: (Score:2)
Re: (Score:2)
Re: (Score:2, Informative)
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
Re: (Score:2)
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 solvabl
Re: (Score:2)
Are you a mathematician? [tvtropes.org]
Re:Let me ask a "stupid" question (Score:5, Insightful)
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).
Re: (Score:2)
"so grandpa. it's like this. if you lose your cell phone, it's P-easy to say it's not on the counter, or in the couch. but it's NP-hard to say where they are if you don't remember. what we're trying to figure out is whether we left the phone on, so that we can just dial it up and walk towards the ringing. if it is, then NP-hard is P-easy. if we left it off, then NP-hard means we gotta look everywhere in the house."
Re: (Score:3, Informative)
(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.
Re:Let me ask a "stupid" question (Score:4, Insightful)
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.
Re: (Score:2)
One strange thing is that nobody seems to know of any useful polynomial algorithms where the exponent is very large. There are lots of n^2 algorithms, some n^3 ones. What about n^10
Re: (Score:2)
Two examples are given: decrypting encoded Internet traffice and decrypting encoded credit cards. If this problem is solvable by conventional computer, I see two major side-effects. First, it would mean we would have to be a lot more worried about the safety of our private information. since cracking current encryption would be a matter of short time. Second, it could mean a significant reduction in the funding and research for "unconventional" computer, the most prominent example being quantum computers.
As
Re: (Score:3)
Re: (Score:2)
Re:Let me ask a "stupid" question (Score:4, Insightful)
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.
Re: (Score:2)
I think a better way to put it is this....
Many security systems, like those used to protect online banking, online commerce in general etc, are based on these problems being very hard to solve. If it turns out that they are not as hard as we think, then we are not as safe as we think we are.... If we don't have honest people looking for the solution and letting everyone else know, then, we will not found out whether we are safe or not until someone dishonest figures it out and uses it against us.
Just puttin
Re: (Score:2)
And even if he doesn't do online banking, I'd be willing to bet his bank trades his money with other banks using encrypted electronic transfers.
My grampa keeps his money under his mattress, you insensitive clod!
Re: (Score:3)
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 l
Re: (Score:2)
How does the solving of problems like these really help the world?
Because solving this problem can help solve another problem that impacts the world more than the original problem.
Re: (Score:2)
I would be most grateful if you gave an example of that 'other problem' that impacts the world which could be solved. From your missive, I am assuming that the problem actually exists.
Thanks.
Re: (Score:2)
Re: (Score:3)
Re: (Score:2)
Computers can solve simple problems immediately. Difficult problems take a bit longer. If we could simplify difficult problems, computers could solve them immediately. One type of difficult problem which has a possibility to be simplified is the NP type.
The possibility is so small that he may be better to donate to a humanitarian cause. The humanitarian cause may help someone survive that can answer this question. Even if they can't, he at least helped them survive.
Re: (Score:2)
Now imagine the puzzle is "find the most efficient antenna", or "find the most aerodynamic car frame that has enough space inside", or "find the shortest description of this stock market data", and you start to get at the power of the thing. Forget public key decryption -- a large swathe of engi
Re: (Score:2)
Not a stupid question. In fact, you would have been justified asking this question back when Galois was doing his work on abstract algebra in the 1830s. Or when Fourier was doing his work on temperature a bit earlier than that.
Over a century later, the work of both Fourier and Galois has moved so far from the abstract and so deeply entrenched in the practical, consumer-applied engineering fields that it would be hard to name anything in technology that didn't at least consider the application of both.
Four
Re: (Score:2)
Your grandfather is likely aware of the role that encryption played in WWII, so use that. You say something like this:
After WWII, encryption became entirely dependent upon math to prove that, even with computers, some encryption schemes would be virtually impossible to break in any reasonable timeframe. In other words, as long as the math was safe, the encryption was safe.
Proving P = NP means that the math isn't safe anymore. It used to be safe because, given the state of mathematical knowledge at the ti
Re: (Score:2)
Re: (Score:2)
Though it should be noted that polynomial time doesn't nessacerally mean practical time.
Re: (Score:2)
Faster execution means:
1. Less polution of the earth ("Hah, carbondioxide is bullshit!" - yeah say that to Venus, lol)
2. Giving America ("Fsck yeah! Here to save the motherfscking day, yeah!") the upperhand in decoding terrorist communication so people's lifes can be saved.
This all is ofcourse not realy entirely true, but at least you can lie with a straight face and not feel completely guilty about it :)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
truly test the answer space
The problem is its both simple enough and high profile enough that it attracts cranks like moths to a flame, and stereotypically none of them have the ability to operate in an "answer space" even as large as high school algebra or maybe high school geometry.
Very much like the drunk whom loses their car keys in the dark alley, but decides to search under the streetlamp for the keys, "because the light is better under the lamp". It tends to be a bit of a waste of time. Having a billion drunks search under t
Re: (Score:3)
That just keeps getting funnier every time it's posted (Which is about 30 times in any P =? NP story.)
Re: (Score:2)
You ignored the P=0 solution, by assuming it wasn't in your third step..
Re: (Score:2)
P and NP are both sets.
Re: (Score:2)
Let's isolate the N.
N = P/P
if p == 0 then fail
Re: (Score:2)
Every time a notion of P=NP or P!=NP comes up on slashdot, about 30 or 40 people say the same thing... to be frank, it's getting tiring.
This might be a solution (and not the only one, even) if the notion of P = NP actually described a situation where P and N are supposed to be constants (and that the right hand side multiplied them together), and that the expression P = NP were actually intended to convey a notion of algebraic equivalence.
However, it is neither.
When discussing P's equivalence to NP,
Re: (Score:2, Interesting)
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.
Re: (Score:2)
You're missing the point: if P=NP, then any problem that is in NP (e.g., prime factorization) is also obviously in P (since, well, NP=P), and so, solvable in polynomial time. In fact, if P=NP, there is no "hard for NP", since it's all really P.
Maybe you're confusing it with the converse: if P!=NP, then, sure, it doesn't follow that it's hard to solve (for instance) prime factorization -- it might be in P, in NP-complete or neither.
Re: (Score:2)
Wrong. If P=NP, all problems in NP (including NP complete and Co-NP problems) are solveable in polynomial time.
Re:This will NO break any encryption algorithms... (Score:4, Informative)
Re: (Score:3)
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.
Re: (Score:2, Informative)
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)
Re: (Score:2)
What about this:
http://en.wikipedia.org/wiki/Fast_Syndrome_Based_Hash [wikipedia.org]
Unlike most other cryptographic hash functions in use today, FSB can to a certain extent be proven to be secure. More exactly, it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as Regular Syndrome Decoding.
Yeah I know it is just a hash...
Re: (Score:2)
Would somebody with half a clue PLEASE mod this post down???
It's just mis-information of the worst kind -- to lay people (even for CS grads that didn't take any computational complexity courses) it sounds right except that it isn't.
Where are my fucking mod points.....
Re: (Score:2)
And he's saying things that make absolutely sense to me, so I'll skip on the citations.
Re: (Score:2)
I hear this a lot. Are there any NP problems that are usually hard to solve?
Re: (Score:3)
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 ti
Re: (Score:2)
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no, since if it could be shown to be then this would prove that NP=Co-NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine.
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
You got that wrong. If P=NP, then NP=Co-NP, so your public key cryptosystems are broken. (Also, if P=NP, all problems in P are NP complete)