Content area
Full text
THE GOLDEN TICKET: P, NP, AND THE SEARCH FOR THE IMPOSSIBLE by Lance Fortnow Princeton University Press, 2013, 176 pp. ISBN: 978-0-691-15649-1
Does P = NP? Are there efficient algorithms to answer some of the most difficult questions in mathematics? This simple question is so important to mathematics, computer science, and the modem world that the Clay Mathematical Institute has made it one of its seven Millennium Prize Problems. The person who comes up with a definitive answer to the question will earn $1,000,000. P and NP are classes of problems that can be solved on computers in two different but related ways. A formal mathematical explanation of the P = NP question requires knowledge of formal language theory, automata theory, and computational complexity theory.
The Golden Ticket: P, NP, and the Search for the Impossible explains the P = NP question to the general reader in non-technical terms. The author, Lance Fortnow, is the Chair of the School of Computer Science at Georgia Tech and a well-known authority...