Lance Fortnow wrote an amazing article in the Communications of the ACM Vol. 52 entitled The Status of the P Versus NP Problem
I Just found the bellow article passage amazing and wanted to know what would people think about it:
In 2000, the Clay Math Institute named the P versus NP problem as one of the seven most important open questions in mathematics and has offered a million-dollar prize for a proof that determines whether or not P = NP.
To understand the importance of the P versus NP problem let us imagine a world where P = NP. Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems.
- Many focus on the negative, that if P = NP then public-key cryptography becomes impossible. True, but what we will gain from P = NP will make the whole Internet look like a footnote in history.
- Since all the NP-complete optimization problems become easy, 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.
- 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.
- P = NP would also have big implications in mathematics. One could find short, fully logical proofs for theorems but these 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 reasonable length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with $1 million check but with seven (actually six since the PoincarÃ© Conjecture appears solved).
Don’t get your hopes up. Complexity theorists generally believe P â‰ NP and such a beautiful world cannot exist.
Well, I tend to agree with them for such a world would be really too much perfect!