book_cover

The book titled, “The Golden ticket”, gives a non-technical introduction to the most important unsolved problem in the computer science,“Whether P = NP?”. If you are curious about knowing this problem and do not want to slog through the dense math behind it, then this book might be a perfect introduction to the problem. The author makes sure that the concepts are introduced using plain English and nothing more. By the time you are done with the book, I bet you will start appreciating a few if not all the NP-complete problems that are yet to be cracked. In this post, I will try to summarize briefly the main points of the book.

Preface

The author starts off by stating the P vs. NP challenge as one of seven recognized Millennium prize problems by the Clay Mathematical Institute. P refers to the class of problems that can be solved efficiently using computers. Efficient here means using a polynomial time algorithm. NP refers to the class of problems to which we would like to find the best solution. Another way to state NP class of problems is the set of problems for which a we can efficiently check its solution. So, the million dollar question is, whether the set of all problems that can be solved efficiently and the set of problems that for which we can efficiently check its solution are one and the same. For someone who is coming across this for the first time, it might be a bit puzzling. Why is “having a quick algo for verifying a solution?” for a problem important ? What’s the connection between an algo used for verifying a solution to a problem and an algo used for solving the problem? This question is answered elaborately in the chapters to follow.

The Golden Ticket

The author clarifies the intent behind using the phrase, “The Golden Ticket”, in the title of the chapter. It acts as a cue to the story of a candy manufacturer who places a handful of golden tickets inside chocolate bars, hidden among tens of millions of bars produced each year. The finders of the golden tickets will get a free factory tour. If you want to desperately find the golden ticket, How do you find one ? No matter how you find the ticket, you will need a considerable amount of time, money and luck. This is a nice example to have in mind as it reminds the user that there are problems that we encounter in our lives for which the solutions take considerable amount of time, no matter how much computing power you have.

The chapter introduces the traveling salesman problem, a problem that involves selecting the best route to minimize the total distance travelled. The problem looks deceptively simple. In fact for 48 city tour, if you intend to check all the tour combinations on a laptop, it will take 10 trillion trillion times the current age of the universe. There are many problems such as TSP that fall under NP category, i.e the class of problems for which we want to find the solution. P refers to the class of problems for which one can find an efficient solution. P=NP means we can quickly find a solution to all the NP problems. P ≠ NP means we can’t. Do we come across NP problems in real world or Are they just a figment of imagination for a pure mathematician ? Well, NP-complete problems are everywhere. For example, when you plug in your start and end points in a GPS system, the possible combinations of routes are too many for one to do a exhaustive search. Instead the GPS finds the best route heuristically.

The chapter ends with a list of problems that the author promises to answer via this book, i.e.

  1. What are P and NP?

  2. What kinds of problems do they capture?

  3. What are NP-complete problems, the hardest of all search problems?

  4. How do these problems capture the P versus NP question?

  5. How did we get to P and NP?

  6. How do we approach a proof that P ≠ NP ?

  7. Kurt Gödel showed that mathematics cannot solve every problem. Can similar techniques show that there are search problems we can’t solve quickly?

  8. What good can come out of P ≠ NP?

  9. Can future computers based on quantum mechanics make the P vs.NP problem irrelevant?

  10. What about the future? The great challenges of computing still lie ahead of us. a) How do we deal with computers that have to work together to solve problems? b) How do we analyze the massive amount of data we generate every day? c) What will the world look like when we network everything?

The Beautiful World

The author gives a futuristic tour of various domains, if P=NP were to be proved conclusively. There are examples on the brighter side as well as the darker side. Cancers can be cured, Sports as we know it will get completely revolutionized, Politics and the whole activity of campaigning will turn in to a game of algos, Police would be crack cases in days what used to take months and years. However the dark side of it is that machines will become so damn powerful that there will be privacy issues, public key-private key encryption will be falter and ecommerce will fall back to a more primitive encryption, more people will lose jobs as machines become efficient in doing cognitive jobs too. These scenarios help a reader to visualize the future if ever P=NP were to be proved.

P and NP

The author uses an example of a fictional land,“Frenemy” to illustrate various types of problems that fall under class P. What does Frenemy look like?

Frenemy has about 20,000 inhabitants. Every individual seems normal, but put two in close vicinity and a strange thing happens. Either the two take an instant liking to each other, immediately becoming the best of friends, or they take one look at each other and immediately become the worst of enemies. Despite the Frenemy name, two inhabitants are never observed taking a middle ground; they are always either close friends or distant enemies.

