What do you think?
Rate this book
Computational Complexity: A Modern Approach
This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem.
609 pages, Kindle Edition
First published December 13, 2007
53 people are currently reading
918 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 17 of 17 reviews
June 23, 2009
Amazon 2009-06-17. Wow, this is *REALLY GOOD* so far, definitely the best of several computational complexity books I've ever read (as the first major publishing event in complexity theory since Aaronson's development of the Complexity Zoo, perhaps there was a higher bar to leap). Seventeen thirty-two, personal note: my signature lifts a quote from the Complexity Zoo:
The book has wonderful quotes heading each chapter, which I just can't say enough about. Computer scientists don't know nearly enough of the rich history of their study (I'm regularly scandalized when I run into graduate students -- not the ladies and man-ladies in things like Human-Computer Interaction, but real apprentice computer scientists -- who don't know the names of Church, Rabin, Aho, Hamming and Hoare. I want to punch these ingrates in the face), and things like this can only help. The bibliography and citations are kind of sparse, but the important ones are there, and the authors are as current with the literature as one would hope (I was pleased to see the newly-seminal AKS2004 referenced early on).
Be sure to check out section 2.7.3, "The P == NP Utopia", for a special treat -- coverage of the implications of that most foul heresy, the majority of which I'd heard elsewhere, but only as single, whispered perversions -- with a look forward to chapter 5, its coverage of the polynomial hierarchy, and a surprise or two regarding MIN-EQ-DNF (btw, if you've never read it, Aaronson's tongue-in-cheek "Polynomial Hierarchy Collapses" is one of the funniest things ever written).
One comment -- the exercises, so far, are both really fucking weird and really fucking difficult. I am not sure I'd want to use this book's problem sets as self-study; classics like Papadimitriou are still the best in this arena, IMHO.
I'm not yet done, and this might yet get its fifth star -- we'll see. What is certain, however, is that there is a new standard reference for undergraduate and graduate students, researchers and professionals interested in the majestic sweep of complexity theory, and its authors are Sanjeev Arora and Boaz Barak.
Nondeterministic Polynomial-Time: The class of dashed hopes and idle dreams...The book was clearly designed with the assumption that Sipser's modern classic Introduction to the Theory of Computation would be used as an undergraduate precursor; besides referencing Sipser several times early on (and his role heading up MIT's Math department, a group the authors are -- from the Foreward -- definitely good pals with (the authors themselves hail from Princeton, where I had no idea but Brian Kernighan and Robert Sedgewick are still faculty (of course I knew Andrew Appel, Edward Felten, and Robert Tarjan were still there, and Andrew Yao/Richard Lipton's emeritus status (but we've got Lipton now, motherfuckers!)))). The book takes off almost directly from where Sipser's study of complexity ends, with a deep study of p≤ polynomial-time Karp reducibility (well, actually it starts with deterministic TM's, but as I've studied the 7-parameter TM formalism since I was thirteen or so, I didn't look at Chapter 1 too closely (I *do* applaud their Claim 1.6: single-tape simulation of k-tape TM's in time 5kT(n)^2 -- this kind of rigorous, strong presentation is welcomed -- and ESPECIALLY the early presentation of oblivious Turing Machines (those which care only about the input length, not the input content), as this simplifies many a proof later on (most authors, if they introduce OTM's at all, do so only as a curiousity and not as a fundamental proof mechanism))). The heavy emphasis throughout on the dual miracles of randomization and modern crypto (including more advanced topics like derandomization, the probabilistic complexity classes, pseudorandomization and hardness amplification) will hopefully result in these topics being more deeply embedded within classical theory classes, as they should be. Furthermore, being placed (for the first time?) on the same footing as automata and the Hierarchy means that relevant issues are addressed throughout -- the implication that P == NP, for instance, would mean that nothing is to be gained from randomized algorithms, was entirely new to me *despite* having taken Lipton's Randomized Algorithms class and having read both of the two major books on the subject (Motwani + Raghavan and Mitzenmacher + Upfal). I can fairly say that realizing this obvious truth blew my mind.
The book has wonderful quotes heading each chapter, which I just can't say enough about. Computer scientists don't know nearly enough of the rich history of their study (I'm regularly scandalized when I run into graduate students -- not the ladies and man-ladies in things like Human-Computer Interaction, but real apprentice computer scientists -- who don't know the names of Church, Rabin, Aho, Hamming and Hoare. I want to punch these ingrates in the face), and things like this can only help. The bibliography and citations are kind of sparse, but the important ones are there, and the authors are as current with the literature as one would hope (I was pleased to see the newly-seminal AKS2004 referenced early on).
Be sure to check out section 2.7.3, "The P == NP Utopia", for a special treat -- coverage of the implications of that most foul heresy, the majority of which I'd heard elsewhere, but only as single, whispered perversions -- with a look forward to chapter 5, its coverage of the polynomial hierarchy, and a surprise or two regarding MIN-EQ-DNF (btw, if you've never read it, Aaronson's tongue-in-cheek "Polynomial Hierarchy Collapses" is one of the funniest things ever written).
One comment -- the exercises, so far, are both really fucking weird and really fucking difficult. I am not sure I'd want to use this book's problem sets as self-study; classics like Papadimitriou are still the best in this arena, IMHO.
I'm not yet done, and this might yet get its fifth star -- we'll see. What is certain, however, is that there is a new standard reference for undergraduate and graduate students, researchers and professionals interested in the majestic sweep of complexity theory, and its authors are Sanjeev Arora and Boaz Barak.
September 3, 2025
Com que aquí estem en petit comitè, us confesso (ho negaré en seu judicial) que poder saludar a en Boaz el desembre passat em va fer il·lusió.
August 12, 2018
An excellent book on computational complexity, covering a wide range of topics that I haven't found discussed in other books. It is useful both as reference material and as a self-learning textbook. I haven't read all the chapters in detail (I was more interested in Parts I and III).
The exercises are interesting and have hints and the chapter notes are full of really useful references for further reading
The exercises are interesting and have hints and the chapter notes are full of really useful references for further reading
April 7, 2021
Read it to get the details. Sort of overshadowed, for me, by Moore's "Nature of Computation"
March 8, 2026
Abstract
Computational complexity theory provides the formal framework for understanding the intrinsic difficulty of computational problems. The monograph Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak represents one of the most comprehensive modern treatments of the subject. This review critically evaluates the book from a doctoral research perspective, focusing on its mathematical foundations, theoretical contributions, pedagogical structure, and influence on contemporary complexity theory. Particular attention is given to the formal definitions of complexity classes, probabilistic proof systems, pseudorandomness, and circuit complexity. The review further discusses major unresolved problems such as the P versus NP problem, circuit lower bounds, and derandomization. Finally, several research directions are proposed that extend the theoretical framework presented in the text toward modern developments in quantum computation, fine-grained complexity, and learning theory.
1. Introduction
The study of computational complexity seeks to classify problems according to the resources required to solve them. These resources typically include time, space, randomness, and communication. Since the emergence of complexity theory in the 1960s and 1970s, the discipline has developed into a central pillar of theoretical computer science.
The foundations of modern complexity theory were laid by the pioneering works of Stephen Cook, Richard Karp, and Leonid Levin, particularly through the formalization of NP-completeness and polynomial reductions.
The book under review synthesizes several decades of progress in complexity theory, integrating classical results with modern developments such as:
• probabilistically checkable proofs
• hardness of approximation
• pseudorandomness
• interactive proof systems
• quantum complexity
The work functions both as a pedagogical text and as a conceptual synthesis of the field.
2. Mathematical Foundations
The book begins with formal definitions that establish the theoretical framework of computational complexity.
2.1 Models of Computation
The canonical model of computation remains the Turing machine, introduced by Alan Turing.
Definition (Deterministic Turing Machine)
A deterministic Turing machine is a tuple
The running time of (M) on input (x) is the number of steps until halting.
2.2 Time Complexity Classes
Definition (Class P)
The complexity class
represents problems efficiently solvable on deterministic machines.
Definition (Class NP)
This formulation highlights the verifiability paradigm central to complexity theory.
2.3 NP-Completeness
A language (L) is NP-complete if
1. (L \in NP)
2. Every language in NP is polynomial-time reducible to (L).
The first NP-complete problem was SAT, established in the seminal theorem of Cook.
Theorem (Cook–Levin)
Boolean satisfiability is NP-complete.
This theorem forms the conceptual foundation of computational hardness.
3. Contributions in the Book
The book’s primary strength lies in its detailed treatment of advanced topics that shaped modern complexity theory.
3.1 Interactive Proof Systems
Interactive proofs extend classical verification by allowing communication between a prover and a verifier.
Definition
An interactive proof system consists of
• a probabilistic polynomial-time verifier (V)
• an unbounded prover (P) revealed unexpected computational power in interaction.
3.2 Probabilistically Checkable Proofs
One of the most influential results presented is the PCP theorem.
Theorem (PCP)
This means NP proofs can be verified by examining only a constant number of bits.
Consequences include:
• hardness of approximation
• new cryptographic constructions
• connections with coding theory.
The theorem was proven through work by researchers including Sanjeev Arora, Shmuel Safra, and Madhu Sudan.
3.3 Pseudorandomness and Derandomization
Randomized algorithms play an important role in complexity theory.
The class
represents problems solvable in polynomial time with bounded error.
A major open question is -
Research suggests that sufficiently strong circuit lower bounds may imply derandomization.
3.4 Circuit Complexity
Circuit complexity studies computation using Boolean circuits.
Definition
A Boolean circuit is a directed acyclic graph where nodes are logical gates.
The circuit complexity (C(f)) of a Boolean function (f) is the minimum number of gates required to compute (f).
Despite decades of research, proving super-polynomial lower bounds for general circuits remains one of the deepest problems in theoretical computer science.
4. Evaluation of the Book
4.1 Conceptual Integration
The book excels in synthesizing disparate areas of complexity theory into a unified framework. The integration of pseudorandomness, coding theory, and proof systems reflects the modern interdisciplinary nature of complexity research.
4.2 Mathematical Rigor
The presentation maintains strong mathematical rigor while remaining accessible. Many proofs are presented with careful intuition before formal derivation, which aids conceptual understanding.
4.3 Pedagogical Limitations
From a research perspective, certain limitations are notable:
1. Limited coverage of fine-grained complexity
2. Minimal discussion of parameterized complexity
3. Lack of extensive treatment of complexity in machine learning
These fields have become prominent in the past decade.
5. Open Problems -
The book naturally leads to several fundamental unresolved questions.
5.1 The P vs NP Problem
The central open question:
remains unresolved.
Its solution would fundamentally alter our understanding of computation, optimization, and cryptography.
5.2 Circuit Lower Bounds
A major challenge is proving that
5.3 Quantum Complexity
Quantum computation introduces complexity classes ,
whose relationship with classical complexity classes remains partially understood.
Research areas include:
• quantum PCP conjecture
• quantum supremacy
• complexity of quantum verification.
6. Emerging Research
6.1 Fine-Grained Complexity
Fine-grained complexity investigates exact polynomial exponents.
Examples include conjectures such as
• Strong Exponential Time Hypothesis (SETH)
• Orthogonal Vectors conjecture.
6.2 Complexity of Machine Learning
Modern AI systems raise new theoretical questions:
• complexity of training neural networks
• generalization bounds
• computational hardness of learning.
6.3 Algebraic and Geometric Complexity
The Geometric Complexity Theory program seeks to address complexity lower bounds using representation theory and algebraic geometry.
7. Interdisciplinary Perspectives
Future progress in complexity theory may emerge through connections with:
• statistical physics
• information theory
• quantum information
• biological computation.
These interdisciplinary approaches may provide new mathematical tools for addressing fundamental complexity questions.
8. Conclusion
Computational Complexity: A Modern Approach remains one of the most influential monographs in theoretical computer science. Its comprehensive treatment of complexity classes, proof systems, pseudorandomness, and circuit complexity provides a foundational framework for modern research.
Despite the emergence of new subfields since its publication, the book continues to serve as a cornerstone reference for graduate education and theoretical investigation. The open problems it highlights—particularly the P vs NP problem and circuit lower bounds—remain central challenges of mathematics and computer science.
References
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
Cook, S. (1971). The complexity of theorem-proving procedures. Proceedings of the ACM Symposium on Theory of Computing.
Karp, R. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations.
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998). Proof verification and hardness of approximation problems. Journal of the ACM.
Goldwasser, S., Micali, S., & Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing.
Babai, L. (1985). Trading group theory for randomness. Proceedings of STOC.
Computational complexity theory provides the formal framework for understanding the intrinsic difficulty of computational problems. The monograph Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak represents one of the most comprehensive modern treatments of the subject. This review critically evaluates the book from a doctoral research perspective, focusing on its mathematical foundations, theoretical contributions, pedagogical structure, and influence on contemporary complexity theory. Particular attention is given to the formal definitions of complexity classes, probabilistic proof systems, pseudorandomness, and circuit complexity. The review further discusses major unresolved problems such as the P versus NP problem, circuit lower bounds, and derandomization. Finally, several research directions are proposed that extend the theoretical framework presented in the text toward modern developments in quantum computation, fine-grained complexity, and learning theory.
1. Introduction
The study of computational complexity seeks to classify problems according to the resources required to solve them. These resources typically include time, space, randomness, and communication. Since the emergence of complexity theory in the 1960s and 1970s, the discipline has developed into a central pillar of theoretical computer science.
The foundations of modern complexity theory were laid by the pioneering works of Stephen Cook, Richard Karp, and Leonid Levin, particularly through the formalization of NP-completeness and polynomial reductions.
The book under review synthesizes several decades of progress in complexity theory, integrating classical results with modern developments such as:
• probabilistically checkable proofs
• hardness of approximation
• pseudorandomness
• interactive proof systems
• quantum complexity
The work functions both as a pedagogical text and as a conceptual synthesis of the field.
2. Mathematical Foundations
The book begins with formal definitions that establish the theoretical framework of computational complexity.
2.1 Models of Computation
The canonical model of computation remains the Turing machine, introduced by Alan Turing.
Definition (Deterministic Turing Machine)
A deterministic Turing machine is a tuple
The running time of (M) on input (x) is the number of steps until halting.
2.2 Time Complexity Classes
Definition (Class P)
The complexity class
represents problems efficiently solvable on deterministic machines.
Definition (Class NP)
This formulation highlights the verifiability paradigm central to complexity theory.
2.3 NP-Completeness
A language (L) is NP-complete if
1. (L \in NP)
2. Every language in NP is polynomial-time reducible to (L).
The first NP-complete problem was SAT, established in the seminal theorem of Cook.
Theorem (Cook–Levin)
Boolean satisfiability is NP-complete.
This theorem forms the conceptual foundation of computational hardness.
3. Contributions in the Book
The book’s primary strength lies in its detailed treatment of advanced topics that shaped modern complexity theory.
3.1 Interactive Proof Systems
Interactive proofs extend classical verification by allowing communication between a prover and a verifier.
Definition
An interactive proof system consists of
• a probabilistic polynomial-time verifier (V)
• an unbounded prover (P) revealed unexpected computational power in interaction.
3.2 Probabilistically Checkable Proofs
One of the most influential results presented is the PCP theorem.
Theorem (PCP)
This means NP proofs can be verified by examining only a constant number of bits.
Consequences include:
• hardness of approximation
• new cryptographic constructions
• connections with coding theory.
The theorem was proven through work by researchers including Sanjeev Arora, Shmuel Safra, and Madhu Sudan.
3.3 Pseudorandomness and Derandomization
Randomized algorithms play an important role in complexity theory.
The class
represents problems solvable in polynomial time with bounded error.
A major open question is -
Research suggests that sufficiently strong circuit lower bounds may imply derandomization.
3.4 Circuit Complexity
Circuit complexity studies computation using Boolean circuits.
Definition
A Boolean circuit is a directed acyclic graph where nodes are logical gates.
The circuit complexity (C(f)) of a Boolean function (f) is the minimum number of gates required to compute (f).
Despite decades of research, proving super-polynomial lower bounds for general circuits remains one of the deepest problems in theoretical computer science.
4. Evaluation of the Book
4.1 Conceptual Integration
The book excels in synthesizing disparate areas of complexity theory into a unified framework. The integration of pseudorandomness, coding theory, and proof systems reflects the modern interdisciplinary nature of complexity research.
4.2 Mathematical Rigor
The presentation maintains strong mathematical rigor while remaining accessible. Many proofs are presented with careful intuition before formal derivation, which aids conceptual understanding.
4.3 Pedagogical Limitations
From a research perspective, certain limitations are notable:
1. Limited coverage of fine-grained complexity
2. Minimal discussion of parameterized complexity
3. Lack of extensive treatment of complexity in machine learning
These fields have become prominent in the past decade.
5. Open Problems -
The book naturally leads to several fundamental unresolved questions.
5.1 The P vs NP Problem
The central open question:
remains unresolved.
Its solution would fundamentally alter our understanding of computation, optimization, and cryptography.
5.2 Circuit Lower Bounds
A major challenge is proving that
5.3 Quantum Complexity
Quantum computation introduces complexity classes ,
whose relationship with classical complexity classes remains partially understood.
Research areas include:
• quantum PCP conjecture
• quantum supremacy
• complexity of quantum verification.
6. Emerging Research
6.1 Fine-Grained Complexity
Fine-grained complexity investigates exact polynomial exponents.
Examples include conjectures such as
• Strong Exponential Time Hypothesis (SETH)
• Orthogonal Vectors conjecture.
6.2 Complexity of Machine Learning
Modern AI systems raise new theoretical questions:
• complexity of training neural networks
• generalization bounds
• computational hardness of learning.
6.3 Algebraic and Geometric Complexity
The Geometric Complexity Theory program seeks to address complexity lower bounds using representation theory and algebraic geometry.
7. Interdisciplinary Perspectives
Future progress in complexity theory may emerge through connections with:
• statistical physics
• information theory
• quantum information
• biological computation.
These interdisciplinary approaches may provide new mathematical tools for addressing fundamental complexity questions.
8. Conclusion
Computational Complexity: A Modern Approach remains one of the most influential monographs in theoretical computer science. Its comprehensive treatment of complexity classes, proof systems, pseudorandomness, and circuit complexity provides a foundational framework for modern research.
Despite the emergence of new subfields since its publication, the book continues to serve as a cornerstone reference for graduate education and theoretical investigation. The open problems it highlights—particularly the P vs NP problem and circuit lower bounds—remain central challenges of mathematics and computer science.
References
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
Cook, S. (1971). The complexity of theorem-proving procedures. Proceedings of the ACM Symposium on Theory of Computing.
Karp, R. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations.
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998). Proof verification and hardness of approximation problems. Journal of the ACM.
Goldwasser, S., Micali, S., & Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing.
Babai, L. (1985). Trading group theory for randomness. Proceedings of STOC.
July 29, 2011
This is a very comprehensive and detailed book on computational complexity. Its target audience are the advanced undergraduates or the first-year graduate students in computational science or a related field. The book has many good and interesting exercises and is very suitable as a textbook. It can be used as a self-study textbook for researchers in other fields as well. However, the notation may not be too familiar to those who have not had any prior exposure to the topics in computational complexity. I am a theoretical Physicist and I consider myself to be fairly well versed in advanced mathematics, but I would probably want to read a book that is at a level just below this one in order to familiarize myself with the notational conventions. Otherwise, it is an extremely interesting and well-organized textbook.
May 21, 2018
The only book around that teaches the lower bound theory well.
March 25, 2019
It's better than Sipser's.
December 15, 2024
Good graduate text on complexity theory. Of all the complexity books out there I’d choose this one. Gives a very thorough survey of the field, starts with a basic review of Turing machines, NP-completeness, etc. Nice intro to some of the real topics in complexity: polynomial hierarchy, circuit complexity, interactive proofs, cryptography, etc.. Also includes a lot of advanced topics like derandomization and quantum computing. Definitely requires some math background - to understand everything in the book you need to know probability, linear algebra, and some group/ring theory. Each concept is accompanied by motivating commentary which makes it enjoyable, and chapters open with quotes providing nice historical context. The exercises are freaking hard but pedagogically effective. Overall a pretty hardcore book, definitely for grad students, but densely packed with information. Learned a lot from it.
March 27, 2021
This book broke my neck and I loved it. Essential if you are interested in theoretical CS.
September 2, 2016
great book covering a lot of modern topics. For a long time there was no textbook for material beyond Sipser's book but this book nicely fits in this gap and offers enough material for a graduate level course and more for personal exploration.
October 3, 2012
A great book helped me throught the computational complexity subject back when it was in the draf version. My name appears on page 12 ;)
February 12, 2016
A very comprehensive book on complexity. It is quite understandable and goes far beyond understanding the P = NP problem (which was my initial goal).
May 27, 2016
Excellent Book. Very well written. Contained a few typos in my edition but nevertheless, generates an interest in the subject.
January 29, 2023
Loved it!
Want to read
January 23, 2010recommended by Scott Aaronson as an advanced investigation into complexity
Read
May 19, 2019We worked through most of this book in a seminar for grad students, when it was new. Don't think it is for beginners in (theoretical) computer science, but it is decent for an extended intro into complexity theory.
Displaying 1 - 17 of 17 reviews