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..."
Re:Let me ask a "stupid" question (Score:4, Insightful)
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:Let me ask a "stupid" question (Score:1, Insightful)
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?
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: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: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.
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 fuck over yourselves.
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.