When i first read the cover article in the September Communications of the ACM, I had the feeling that this article was not ordinary and would raise much attention among computer science specialists and even the curious average reader. The subject of the article was very amazing and the reader could not resist the tempting Idea to wonder about this beautiful -Still Not Found- World of P=NP.

The article did Indeed took its promise and more than 10 times the usual number of readers downloaded this popular article. This success was also quoted by NY Times science and technology reporter *John Markoff* who highlights the allure of the P vs. NP challenge. He reports that if this grand challenge for theoretical computer science and complexity theory is proven, some of the hardest computing challenges may collapse, leading to burst of new economic and technological productivity.

Another reaction to the article was by Communications Editor in Chief *Moshe Vardi*. He predicts that to investigate the P vs. NP problem, computer scientists may have to start learning a very difficult mathematical field known as algebraic geometry, which offers some hope for proving or disproving the problem.

# Tag Archives: P vs NP

# The Too Beautiful World of P=NP !

* Lance Fortnow* wrote an amazing article in the

*entitled The Status of the P Versus NP Problem*

**Communications of the ACM Vol. 52**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!