American Scientist

THE NATURE OF COMPUTATION. Cristopher Moore and Stephan Mertens. xviii + 985 pp. Oxford University Press, 2011. $90.

A YouTube video shows a smartphone, its camera aimed at a device made of Legos that it also controls, solving a Rubik’s Cube. It’s one of many such videos, and the smartphones in them do not solve only the standard 3 x 3 x 3 cube: One solves the 7 x 7 x 7 in 39 minutes, an impressive time. The phenomenon raises some questions—in addition to the obvious one of why anyone would undertake a project as crazy as this. How does the time taken by the robot to solve the cube increase with the size of the cube? Does the smartphone’s memory capacity, modest by today’s standards, limit its ability to solve cubes? And then there’s a host of more mundane questions, like how colors are distinguished and represented, how three-dimensional space is “imagined,” and so on.

It’s easy to see why computer scientists are especially intrigued by the challenge posed by the actual puzzle, and perhaps less by the implementation of simple tasks, such as making the robot execute a specific move. To be sure, the latter is not without its technical challenges, and it is mostly in this domain that computer-powered technology dazzles us. But it is in the details that lead to the solution—the planning of moves, the formulation of strategies, what we imagine as the willingness to prevail in seemingly hopeless circumstances—that the actions of the automaton command our respect.

Despite its name, theoretical computer science has very little to do with actual electronic computers. The notion of an algorithm, a procedure for arriving at a solution by a sequence of elementary steps, was familiar even to the ancient Greeks. Euclid’s algorithm for finding the greatest common divisor of two integers is still in use today. And although much of current computer science is devoted to finding efficient algorithms, that accounts for only part of the subject. The field has a deeper and even philosophical half that the average technology consumer is unaware of. This branch began in the 1930s when Alan Turing decided it was interesting to ask what could be computed in principle, efficiency be damned.

When time and memory capacity are treated as abstract commodities, computer science addresses questions at the very foundations of mathematics. For example, Turing showed that David Hilbert’s famous Entscheidungsproblem (“decision problem”) was “undecidable”—deciding whether a proof exists for any given mathematical statement cannot be done in a finite amount of time by any algorithm. Perhaps the premier unresolved mathematics question of the present day is the P versus NP problem. The letters refer to “complexity classes,” broad characterizations of computational difficulty. Problems in the class P can be solved efficiently, while for those in NP, we know that checking a candidate solution is easy. The prevailing wisdom is that there are problems in the class NP that are not in P —that problems exist for which it’s easy to check a given solution but that are very hard to solve . The Clay Mathematics Institute is offering a $1 million prize to anyone who can decide whether this is the case .

In The Nature of Computation, Cristopher Moore and Stephan Mertens have produced one of the most successful attempts to capture the broad scope and intellectual depth of theoretical computer science as it is practiced today. In the preface we are told that this monumental project of almost 1,000 pages was launched as an effort to explain complexity classes to physicists. Physicists have contributed to computer science in two ways: through applying the methods of statistical mechanics to computation problems and, more recently, through the introduction of quantum mechanics to models of computation. Had Moore and Mertens followed their original plan, the outcome would have been a guide for physicists, written in physicists’ language, to the arcane world invented by computer scientists. As it happens, the book instead took the form of a comprehensive and very readable textbook on computer science. Although it is true that some of the later parts of The Nature of Computation feature the physics-inspired work of the two physics-trained authors, these sections do not take center stage. Rather, what shines from every page is that Moore and Mertens are crazy about computer science and have gone all out to share their fondness for the subject.

Some reviewers of this book have made the comment that one of its few weaknesses is that it sometimes does not present enough technical detail to serve as a rigorous textbook. I disagree. Details are omitted only when they would intrude on the clear exposition of the main theme, and even then the authors are careful to provide accessible supporting material in the form of illustrations and plausibility arguments. Certainly, wherever computer science makes its most creative displays, such as when reducing one problem type to a seemingly very different one, the material is presented with complete rigor. The book is also not short on more technical topics that, although they are cornerstones of practical computation, receive only passing reference in many textbooks. For example, I was delighted to see a beautiful chapter on linear programming, a geometric computing paradigm. Instructors will be pleased by the easy exercises sandwiched between paragraphs, designed to stimulate comprehension, in addition to the wealth of engaging and more challenging problems at the end of each chapter. There are extensive notes and reference material, also at the ends of the chapters, conveniently notated with a special symbol in the margins of the main text.

Even if you are not a student or instructor of computer science, you should consider buying copies of this book for your friends’ coffee tables. The Nature of Computation is one of those books you can open to a random page and find something amazing, surprising and, often, very funny. From the generous selection of eclectic quotations and the gorgeous illustrations, it’s clear the authors had fun writing it. So how does one illustrate a chapter about a very abstract topic called “interactive proofs” that features mathematical conversations between Arthur and Merlin? For this Moore and Mertens have chosen some nice engravings, one of which shows Vivien (who, in the legend of King Arthur, enchanted Merlin and imprisoned him in a tree trunk), in the wizard’s arms. The caption reads, “Merlin is too busy to have a conversation with Arthur. He will send a proof instead.”