Hacker News new | past | comments | ask | show | jobs | submit login

If P=NP, then conventional cryptography would be impossible. In particular you would have no public key cryptography so it would not be possible to transmit information securely over an unsecure channel without sharing a some sort of key beforehand. Think of what this will do to online transactions which rely on information like credit card numbers being transmitted securely. I'm sure other areas of the economy would be vastly affected too.

The one form of cryptography that would still be possible is quantum cryptography. But if I recall correctly, that requires that two parties already hold some shared secret before communicating.

Edit: In addition although it would be possible to detect if someone is eavesdropping over your communication, you still wouldn't have the privilege of being able to communicate securely regardless of whether your message is being recorded. This of course presumes that not only P=NP, but an efficient polynomial time algorithm exists for NP problems i.e. one which is say linear or quadratic or even cubic time.




If P = NP then factoring numbers may be easy in such fashion that factoring numbers is not really that easy. N^749 is still polynomial time.


Your second part contradictions your first.

P=NP in a completely real world intractable way. And if P=NP, one would guess it would be in such an intractible fashion, since otherwise the algorithm would have found it's way into nature or something.

Most researcher think P!=NP to begin with, so if it was proven, very little would change. So it's likely any proof regarding P and NP will have little direct impact, though it might have a big impact just by the mathematical formalism it creates.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: