Lance Fortnow’s “The Golden Ticket: P, NP and the Search for the Impossible” tells the story of P vs. NP, a famously unsolved question in computer science.
Much of modern computer science relies on the assumption that P≠NP, that certain computational problems are so hard as to be impossible for any existing processor to solve. The assumption that these trickier problems (NP) are fundamentally different from ordinary ones (P), undergirds encryption, secure voting and e-commerce, which require would-be code-breakers to solve one of the harder problems in order to gain access to the protected information. So strong is the assumption that P≠NP, that most aspiring hackers do not even try to design algorithms that will undertake these computations. But even though the vast majority of computer scientists assume that P≠NP, the consequences of a proof that P=NP could be profound. Aside from implying that cryptography as we know it is insecure, such a result would give biomedical scientists a glimmer of hope toward better cancer treatments (protein folding is a hard problem), among myriad other applications.
Fortnow, a professor of computer science at Georgia Tech, details the history of P and NP in terms a general audience can understand, and in so doing communicates the profundity of some of the issues that arise in data scientists’ daily work.
