The Golden Ticket: P, NP, and the search for the impossible
by Lance Fortnow

I had this book on my bedside table for the past two months. As you can see, I did not have time to write anything here since the end of April: the end of term, exam marking, exam boards, a long list of project deadlines and reviews for various conferences meant that I had to postpone almost everything that was not urgent, including the removal of items from the stack on my bedside tabale (the actual structure of the pile of items is an interesting topic of research on its own: see exercise below).

An eleven hours flight to San Francisco is the perfect environment to read this short book, to write this post, and to make my wife slightly less upset about the status of my bedside table: hopefully I’ll be able to empty it by the end of summer so that dust can be appropriately removed without the need of finding the shortest path among all the obstacles I leave on it.

Back to the book: it starts with the observation that “there seems to be no limits to what computers can do. Or is there? [The] book explores the computational problems that we may never be able to compute easily“.

The bold is mine, because this is the key issue: some problems have solutions that are “easy” to compute, some others are difficult.  The book is not about undecidable problems (see my other post www.rmnd.net/the-universal-computer/ for a reference), but about the complexity of problems for which a solution exists. The book avoids all the technical details of complexity classes expressed in terms of Turing machines and focuses instead on two of them: the class of “easy” problems called P (because they can be solved with an algorithm that runs in time polynomial in the size of the input), and the class of problems for which a solution cannot be computed easily but, when a solution is given, its correctness can be verified easily. This latter class is called Non-deterministic Polynomial, because when a solution can be guessed, it can be verified in polynomial time. If you are interested in the mathematical details, I recommend the book “Computational Complexity” by Christos Papadimitriou.

One of the fundamental questions in Computer Science and in Mathematics is: are the two classes P and NP equal or different? This is the question that the book explores with captivating examples and a presentation that is suitable for everyone.

Chapter 3 provides examples of problems in P (matching problems, shortest and Eulerian paths, min-cut) and so-called NP-complete problems (Hamiltonian cycles, four colour problem, max-cut). I know my list may sound boring, but the presentation in the book is full of clear and funny examples. Additional hard problems are described in Chapter 4, including games such as Minesweeper, Tetris and Sudoku, the satisfiability problem and the works of Cook, Karp and Knuth.

Chapter 6 presents in a very clear way some of the techniques that can be used to solve “difficult” problems in NP, and Chapter 7 describes some of the techniques that have been employed to tackle the P vs. NP problem. This latter chapter, together with Chapter 5, are my favourite in the book: they provide the historical context in which the problem was born, and they give an account of both the Western and the Eastern research groups involved. This is something you don’t find in standard textbook and is one of the reasons you should read this book even if you already familiar with computational complexity (in addition to a very useful list of examples that can be used for teaching purposes)

Chapters 8 to 10 take a detour in cryptography and quantum computing, presenting the important connections between these topics and complexity theory, and concluding with a list of challenges for the future that go beyond the P=NP question.

Franco, did you buy a faulty book without chapter 2? Why are you not talking about it?
Because I think it should have been more formal. The chapter talks about an ideal world in which P is equal to NP: in this world it would be possible to cure cancer and to forecast weather at any time in the future. I don’t think this is the case. I am not an expert in DNA sequencing, but I know something about weather forecast: in this case reliability is not related to the complexity of finding a solution, but to the problem of the dependance from initial conditions (the famous butterfly effect). Even if we had a polynomial algorithm for weather forecast, I think this would not solve the issue of the uncertainty of result given the sensitivity on initial conditions.

So should I read the book or not?
You should definitely read it! The book is excellent, a pleasure to read and full of very interesting and useful information. I personally did not like the style of chapter 2, but this is the only issue I had (and it could be that other people like that chapter); I really enjoyed everything else.

The Golden Ticket
P, NP, and the search for the impossible
by Lance Fortnow
Princeton University Press, 2013

Digression:

I have realised that the pile of books on my bedside table does not seem to be manageable by any of the esiting data structures in the literature. Sometimes it behaves as a stack, sometimes as a queue, and sometimes it is random access. Therefore, I would like to put forward the following exercise to my students.

Design a data structure with the following characteristics:

•  if you do a put operation (I.e., you buy a new book) place it on top of the stack. However, if this compromises the stability of the structure, place it in an appropriate position in the pile considering its dimensions.

• if you are reading a book and you do a put operation before going to bed, the book should sit as high as possible in the pile, preserving stability.

• if you are doing a put operation to replace a book that you pulled a few minutes before just to read the title wondering why you bought it, then put it back in the same position, unless you changed you mind about how interesting it is.

For a pull operation:

• if you are reading a specific book, pull that book in most cases.

• However, you can randomly pull any other book  every once in a while just to remind you why the book is there in the pile, so that you can explain to your wife that the book cannot be moved to the bookshelf in the other room but it must remain there.

•  if you are not reading a specific book in the pile and you are deciding what to read next, you should morally pull the book at the bottom of the pile. However, if you have other unread books on top, it means that you probably considered them more interesting than the book at the bottom (or maybe stability issues caused a rearrangement). You may need a ranking procedure here to decide what to pull.

Your chosen solution should model all the possible parameters (dimensions, boringness, time on bedside table, current book being read, etc.) and provide an adequate representation with a detailed analysis of the complexity for all the operations. My wife will be happy to provide input data for all your unit tests