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.

References to P=NP in The Simpsons and Futurama
References to P=NP in The Simpsons and Futurama

The book also deals with quantum computer. Quantum computer can help solve some of the NP problem such as the factoring problem using Shor’s algorithm that take advantage of the fact that this specific problem has an algebraic structure. This algorithm can only solve this specific NP problem and not all NP problem, this means Quantum Computer cannot solve all NP problem, and NP problem still remains hard to solve.

In the future, it is predicted parallel computing will be more important as Moore’s law starts to break down. Moore’s law states that the number of transistors on integrated circuit doubles every 18 months, hence increases the computing power. This starts to breakdown as transistor becomes smaller and overheating issue starts to arise. Hence, the use of parallel computing, computers can compute many things at once.

Besides that, in the future, dealing with big data will be important. Be it social media information from Facebook, Twitter, scientific data from Large Hadron Collider, or DNA sequencing data, we are getting a lot of information and we have to deal with it and make use of it. Google uses big data to provide better search and translation, perhaps one day we can install chips in our car, and uploads that information into a computer system that calculate and coordinate how each car should move to minimize traffic jam (This may be useful if used together with self driving car).

Lastly, we will see the networking of everything. Everything from toaster, clothes, shampoo, etc will be fitted with small low-cost chips. They can guide our daily lives by telling us what to wear to get the best appearance, remind us when the milk becomes sour, automatic credit deduction when we walk our of mall so that we do not have to go through cashier, etc.

Leave a Reply