You are here

Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak
Cambridge University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Leon Harkleroad
, on

Computational Complexity could have been — and still could be, in a future edition — a fine book. As it stands, however, errors seriously sabotage its potential. This is quite unfortunate, as the book has a lot going for it, including the range of coverage, the overall approach, and the authors’ expertise.

To accommodate a variety of audiences (undergraduates, graduates, computer scientists, mathematicians, etc.), Arora and Barak have organized the book into three parts. The first eleven chapters lay out the basics of topics such as P and NP, randomized algorithms, interactive proofs, quantum computation, and much more. Several of the themes introduced here then reappear in more detail in Part Two (five chapters on Boolean circuits, decision trees, and other models of computation) and Part Three (seven chapters under the heading of advanced topics). For example, Chapter 11 describes the PCP Theorem (PCP stands for probabilistically checkable proof), explores it from different angles, and proves a weaker version. Subsequently, Chapter 22 presents a proof of the full theorem, treats related results, and so on. Structuring the material this way not only provides flexibility, but also lends itself to keeping the forest visible for the trees.

The text consistently emphasizes the ideas underlying the various definitions, results, and techniques. Computational Complexity makes good on the claim in the preface that “[t]hroughout the book we explain the context in which a certain notion is useful, and why things are defined in a certain way.” And to call the authors well qualified would understate matters. Arora, particularly noted for his work on probabilistically checkable proofs, delivered an invited address to the 2002 International Congress of Mathematicians. Colleagues at Princeton, Arora and Barak share the distinction of having won ACM awards for their respective doctoral dissertations.

All of the above makes it quite disappointing that so many errors mar Computational Complexity. I will discuss only a few, but these are not isolated examples. Given human fallibility, some mistakes — especially in a first edition — do not come as a surprise, but the book contains considerably more than its share of glitches that can mislead, confuse, or disturb. Several statements are downright incorrect. For instance, the analysis of the running time for one algorithm relies on “the fact that Σj>k jn(nk)/2,” where 1 ≤ kn. That supposed fact fails for every such integer k other than n.

Elsewhere the text gives, as the formula for the inverse of a matrix A, that the “(i,j)th entry is det(A–(i,j))/det(A), where A–(i,j) denotes the (n–1)x(n–1) matrix obtained by removing the ith row and jth column from A,” wrong by both a transpose and signs.

Likewise, the book missteps in its handling of the Chinese Remainder Theorem, given in the form that for relatively prime p and q, the map taking m to (m mod p, m mod q) is an isomorphism. Taken at face value, the relevant passage seems to claim that an injective homomorphism must be an isomorphism. At any rate, the purported proof does not at all address the surjectivity of the map, which of course constitutes the heart of the theorem.

Many errors take the form of omissions. Thus Computational Complexity names, as an example of a group, “the set of functions from a domain A to itself, with function composition being the group operation,” with no mention of bijectivity. On one page the authors state, “Vector spaces with an inner product are known as Hilbert spaces,” and two pages later they add, “Vector spaces with a norm are sometimes known as Banach spaces.” Completeness never enters into the picture. The book’s version of what it calls Fermat’s Little Theorem — in reality, Euler’s generalization — claims that “[f]or every n and x {1, … , n–1}, xφ(n)=1 (mod n),” neglecting the requirement that x and n be relatively prime.

One omission, merely typographical but potentially very serious, occurs in the definition that “EXP = c>1.” If not for the fortunate circumstance that fifteen pages later, the authors remind the reader that previously “we encountered the class EXP = c≥1DTIME(2nc ),” this important notion would lack a proper definition in the book. Again, many other mistakes of content, larger and smaller, occur throughout. Additionally, a multitude of misspellings, grammatical errors, and slips of the cut-and-paste variety indicate that the text received poor, if any, copy-editing from the publisher.

Regrettably, this high error rate undermines, for the reader, the credibility of a book that could offer much. A revamped second edition with more careful attention to correctness could let all that Computational Complexity has to offer come shining through, unobscured.

Although in recent years Leon Harkleroad has spent much time with mathematical aspects of music, he still enjoys exploring his original stomping grounds of computability theory and related areas.


Part I. Basic Complexity Classes: 1. The computational model - and why it doesn’t matter; 2. NP and NP completeness; 3. Diagonalization; 4. Space complexity; 5. The polynomial hierarchy and alternations; 6. Boolean circuits; 7. Randomized computation; 8. Interactive proofs; 9. Cryptography; 10. Quantum computation; 11. PCP theorem and hardness of approximation: an introduction; Part II. Lower Bounds for Concrete Computational Models: 12. Decision trees; 13. Communication complexity; 14. Circuit lower bounds; 15. Proof complexity; 16. Algebraic computation models; Part III. Advanced Topics: 17. Complexity of counting; 18. Average case complexity: Levin’s theory; 19. Hardness amplification and error correcting codes; 20. Derandomization; 21. Pseudorandom constructions: expanders and extractors; 22. Proofs of PCP theorems and the Fourier transform technique; 23. Why are circuit lower bounds so difficult?; Appendix A: mathematical background.