Books The Golden Ticket

Published on October 31st, 2013 | by Travis Korte


The Golden Ticket: P, NP and the Search for the Impossible

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.

Get the book.

Tags: , , , , ,

About the Author

Travis Korte is a research analyst at the Center for Data Innovation specializing in data science applications and open data. He has a background in journalism, computer science and statistics. Prior to joining the Center for Data Innovation, he launched the Science vertical of The Huffington Post and served as its Associate Editor, covering a wide range of science and technology topics. He has worked on data science projects with HuffPost and other organizations. Before this, he graduated with highest honors from the University of California, Berkeley, having studied critical theory and completed coursework in computer science and economics. His research interests are in computational social science and using data to engage with complex social systems. You can follow him on Twitter @traviskorte.

Back to Top ↑

Show Buttons
Hide Buttons