If one were to check whether six degrees of freedom holds good for any two individuals in Frenemy by brute force, i.e. counting all the possible links of six links, this problem will take more than 100 years to compute. There are simple algos that make such tasks computationally tractable. To find the lengths of separations between all pairs of inhabitants of Frenemy, one can use Floyd-Warshall algorithm, which will compute all these distances in about eight trillion computation steps. Given the modern day computing power of about billion operations per second, this can be done pretty quickly. The author uses various types of examples using Frenemy citizens to illustrate various problems and algos.

  1. Claude Berge Algorithm

  2. Jack Edmonds Algorithm - In a paper, he was the first to use the term,“algebraic time” to capture the intuitive idea of efficiency of an algorithm. Later the term was replaced by “polynomial time”. The class of problems that can be solved in “polynomial time” is referred to as P.

  3. No mathematically rigorous proof that shows a map can be colored using four colors.

  4. Algorithm for finding Eulerian path

  5. Min-cut Problem in graph theory

  6. No polynomial time algo for finding Cliques

  7. No polynomial time for finding Hamiltonian Cycles

  8. No polynomial time for Max-cut problem

  9. No polynomial time for coloring maps

The last four of the above problems, as they stand today, have no polynomial time algo to find the solution. However given a potential solution, you can easily check whether it is indeed a solution or not. The class of problems such as these is called NP.

There are a ton of problems for which we do not know how to find the solutions quickly. The author goes on to give a list of NP problems in various fields

  1. Genomics - Current DNA sequencing technologies can only sequence about 1000 base pairs at a time and shortest chromosome has 47 million base pairs. How best to put these pairs together and get a full sequence is an NP problem

  2. How does a protein fold based on mRNA sequence is also a NP hard problem

  3. Optimization problems can be NP hard problems. Finding the minimum energy of a physical system can be an NP hard problem

  4. There are many NP problems in game theory

The Hardest Problems in NP

A logic expression is satisfiable if there is someway to find a solution that satisfies the logic expression. If there is a quick algorithm for solving the satisfiable problem, then by “reduction”, you can use the same algorithm for solving the original problem. The author shows the clique problem can be reduced to satisfiability problem. It was Steve Cook, an University of Toronto professor who showed that “Satisfiability” is a good candidate for an interesting problem not efficiently computable. Even though Cook was the first to notice the importance of the problem, it was Richard Karp, a Berkley professor who converted the satisfiability problem to clique problem. Cook and Karp’s work meant that satisfiability for a clique is easy to compute if and only if clique was easy to compute. Thanks to the connection between satisfiability and solvability, there were now many different problems that are equivalent in terms of computational hardness. Solve any of the problem efficiently, and you have the solution to all the problems, i.e P=NP. These problems did not emanate from some pure mathematician’s head but arose from the practical world. It was Donald Knuth who ran a poll to figure out a name for the set of problems in NP that are hardest and the poll suggested the name, “NP complete”.

The author gives the following examples from the real world that are NP-complete:

  1. Scheduling operations in a Coke plant

  2. How to go for a Disney tour so that you spend minimum amount of time ?

  3. Figuring out the dominating set in a graph

  4. Large Sudoko games

  5. Minesweeper game

  6. Tetris

  7. Graph Isomorphism

  8. Factoring a prime number

  9. Integer Linear Programming problems

The Prehistory of P versus NP

Another way to verbalize P=NP is : Do you need a brute force search to solve a problem or do you have a smart algorithm for solving the problem ? This chapter gives the historical background to the P versus NP problem. There are two strands of developments mentioned, one in the Russian camp and other the Western nations camp. The following personalities figure on the Western nations camp :

  • Warren McCulloch

  • Walter Pitts

  • Juris Hartmanis and Richard Stearns

  • Jack Edmonds

  • Alan Cobham

  • Steve Cook

  • Richard Karp

And on the Russian side,the following spearheaded the effort:

  • Sergey Yablonsky, who first focused on perebor for finding the smallest circuits for computing functions but whose power and arrogance worked against the development of computational complexity in Russia.

  • Andrey Kolmogorov, the great Russian mathematician, who measured complexity via algorithmic information.

  • Kolmogorov’s student Leonid Levin, who independently developed the P versus NP problem and the theory of NP-completeness.

**

Dealing with Hardness

**

NP-complete problems are nasty creatures. Should one give up whenever one stumbles on to a variant of NP-complete problem. Not necessarily. This chapter gives a list of alternative approaches that can be used to solve moderate sized problems.

  • Brute force : Thanks to Moore’s law, the computing power of today’s computers help one use a brute force approach to find the solution. For example TSP on 1000 cities can be solved using today’s technology

  • Heuristics

  • Search for a smaller version of the problem

  • Approximate solutions

There are many other problems though, that do not yield to any of the above hacks and they are many out there that are NP-hard.

Proving P ≠ NP

