http://www.technologyreview.com/articles/04/09/wo_garfinkel090104.asp?p=0
P is the set of problems that are easy to solve. Strictly speaking, it is the set of problems that can be solved in "polynomial" timeóthat is, in an amount of time that is roughly proportional to the size of the problem's description. Most of these problems are so easy, in fact, that we hardly even consider them to be problems at all. For example, multiplying two numbers together is a P problem: the solution can be found in polynomial time. Another P problem is searching for a book that's lost in your house. Even if all of your books are packed away in boxes in your basement, it's still an "easy" problem to solve, at least by mathematical standards: just open up every box and look. It might take you days, but if you can do a thorough search, you will find the book.
Factoring is an NP problem. Although there are various techniques for factoring large numbers, all of them involve searching through large numbers of, well, numbers. The difficulty of factoring large numbers is at the basis of the RSA encryption algorithm, which is built into practically every Web browser and is the basis of most e-commerce.
There exists a large number of NP problems that can be thought of as "perfect" or "complete." Each of these so-called NP-complete problems encompasses everything that it means to be an NP problem. That means that if a solution for any NP-complete problem could be found that could be solved in polynomial time, then a short-cut solution could be found for every NP problem.
In practical terms, that would spell the end of encryption as we know it.
No comments:
Post a Comment