This book is one of those inspiring books that almost every computer scientist should read. Moreover, it is also very well suited to a wider audience, including those curious about the field and newcomers. Its authors, Lipton and Regan, did a wonderful job introducing and analyzing important problems in complexity theory with an easy-to-read text.
The book is divided into 63 chapters (and indeed I found it funny that this number is 26-1, which is maybe a coincidence but a funny one), each one dealing with a different question or, more generically, a problem. While a few chapters actually require a good background in complexity theory or other fields of mathematics, many are accessible to a wide audience, from undergraduates to scientists in the field.
The book consists of different entries from the authors’ blog Gödel’s Lost Letter and P=NP (http://rjlipton.wordpress.com/), which is highly recommended to everyone with any interest in computers in general and complexity theory in particular. This type of presentation might sound boring, but it is not. Some chapters reference others, and every one is well self-contained so that it is a complete book in the traditional sense. Every chapter starts with a simple introduction, which is followed by some sections that deal with the question selected in that particular chapter, and ends with open questions and various notes and links. It is a perfect match for those seeking new problems or progress in the current state of the art. Maybe the only miss is that it does not contain a complete glossary at the end.
Since the book consists of a collection of various posts from their blog, the first chapter is devoted to the importance of the collaborative work that can arise on the Internet. The example could not be more prominent and demonstrates the power of openly sharing knowledge among different people in the world. Chapter 1 provides a lot of details on the exciting events that followed the attempt of Vinay Deolalikar to prove that P≠NP. In addition, it is also mixed with personal details and anecdotes, which also happens often in other chapters.
The book often uses the figure of a remarkable personality in the world of science (such as Einstein or Feynman) to motivate the research into a particular question. Indeed, the name of every chapter consists of two parts: the name of a researcher and a reference to the problem under study in that chapter. It is full of citations and personal judgments about the results of some research (most of them very positive).
Problems in this book are presented in various forms. Most are presented in a mathematical way, some are presented as games, and others consist of reflections about how to make good science with a number of invaluable suggestions (even more invaluable considering where they come from) or other considerations, such as historical remarks, sometimes very surprising. Most chapters are written in a very personal way that makes you feel that the authors are speaking directly to you. This reaches a climax in chapter 55 where the authors offer various gifts to their readers.
This book is only about 330 pages long, but it is far thicker than what it seems. Its format allowed the authors to put the essence of an impressive number of techniques and subdisciplines together, from traditional complexity to quantum computing, pseudo-random algorithms, set theory, combinatorics, number theory, propositional logic, and so on.
In conclusion, this book reveals two acclaimed scientists’ particular understanding of, and way of thinking about, so many intricate yet extremely interesting problems. It is therefore an invaluable source of inspiration and study.
More reviews about this item: Amazon
