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..."
Not to burst anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is not, since if it could be shown to be then this would prove that NP=Co-NP. This would be a surprising result since it would prove that the graph isomorphism problem is in NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine. Symmetric key cryptosystems such as 3-DES and AES should also be fine. They aren't known to be NP complete problems, and in fact there are no theoretical guarantees about their security at all. They just seem to create messages that are difficult to decrypt given our current cryptoanalytic abilities. In fact, there are NO known NP-complete crypto schemes around today. TL;DR - No encryption schemes will be broken if it is proved that P=NP