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: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 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.
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:Let me ask a "stupid" question (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, 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:This will NO break any encryption algorithms... (Score:4, Informative)
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:This will NO break any encryption algorithms... (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)