Cryptography If Pnp Is True

There has been a LOT of debate as of late regarding Vinay Deolalikar’s P != NP research paper. I’m not going to lie, I don’t understand very many of the concepts described in his P!= NP paper (released August 6, 2010). I’m still learning many of the theoretical Computer Science concepts, but I found many of the debates brought up by this paper very interesting. One of the interesting debates involves cryptography.

Cryptography is the practice and study of hiding information via combinations of mathematics, computer science, and engineering. It is often used to prevent unwanted third parties from viewing certain data. The debate regarding this paper and Cryptography that has arisen basically says that if P=NP then all current cryptographic implementations would become theoretically much more vulnerable. Cryptography relies on certain problems being difficult. A good and efficient solution to certain NP complete problems could break many existing cryptographic systems, for example the NP complete problem 3-SAT and public-key cryptography. These cryptographic systems would need to be updated or replaced with something stronger.

Although Cryptography could face many problems, if P=NP there could be many benefits for other problems in mathematics. Efficient solutions to other difficult problems would have huge implications for problems such as protein structure prediction or various logistics problems. Proving some mathematical theorms can take decades of research. A method that is proven to find proofs to these theorms would put an end to this problem.

Additional Resources

Written on August 28, 2010