Review: The Golden Ticket

What problems cause even the most powerful computers difficulty? When should we settle for a best effort, using a heuristic algorithm rather than the absolute best result? How is all this worth one million dollars?

The Golden Ticket - Lance Fortnow

I’ve known about the P vs NP problem for a long time, but my memory of the specifics were hazy. It’s not since university that a course introduced us to Big O Notation, explaining about the difference between problems for which there is a likely efficient algorithm to solve them no matter how many variables and those that take an exponentially longer time to solve as more data is added.

Realising that the majority of the class were going to join industry rather than follow the academic path, his point was to try to get us to understand that some problems were difficult, and in fact would not be possible to solve in a reasonable amount of time.

The lecturer envisioned a boss, somewhere in the future, asking one of us to build a faster algorithm for a business function. In that case, and since we had taken this course, we would be able to say “The problem you are trying to solve is equivalent to this NP-complete problem, and therefore you are asking the impossible. At the very least, it is a problem that no other computer scientist has solved to date.”

Looking back over my career, I don’t think I’ve ever had an opportunity to prove that something I was asked to implement was equivalent to one of these problems. But there have been times when the code that I produced simply did not work fast enough.

While I had never completely forgotten about the NP-complete and NP-hard problems, I had largely ignored scoring the algorithms we produced using Big-O Notation. Since reading this book, I’ve been reminded that perhaps checking the algorithm should be a factor in analysing slow running algorithms.

What is The Golden Ticket?

The book introduces one of the existing Millennium Problems, each of which will earn the person that completes its proof one million dollars. Of the seven original prizes only one has been solved. The problem this book focuses on is the P vs NP Problem.

P problems are those were the solution can be found in polynomial time or better. For example, sorting a list. It’s easy to do and easy to verify the solution.

The solution to NP problems, non-deterministic polynomial-time, can be verified easily, however, finding the solution takes time and grows exponentially as more items are added.

A popular example in modern times is the Sudoku craze. The nine by nine grid is reasonably easy to solve. But when you increase to a sixteen by sixteen grid it gets significantly harder. But if you are presented with the finished grid, it does not take long to check it is all correct. As the number of distinct possible values increases, the solving starts to become intractable, but verification remains relatively easy.

The P vs NP problem challenges us to find a proof that there is no efficient algorithm to reduce NP problems to P problems. Another solution would be to find the opposite - a means to convert a NP problem into a P problem. Doing either will win the million dollar prize.

Should you be able to prove the latter, that there is a way to prove that P and NP are equivalent, than you would automatically be able to solve the other five remaining millennium prizes, possibly taking their prize money also. The idea of a Golden Ticket is based on this.

What’s more is that this proof would change the world as we know it launching humanity on a new trajectory that would make the industrial revolution look like a trivial jump. It’s a tantalising prize and is why this remains an interesting problem almost half a century since it was first articulated.

The Possible Future

It is unlikely that anybody can prove that P = NP. Lance devotes a chapter to how future history might unfold if this were possible. The possibilities are amazing.

I recently read Arthur C. Clarke's The City and the Stars which depicts a human future at least a billion years ahead, where humanity has overcome many challenges and achieved perpetual life, albeit at the cost of staying a resident of the city of Diaspar. It was a strange parallel to the future depicted should P be equivalent to NP.

In such a world all problems would ultimately get reduced smaller and smaller until they were easy. Expensive genetic analysis for example could be done in a fraction of the time and with much lower cost, helping doctors and scientists to resolve genetic issues almost as soon as diagnosing the issue. In fact the diagnosis would probably be done before the patient even knew there was an issue.

The author suggests sports might lose some of the intrigue, the computers being able to predict the winners before seasons even begin. But by cleverly scheduling the fixtures, suspense can be withheld right up to the last few games of a season.

Travel to the planets would also become a possibility. It seems that Space-X has already put us on that trajectory with the launch of its Heavy Falcon. The restriction to our own solar system might be removed much earlier than otherwise likely.

The world where P=NP is a world in which magic can seemingly exist; at least from our perspective. Think Neanderthal in modern New York City. But realistically this is just fantasy as the real proof will probably be that P ≠ NP

Hard Problems

To illustrate the type of problems involved, the book depicts a made up world called Frenemy in which people are either your friend or your enemy - there is no in between. This world is used to describe and demonstrate problems and give some context to what the solution or proof to the P vs NP probable would need to contain.

There is a special category of NP problems called NP-complete. It can be proved that any of these problems can be converted into any other NP-complete problem. Finding an efficient, i.e. polynomial time, solution to one will solve all the problems there.

There are also NP-hard. All NP-complete problems can be reduced to NP-hard ones. A solution in polynomial time for any NP-hard solution would basically solve all NP problems and mean that P=NP after all.

Possible Solutions - Quantum

Some possible directions are given on where the proof to this problem might come from. One of these, quantum computing, is not yet a reality but people are still building algorithms and hoping that a working machine is not to far away.

I’ve always been a bit wary of Schrödinger’s cat, the one that is stuck in a box with poison and may be alive or dead at any state, but checking may change this as the cat may get out. This has never really sat well with me and I was glad when a different approach was used to introduce quantum computing in The Golden Ticket.

Consider someone who has recorded a game, baseball is the example in the book, and while watching it approaches the final few minutes. At that stage either possibility is still alive as far as the viewer is concerned, a win or loss for their team, although the event has in reality concluded.

Consider a second person who also recorded the game and is at the same position. They are somehow entangled with the first viewer. Nothing can change what both eventually find out from their recordings and viewing destroys one of the possibilities. A lot nicer than locking a cat in a box!

What’s intriguing about quantum physics to me is the possibility of its use to teleport things or people from one location to another. The trick is to entangle quantum bits and carefully separate them, moving one set to the destination. That’s the hard part, apparently!

Amateur Maths

P vs NP is a tantalising puzzle and one that attracts some interest from amateur mathematicians. Probably not as much as did Fermat’s Last Theorem, the beauty of which lay in the simplicity of its definition. But with one million dollars up for grabs it will stay in the minds of any who hear about it.

The Golden Ticket is an entertaining read for anyone who has an interest in the more theoretical end of computer science, tracing the history of the P vs NP problem as it emerged independently in both the East and West during the Cold War.

While you may not get enough information to solve the puzzle, you should certainly understand the problem by reading this book. And you never know, a flash of inspiration might be all this problem needs to crack it wide open.

The following is an affiliated link for amazon.co.uk - should you choose to purchase this book after following the link, I will receive a commission. Please feel free to search on independently for the book if you are not comfortable with this: