Theoretical computer science (TCS) encompasses a multitude of diverse subjects with complex issues and many formalisms. The authors address the subject area on at least three different levels. There is the history of scientific discoveries, starting with the founder of graph theory, Leonhard Euler, and his bridges of Königsberg puzzle, followed by a panoply of groundbreaking mathematical, logical, and computational topics and solutions. Then there is the substantive layer, enumerating all of the algorithms, proofs, and lemmas, as well as the factual building blocks of physics, mathematics, and logic, to forge an interdisciplinary construct of TCS. Lastly, there is the pedagogical level, where readers are presented with exercises in the text and problems at the end of each chapter to help check their understanding of the presented subject matter.
The authors recommend reading chapters 1 to 7 in chronological order (p. xvii), and then reading select later chapters depending on need or interest. The book is well suited as a textbook for graduate- and undergraduate-level courses on multiple subjects. Prerequisites for reading the book include linear algebra, calculus, Fourier analysis (especially for chapter 15), a modicum of programming knowledge, such as for/while loops, and some mathematical techniques, such as discrete probability. Many of these techniques are also discussed and explained in an appendix on mathematical tools.
Chapter 1, a prologue, begins with Euler’s armchair solution to the famous puzzle of whether it is possible to walk through the city of Königsberg while crossing each of its seven bridges exactly once. This chapter is a very effective way to get the reader used to thinking about solving a problem algorithmically, and makes clear the level of abstraction on which the book functions. Chapter 2 goes deeper into the notion of algorithms, space and time complexity, scaling, and tractability. Chapter 3 discusses recursion, algorithmic techniques such as divide and conquer, dynamic programming, greedy algorithms (for example, how to most efficiently select coins when making change), and flows and cuts in digraphs.
Chapter 4 introduces the notion of nondeterministic polynomial-time (NP) problems, which will recur in subsequent chapters. Chapter 5 deals with NP-complete problems, which are defined: “A problem B in NP is NP-complete if, for any problem A in NP, there is a polynomial-time reduction from A to B” (p. 128). Since many problems can be proven to be NP-complete, it is sufficient to reduce unclassified problems to known NP-complete examples to show that they too are NP-complete. Over time, known NP-complete problems have been assembled into a family tree, including graph theory, puzzles, and planning. Chapter 5 expands greatly on that family tree.
In chapter 6, the authors propose that the P versus NP question (that is, “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?”) is at the core of the mathematical challenges stated by the Clay Mathematics Institute. The authors claim that the P versus NP problem is also at the core of the survival of human reasoning and creativity, an argument so lucidly presented without the help of formalisms that even nonmathematicians can appreciate it. Chapter 7 explains recursion theory as universal computation with its inherent limitations. The chapter includes a discussion of Babbage’s difference engine and the Turing machine. The three computational formalisms of recursive functions, lambda calculus, and the Turing machine are explained in detail. In chapter 8, the authors discuss space complexity using two-player games as building blocks for defining the classes. They then provide a proof for the nondeterministic logarithmic-space (NL) completeness of the reachability problem to differentiate NL-completeness from NP-completeness.
Chapter 9 includes a 100-page tutorial on optimization and approximation. Starting with approximating to the optimum using minimization and maximization, the chapter discusses linear programming and concludes with smoothed analysis. Chapter 10 introduces randomized algorithms as a prerequisite for the chapters to come. Chapter 11 covers probabilistically checkable proofs, approximability, and their interconnections.
Chapters 12 to 15 deal with complexity and computability related mostly to the statistics of physics and related fields of study. The authors” discussion of the plausibility of the physical Church-Turing thesis (that is, that any computer can simulate any quantum machine with concomitant intended precision) in chapter 15 is a tour de force of quantum theory that links randomized algorithms to quantum phenomena.
In a world of bite-sized wikis and 140-character messaging, it is refreshing to find a truly scientific masterpiece that provides a full 360-degree multifaceted exposition with almost entertainment-like quality. The authors have fully achieved their intention for the book: “We have endeavored to write our book with the accessibility of Martin Gardner, the playfulness of Douglas Hofstadter, and the lyricism of Vladimir Nabokov” (p. xvi).