The P versus NP problem has appeared in shows like The Simpsons and Numb3rs, and in the SIMS 3 video game. What is the P versus NP problem and why should we care?
This past Thursday (Sept. 12) at the Math for Everyone lecture series, Lance Fortnow, Professor and Chair of the School of Computer Science at the Georgia Institute of Technology, gave a presentation on the importance of the P versus NP problem and how, if solved, could dramatically affect our everyday lives.
Fortnow explored the history and importance of the P versus NP problem using several non-technical examples, one of which was a robotic hand. Throughout the lecture, Fortnow used the robotic hand as a metaphor to demonstrate how P ≠ NP represents problems that cannot be solved. Although we know what the solution to a problem should be, which in this case would be crafting a human-like robotic hand, the solution to crafting a fully functional human-like robotic hand cannot be fully met.
Lance Fortnow
Now, if P=NP, we could find solutions to search problems as easily as checking whether those solutions are good. This would essentially solve all the algorithmic challenges that we face today and computers could solve almost any task. Using Fortnow’s example, if P=NP, then the robotic hand would be capable of doing anything an actual human hand can do. If we could find the solution to show that P=NP, we could help cure diseases like cancer and revolutionize society.
The Clay Mathematics Institute (CMI) of Cambridge, Mass. established seven Prize Problems, one of which is the P versus NP problem. The CMI Board of Directors designated a $7 million prize fund for the solution to these problems, with $1 million allocated to the solution of each problem.
Fortnow has also published a book about the P versus NP problem, called P, NP and the Search for the Impossible.
Math for Everyone is a series of math-related talks, specifically for undergraduates. The next Math for Everyone talk, How to Use Your Mathematics Degree After Notre Dame, will be held Thursday, October 10, 2013 at 5:00PM in 101 Jordan Hall. All undergraduates are welcome to attend.