|
I heard about this, but in all honesty, anything more than "Complexity Theory for Dummies" is well beyond my comprehension. Polynomial time (P) is fairly easy for me to comprehend, but I can't fully wrap my head around non-deterministic polynomial time (NP), because I have a hard time understanding exactly what the difference is between a non-deterministic Turing machine and a quantum computer. The difference seems to be something like the difference between non-deterministic operands vs. non-deterministic operations, but I can't quite grok it.
As I understand it, one of the biggest implications of the P=NP debate is with respect to public-key cryptography. It's believed (though as far as I know, unproven) that the problem of factoring numbers belongs to the NP class. Which is to say, it is a fundamentally "difficult" problem for any deterministic computer. The lower bounds on efficiency for this type of problem are such that no computer will ever be able to solve them in a reasonable length of time if the number in question (and thus the factor space we have to search) is sufficiently large.
However, verifying that a number is prime belongs to the P class of problems. Relatively speaking, we can do this very quickly. Thus, we can generate two very large prime numbers and multiply them together, and we can do this very quickly. However, someone trying to factor the resulting prime back into its two prime factors will have a very hard time of it. Public key crypto systems rely on this being true.
If factorization truly does belong to NP, and if P=NP, then a sufficiently ingenuous mathematician could theoretically discover a shortcut -- a way of transforming the NP-class factorization problem into a P-class problem. This would enable us to solve factorization efficiently without the need for non-deterministic Turing machines (or even quantum computers), which would thoroughly undermine modern key distribution.
Of course, public key cryptography methods weren't publicly discovered until the 1970s, so it's not as though this would send us back to the stone ages, exactly, but key distribution was becoming an intractable problem even then. Today ... it's really inconceivable due to the extent that we rely on asymmetric crypto and key exchanges being secure. Secure communications as we currently know them would come to grinding halt if someone found a way to factor numbers in polynomial time.
In the mean time, Deolalikar's proof is going to be at least as controversial and difficult to substantiate as Wiles' proof of Fermat's Last Theorem. If it holds up, it's definitely one for the history books, and a lot of people are going to be letting out a big sigh of relief. On the other hand, it will mean that certain highly vexing problems are likely to remain forever beyond our reach, even if effective quantum computing becomes a reality in the near future.
_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.
|
Login
Register
FAQ
Search