This chapter provides a list of approaches that various people have taken to prove that P is not equal to NP

  • Using Paradoxes : The author lists “I am liar” paradox to show that in mathematics, there is a certain appeal to using paradoxes. Godel upended the foundations of mathematics by showing that there are true statements that one cannot prove as true. Halting problem is another type of problem that can be understood via paradox. There simply can never be any program that can tell whether another program finishes. However the author shows that using this approach to prove P is not equal to NP isn’t going to work.

  • Circuits : Every IC in a computer has transistors and each of these transistors implement logic gates. Every function, no matter how complicated, can be computed by a circuit of AND, OR, and NOT gates. What’s the connection with circuits ? Any problem that has computationally efficient solution can have a reasonably small. There have been many efforts by various people to use circuits to prove or disprove N=NP, but none have stood the test of rigor.

Where are we in the efforts to proving P vs. NP?

The only known serious approach to the P versus NP problem today is due to Ketan Mulmuley from the University of Chicago. He has shown how solving some difficult problems in a mathematical field called algebraic geometry (considerably more complex than high school algebra and geometry) may lead to a proof that P ≠ NP. But resolving these algebraic geometry problems will require mathematical techniques far beyond what we have available today. A few years ago Mulmuley felt this program would take 100 years to play out. Now he says that is a highly optimistic point of view. How long until we see an actual resolution of the P versus NP problem? Maybe the problem will have been resolved by the time you read this. Far more likely the problem will remain unsolved for a very long time, perhaps longer than the 357 years needed for Fermat’s Last Theorem, or perhaps it will forever remain one of the true great mysteries of mathematics and science.

**

Secrets

**

This chapter gives a brief introduction to cryptography and in doing so, shows how much of the modern cryptography relies on P ≠ NP. It starts off by giving a 10000 ft. view of public key and private key cryptography. One cannot help but notice that the fact that since factoring is assumed to be NP hard, today we have a convenient secured communication. Every time you see a “https” in your browser URL, it is the public key-private key in action. In the future, if someone were to prove P= NP, the modern cryptography would fall apart. So, does it signify “End of the World” ? Not really. There are techniques like one-time pads that can be used to create secure communication channels, the downside though is that the method of providing these channels become painful.

The author gives an example of Sudoko to illustrate the concept of “zero knowledge proof” Sudoku is NP-complete, so every NP problem can be reduced to Sudoku. So we automatically get a zero-knowledge system for every NP problem. In a common attack in cryptography, a person can cheat by pretending to be someone he or she isn’t. Zero-knowledge proofs give a method to guard against such identity spoofing. There is also a brief mention about the fully homomorphic encryption and Pseudorandom number generators for creating secure communication.

Quantum

This chapter gives a bird’s eye view on Quantum computing and its relevance to the P vs. NP problem. Unlike the traditional bit that is used in the computers, quantum computing uses something called “qubit”. The chapter gives a range of potential applications that can make many NP problems tractable. However the author is cautious about the time it might take for us to see real applications of quantum computing.

Full-scale quantum computers will remain special-purpose machines, useful for factoring  numbers or simulating quantum systems. They may help us break codes and help us better understand the fundamental nature of the universe, but they likely won’t solve NP-complete problems or make spreadsheets run faster.

The Future

By the time a reader hits the last chapter, it is clear that the author has a bleak outlook for the P vs. NP problem. However he says that the problem gives a common framework to solve great computational tasks that lay ahead of us.

  • Parallel computation: Computers used to double in speed every eighteen to twenty-four months, but now we are hitting physical limits that prevent much faster processors in the future. Instead, computers are multiplying, and we can have several processors working together on a chip or in a cloud. How can we adjust our algorithms to work in this growing parallel world? The class of the problems that can be solved by parallel computing is called NC. So, the mystery deepens. Is P=NC ? Is NC = NP?

  • Big data: From the Internet to scientific experiments and simulations, we create huge amounts of data every day. How do we reason about, make sense of, learn from, and develop predictions from this massive amount of information?

  • Networking of everything: Much of the world lives on some computer network, whether they use some social network like Facebook or just communicate via email. Soon nearly everything man-made will also be part of this network, from the clothes we wear to the light bulbs we read by. How do we make the best use of this ultraconnected world?

The author concludes the book by saying,

Computation is about process, and not just on computers. The P versus NP problem has to do with the limits on nature itself, on how biological and physical systems evolve, and even on the power of our own minds. As long as P versus NP remains a mystery we do not know what we cannot do, and that’s liberating.

takeawayTakeaway:

The book is more than just describing a particular unsolved problem in computer science. It takes a whirlwind tour of many problems across several domains and gives the reader a beautiful perspective about what could happen if ever the P vs. NP problem were to solved. Even if the problem is not solved for another century, the framework that can be obtained by thinking through the problem would make one’s mind richer.