Lance Fortnow, PhD - Author of The Golden Ticket: P, NP, and the Search for the Impossible, professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology, served as the founding editor-in-chief of the ACM Transaction on Computation Theory, served as chair of ACM SIGACT and currently sits on the Computing Research Association board of directors. He served as chair of the IEEE Conference on Computational Complexity from 2000-2006.
It's time to bend your brain and mess with your mind with one of Smart People Podcast's most intellectual and in-depth interviews EVER!
Did you know that there is a problem known as the "P versus NP problem" that, if solved, could cure cancer, predict the weather, rid us over poverty, and pretty much change the entirety of our world? Our guest this week goes so far as to say, "What we would gain from P = NP will make the whole Internet look like a footnote in history!"
But there is one pretty big problem.
We have had the best and brightest people in the world (including this week's guest) working on this problem for decades and they still can't even decide IF it can be solved! Due to the complexity and positive implications that a solution would have on our society, the "P versus NP problem" is one of the seven Millennium Problems for which the Clay Mathematics Institute will give you one million dollars if you can prove it.
We are going to leave the heavy lifting to Lance, but as a primer, P versus NP basically states that if these two variables are equal, we would be able to solve every complex issue with a very simple equation. Oh, you want more than that? Ok fine. P stands for "Polynomial Time" and represents the entire class of problems with efficient solutions. NP stands for "Nondeterministic Polynomial-Time" and represents the entire class of the very hardest, most difficult problems. Therefore if the 2 were equal, we would be able to apply this algorithm to all of our most difficult, complex problems and come up with a simple solution.
Believe us, even those that aren't math or computer savvy will love to hear the way that Lance breaks down such a complicated idea into a real life scenario. Imagine the possibilities if P = NP! (I never thought I would write that in my life)
Lance Fortnow is professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology. His research focuses on computational complexity and its applications to economic theory.
Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Georgia Tech in 2012, Fortnow was a professor at Northwestern University, the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. Since 2007, Fortnow holds an adjoint professorship at the Toyota Technological Institute at Chicago.
Fortnow's research spans computational complexity and its applications, most recently to micro-economic theory. Fortnow's survey The Status of the P versus NP Problem is CACM's most downloaded article. Fortnow has written a popular science book The Golden Ticket: P, NP and the Search for the Impossible loosely based on that article.
Learn more about your ad choices. Visit megaphone.fm/adchoices