Lance Fortnow's guest appearances

Lance Fortnow

Smart People Podcast

New Books in Mathematics

Inspired by Math!

New Books Network

Princeton UP Ideas Podcast

Leila Schneps

Tim Chartier

Chuck Adler

David Reimer

Alfred Posamentier

Coralie Colmez

Seth Stephens-Davidowitz

Al Cuoco

Colm Mulcahy

Sue VanHattum

Ian Stewart

Joe Navarro

Michael Bungay Stanier

David Burkus

Adam Grant

OwlTail

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

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 <a href="https://megaphone.fm/adchoices" rel="nofollow" target="_blank">megaphone.fm/adchoices</a>

Lance Fortnow wrote a great book about the P/NP problem for a general audience. We discuss the problem, its importance, its interest to Lance, how difficult it is to solve, what some of the difficult problems are, and a bunch more.

Lance Fortnow - Inspired by Math #28

Today we’ll be discussing Lance Fortnow‘s bookThe Golden Ticket:P, NP, and the Search for the Impossible (Princeton University Press, 2013).The book focuses on the challenges associated with solving problems requiring significant computation, such as “What is the largest group of Facebook users, all of whom know each other?”If it is shown that all computational problems can be solved relatively easily (this is known as showing that P=NP), then such problems as finding a cure for cancer and other diseases would be much more easily solved. Listen in and find out how. Learn more about your ad choices. Visit megaphone.fm/adchoicesSupport our show by becoming a premium member! https://newbooksnetwork.supportingcast.fm/mathematics

Today we’ll be discussing <a href="http://lance.fortnow.com/" rel="nofollow" target="_blank">Lance Fortnow</a>‘s book<a href="http://www.amazon.com/dp/0691156492/?tag=newbooinhis-20" rel="nofollow" target="_blank">The Golden Ticket:P, NP, and the Search for the Impossible </a>(Princeton University Press, 2013).The book focuses on the challenges associated with solving problems requiring significant computation, such as “What is the largest group of Facebook users, all of whom know each other?”If it is shown that all computational problems can be solved relatively easily (this is known as showing that P=NP), then such problems as finding a cure for cancer and other diseases would be much more easily solved. Listen in and find out how. Learn more about your ad choices. Visit <a href="https://megaphone.fm/adchoices" rel="nofollow" target="_blank">megaphone.fm/adchoices</a>Support our show by becoming a premium member! <a href="https://newbooksnetwork.supportingcast.fm/mathematics" rel="nofollow" target="_blank">https://newbooksnetwork.supportingcast.fm/mathematics</a>

Lance Fortnow, “The Golden Ticket: P, NP, and the Search for the Impossible” (Princeton UP, 2013))