, 1 min read
Is P vs. NP a practical problem?
Here’s a recent quote from ACM TechNews:
The ACM’s Special Interest Group on Algorithms and Computing Theory honored Rudich and Razborov for their contributions to addressing the P vs. NP problem, which involves the computational complexity behind the security of ATM cards, computer passwords, and electronic commerce.
The implication here is that the P vs. NP problem is important for computer security. This seems like saying that General Relativity is important to establish a mining operation on the Moon.
This may be a naïve question, but would proving that P=NP (or disproving it) change anything in computer security?
Yes, I can appreciate the fundamental nature of the P vs. NP problem. But does it have any practical consequences?
Note that whether a problem requires 2n or n150 time will not make much difference: both are intractable.
As a database researcher, anything requiring n4 time is already intractable. Don’t believe me? If n is 1 million and a computer can do 1012 operations per second, it takes 30 thousand years to solve a n4 time problem. I am not even going to get in the constants: what if your complexity is 10120 n?
Oh yes! Please, give prizes to anyone who makes progress toward the P vs. NP problem, but I am still waiting for the practical implications.
(If I am making a crucial mistake here, please tell me! I want to know.)
Update. André pointed me to a web site that pretty much says that P vs. NP is not so important for cryptography.