, 2 min read
The most important Theoretical Computer Science problem is inconsequential
Some consider the P = NP problem to be the most important Theoretical Computer Science problem. It asks whether all problems whose solution can be verified quickly, can also be solved quickly. If you can answer this question, you win one million dollars.
The catch is that quickly is defined as in polynomial time. Thus, if you can solve a problem in time O(nx) where x is the number of electrons in the universe, then you are quick.
This is an annoyingly silly definition. Bubble sort is in O(n2). Yet, try replacing all sorting within Google’s infrastructure by this quick algorithm. Google would die.
Lance Fortnow asks us to take for granted that proving P = NP implies we have fast algorithms for all NP problems. William Gasarch just predicted that proving P ≠NP would also help real world of algorithms. Unknowingly to them, Zeilberger proved that P=NP on April 1, 2009. Yet, nothing happened. (He was kidding. Or was he?) Anyhow, enough with the dogma! While intermediate steps in the solution of the problem might be critically important to our understanding of computation, knowing that P = NP is inconsequential technologically.
This is as silly as claiming that sending men to Mars will cure cancer. It might very well that the research necessary to send men to Mars might lead to major breakthroughs, but whether we go to Mars or not has nothing to do with cancer.
Yes, please send men on Mars. Yes, please work on the P = NP problem. But stop claiming the answer would change the world.
Further reading: See my older post Is P vs. NP a practical problem?. Dick Lipton wrote a related blog post as well.