[My Computational Complexity Web Log] What if P = NP?
A New York Times essay looks at the hardness of understanding math. The essay quotes from the book The Millenium Problems by Keith Devlin which describes the seven million-dollar Clay Mathematical Institute Millenium Problems including the P versus NP question. So I took a peek into Devlin's book.
Devlin doesn't hide his feelings about the P versus NP problem as "the one most likely to be solved by an unknown amateur." He does make a point that if P = NP we can break RSA and "the current dependence of the Western economies on secure communications over the Internet demonstrates just how high are the P = NP stakes."
Let's play make believe and assume P = NP in a strong way, say that we can find satisfying assignments of Boolean formula in nearly linear time with small constants. It will have a dramatic influence on the Western economy but not at all in the way Devlin perceives. We'll lose public-key cryptography but what we will gain from it will make the whole internet look like a footnote in history.
Learning becomes easy by using the principle of Occam's razor--we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.
Everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface.
P = NP would also have big implications in mathematics. One could find short fully logical proofs for theorems but these fully logical proofs are usually extremely long. But we can use the Occam razor principle to recognize and verify mathematical proofs as typically written in journals. We can then find proofs of theorems that have reasonably length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with one million-dollar check but with seven.
Posted by Lance to My Computational Complexity Web Log at 5/25/2004 02:31:05 PM