Speaker:
Lance Fortnow
Professor and Chair, School of Computer Science
Georgia Institute of Technology
Abstract
It is the most important open question in computer science, if not all of mathematics. Though not widely known and understood, it has been explicitly mentioned in shows like The Simpsons and Numb3rs, and in the SIMS 3 video game. There is a million dollar bounty on its solution and an incorrect proof was even discussed in the New York Times last summer. A solution to this problem could transform computation and society in way that would make the Internet a footnote in history.
This is the P versus NP problem, defined by Steve Cook in 1971 and named after the technical terms (Polynomial-Time and Nondeterministic Polynomial-Time) that the letters P and NP represent. P = NP means that we can find solutions to search problems as easily as checking whether those solutions are good but it means much more. It would essentially solve all the algorithmic challenges that we face and allow us to have computers solve almost any task we can give it. It would help cure diseases and transform every aspect of society from communication, transportation, manufacturing and even entertainment.
In the much more likely scenario that P is different than NP. We will have algorithmic problems that cannot be met; but even in that case, many people have developed tools to deal with these problems as best as they can.
This talk will explore the history and importance of the P versus NP problem via several non-technical stories and examples.
Math for Everyone is a series of math-related talks and discussions, especially for undergraduates. Events conclude with snacks and refreshments. Everyone, from Fields medalists to math phobes, is welcome to attend.