P vs. NP is a problem at the forefront of computer science. Until now there hasn't been a book written for a general audience that introduces the problem and its importance. Lance Fortnow has authored such a book. Lance I discuss the problem, the book, why he wrote it, and what it takes to write such a book in a way that doesn't scare most of us away. And, we take a few detours into talks about computer science and programming early microcomputers.
About Lance Fortnow
From the author's web-site:
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. He also holds an adjoint professorship at the Toyota Technological Institute at Chicago.
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.
Fortnow's research spans computational complexity and its applications, most recently to micro-economic theory. His work on interactive proof systems and time space lower bounds for satsifability have led to his election as a 2007 ACM Fellow. In addition he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97.
Among his many activities, Fortnow 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 and the council of the Computing Community Consortium. He served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog since 2002, the first major theoretical computer science blog. He has thousands of followers on Twitter.
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.
About "The Golden Ticket"
From the Princeton University Press web-site:
The P-NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives.
The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.