# Book review: The Golden Ticket: P, NP, and The Search For The Impossible

While reading Scott Aaronson’s blog here, I was introduced to a book called The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow. It is a book explaining the most important question in Computer science and Mathematics, is P = NP? Alternatively, you can watch Scott Aaronson talk about P = NP in this TED video.

P stands for problems that we can solve easily using computer. NP stands for problems that we cannot solve easily using computer. Example of NP problem is finding the factors of a large number. For example, we multiply two numbers

84,578,657,802,148,566,360,817,045,728,307,604,764,590,139,606,051
and
97,823,979,291,139,750,018,446,800,724,120,182,692,777,022,032,973
to get
8,273,820,869,309,776,799,973,961,823,304,474,636,656,020,157,784,206,028,082,108,433,763,964,611,304,313,040,029,095,633,352,319,623.
Multiplying the two numbers is easy, however finding the two numbers from the large number is hard. If someone is able to prove that P = NP, it means we can use our computer to find the factors from a large number as easily as multiplying the factors to get the large number. If P = NP, we can find solutions to questions as easily as we can test the solution. Chapter 2 of the book: The Beautiful World envisions a world where P is equals to NP, where we can program our computers to find the cure of AIDS, make movie with simulated actors, find criminals, etc.

P = NP problem is so important that Clay Math Institute decides to offer 1 million dollar to anyone who can prove or disprove it and is one of the seven Milliennium Problems (One of which had already been solved: Poincaré Conjecture). However, it is regarded by Scott Aaronson as the most important question among the seven, because if you can prove that P is indeed equals to NP, you can program your computer to find the solutions to the other six questions.

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