English
In 1971, Stephen Cook proved that Boolean satisfiability was NP-complete and posed P vs. NP. In 1972, Richard Karp showed that twenty-one natural combinatorial problems were the same problem in different disguises. Within a decade, the catalogue of NP-complete problems had grown to thousands. This initial success created a misleading impression: that complexity theory was primarily a technology for classifying problems as easy or hard, a service discipline for algorithm designers who needed to know whether to keep searching or give up.
Complexity theory as it is actually practiced is something different. It is the mathematical study of the structure of computational difficulty — what kinds of hardness exist, how different kinds of hardness relate to each other, and why the central questions about this structure have resisted resolution for half a century. The subject produces specific results (this problem is in this class, this inclusion is strict), but the results are vehicles for understanding a deeper mathematical structure that is still only partially charted. The difference between using NP-completeness results and doing complexity theory is the difference between using a map and making one.
This section extends the theory of computation (§3.2) into the contemporary research territory that §3.2’s third layer — complexity — only introduces. The prerequisites are Sipser-level computability and complexity, discrete mathematics (§2.2) at depth, and mathematical maturity sufficient for graduate-level mathematics. This is not a trunk subject in the sense that §3.2 is; it is for readers who want to understand complexity theory as it is currently practiced, not only as a classification system.
Prerequisites: Theory of computation (§3.2) — Sipser-level coverage of P, NP, and NP-completeness is required. Discrete mathematics (§2.2) at depth. Algorithms (§2.6). Logic (§3.1) enriches the material through descriptive complexity.
After NP-Completeness: How Complexity Theory Became a Mathematical Discipline
The first decade after Cook’s theorem was a period of expansion. NP-completeness reductions spread rapidly: problems in scheduling, combinatorics, graph theory, operations research, bioinformatics, and cryptography were reduced to SAT or to each other, building the catalogue that Garey and Johnson’s 1979 Computers and Intractability organized into a reference. The technique of polynomial-time reduction had become a standard tool. But the catalogue was not complexity theory; it was the application of complexity theory.
The deeper work had already started. In the early 1970s, Ladner proved that if P ≠ NP, there exist problems in NP that are neither in P nor NP-complete — a class of problems now called NP-intermediate. This showed that the structure inside NP was richer than the binary easy/hard distinction suggested. The polynomial hierarchy, defined by Stockmeyer in 1976, organized problems harder than NP but below PSPACE into a tower of alternating quantifier classes, each containing problems not in the one below it (assuming plausible separations). Space complexity classes — L, NL, PSPACE, EXPSPACE — completed a different axis of the landscape. By 1980, complexity theory had a rich geography rather than a single landmark.
The entry of randomness changed everything. The class BPP — problems solvable in polynomial time by a probabilistic algorithm with bounded error — was defined by Gill in 1977. Adleman showed in 1978 that BPP ⊆ P/poly (polynomial-size circuit families), connecting randomized computation to non-uniform computation. Schwartz-Zippel’s polynomial identity testing algorithm (1980) showed that randomness could solve specific problems provably faster than any known deterministic algorithm, raising the question of whether BPP = P. Today, most complexity theorists believe BPP = P — that every randomized polynomial-time algorithm can be derandomized — but no proof exists. Pseudorandom generators, which fool polynomial-time algorithms using shorter seeds, are the tool for derandomization, and their existence is connected to circuit lower bounds in a web of conditional results that remains one of the most intricate structures in the subject.
Interactive proof systems — protocols where a computationally bounded verifier checks claims made by an unbounded prover — transformed understanding of what verification meant. The class IP (problems verifiable by polynomial-time probabilistic interaction) was defined by Babai and Goldwasser independently in 1985. The IP = PSPACE theorem, proved by Shamir in 1992, was stunning: problems requiring full polynomial space could be checked interactively in polynomial time. The proof used arithmetization — converting logical formulas into low-degree polynomials — to let the verifier sample the prover’s claims algebraically. Arithmetization would return as the central technique of the PCP theorem.
The PCP theorem, proved by Arora, Lund, Motwani, Sudan, and Szegedy in 1992, is the deepest result complexity theory has produced. PCP stands for Probabilistically Checkable Proof: the theorem says that every NP problem has a proof format in which the verifier needs to read only a constant number of bits (randomly chosen) to check correctness with high probability. Equivalently, approximate satisfiability — deciding whether a 3-SAT formula can be satisfied by at least 7/8 of its clauses — is NP-hard. The immediate consequence was a systematic theory of hardness of approximation: many optimization problems were not only NP-hard to solve exactly but NP-hard to approximate within any constant factor. The gap amplification technique in the proof — showing that the “proof gap” between satisfiable and far-from-satisfiable instances can be amplified by local operations — became a foundational tool. The Unique Games Conjecture (Khot, 2002), which posits that a specific structured version of constraint satisfaction is NP-hard to approximate, implies tight hardness results for dozens of optimization problems including max-cut. Whether the Unique Games Conjecture is true remains open; the question has driven a decade of work in both algorithms and complexity.
The barrier theorems arrived as the field began to understand why its central questions were so hard. Baker, Gill, and Solovay proved in 1975 that P vs. NP cannot be resolved by relativizing techniques — techniques that work uniformly whether or not the algorithms have access to an oracle. Since most known techniques relativize, this eliminated most of the standard proof methods. Razborov and Rudich proved in 1994 the natural proofs barrier: any proof technique that satisfies two mild conditions (constructivity and largeness) cannot separate P from NP if one-way functions exist. Since most combinatorial circuit lower bound techniques satisfy these conditions, and since one-way functions are widely believed to exist (their nonexistence would collapse cryptography), most known lower bound techniques are barred. Aaronson and Wigderson proved the algebrization barrier in 2008: techniques that are “algebraically relativizing” — that work uniformly under certain algebraic extensions — cannot resolve P vs. NP or several related questions. The three barriers together imply that resolving P vs. NP requires genuinely new techniques that are non-relativizing, non-natural, and non-algebrizing. No such technique is currently known to work.
Quantum complexity emerged as a distinct subfield in the 1990s. BQP — problems solvable in polynomial time on a quantum computer — contains some problems believed to be outside P: Shor’s factoring algorithm (1994) implies that factoring integers, the basis of RSA cryptography, is in BQP. Whether BQP contains NP is unknown; most believe it does not (quantum computers are not believed to solve NP-complete problems efficiently). The quantum analogue of NP — QMA, quantum Merlin-Arthur — contains problems like the local Hamiltonian problem (deciding ground state energy of quantum systems), a problem with physical significance and complexity-theoretic depth. The relationship between quantum and classical complexity is a major open frontier.
Fine-grained complexity, developed primarily by Virginia Vassilevska Williams and colleagues in the 2010s, introduced a new perspective: not only whether problems are polynomial-time, but how their polynomial complexity compares. The Strong Exponential Time Hypothesis (SETH), which asserts that satisfying n-variable k-SAT requires time exponential in n, implies specific lower bounds on polynomial-time algorithms: edit distance cannot be computed in o(n^{1.5}) time, diameter of a graph cannot be computed in o(n^2) time (under SETH), and hundreds of other tight bounds. These results revealed a web of conditional equivalences among seemingly unrelated polynomial-time problems, analogous to the NP-completeness web but within polynomial time. Whether SETH is true is itself open.
What this history establishes is that complexity theory’s deepest subject matter is not the classification of specific problems but the structure of computational difficulty itself — how different kinds of hardness relate, why the techniques that work in limited models fail in general, and what new mathematical ideas are needed to make progress. The field has been unusually self-aware about its own limits, which is why barrier theorems are among its central results.
The Structure of Hardness
Complexity Classes and Their Relationships
A complexity class is a set of problems defined by a resource bound and a machine model. P is the set of problems decidable by a deterministic machine in polynomial time. NP is the set decidable by a nondeterministic machine in polynomial time — equivalently, the set with polynomial-time verifiable solutions. PSPACE is the set decidable with polynomial space. The exponential time classes EXPTIME and NEXPTIME allow exponential time. The oracle classes allow the machine access to an oracle.
The major known relationships: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, and PSPACE ⊆ EXPTIME is strict (padding argument). The strictness of P ⊆ EXPTIME follows from the time hierarchy theorem, which says that with more time, strictly more problems can be solved. Whether P ⊊ NP is the fundamental open question; whether NP ⊊ PSPACE is also open. The polynomial hierarchy PH is the union of the levels Σ_k^P and Π_k^P for all k, defined by alternating nondeterministic quantifiers. If PH does not collapse, it is an infinite hierarchy of distinct complexity classes strictly between NP and PSPACE.
The randomized classes BPP and RP are inside PSPACE, and under widely believed assumptions, inside the polynomial hierarchy. The counting class #P — the class of problems counting the number of accepting paths of a nondeterministic polynomial-time machine — is outside NP (unless PH collapses) and inside PSPACE. Toda’s theorem (1991) shows that the polynomial hierarchy is contained in P^{#P}, making #P surprisingly powerful.
Interactive proof classes reveal the power of interaction. MA (Merlin-Arthur) is a one-round version of IP where the prover sends a polynomial-length message and the verifier decides in polynomial time. AM is the two-round version. IP = PSPACE collapses the prover-verifier hierarchy into a single class at PSPACE. MIP (multiple interactive provers) is even more powerful: MIP = NEXPTIME (Babai, Fortnow, Lund, 1991). MIP*, which allows quantum entanglement between the provers, equals RE — the class of all computably enumerable languages — a 2020 result (Ji, Natarajan, Vidick, Wright, Yuen) that shocked the field and resolved a twenty-year-old question in operator algebra (the Connes embedding conjecture) as a byproduct.
Lower Bounds: The Hard Direction
Upper bounds on complexity — showing a problem is in a given class — are established by exhibiting an algorithm. Lower bounds — showing a problem requires significant resources — require proving that no algorithm can succeed, which is the genuinely hard direction in complexity theory. The field’s major open problems are all lower bound questions.
Circuit complexity attacks lower bounds through the combinatorial structure of Boolean circuits. A circuit is an acyclic directed graph of AND, OR, and NOT gates computing a Boolean function. Size (number of gates) and depth (length of longest path) are the complexity measures. The class P/poly consists of problems solvable by polynomial-size circuit families; NP ⊄ P/poly would imply P ≠ NP. Circuit lower bounds have been proved for restricted circuit classes: AC^0 (constant-depth circuits of polynomial size with unbounded fan-in AND and OR gates) cannot compute parity, by Furst-Saxe-Sipser (1984) and the exponential lower bound by Håstad (1986). TC^0 (constant-depth threshold circuits) cannot compute integer multiplication, by a result of Allender. These results use techniques — the switching lemma, algebraic arguments — that do not generalize to unrestricted circuits. Proving super-polynomial lower bounds on general circuits remains open, despite decades of effort.
Communication complexity, defined by Yao in 1979, studies a two-party computation: Alice has input x, Bob has input y, and together they compute f(x, y) while minimizing the bits communicated. Communication complexity lower bounds are proved directly, using combinatorial arguments (fooling sets, rank bounds, discrepancy). These lower bounds transfer to circuit lower bounds, time-space tradeoffs, and other settings. Communication complexity has become one of the most productive sources of techniques in the field, because its restricted model is tractable and its bounds transfer broadly.
Query complexity (also called decision tree complexity) studies the number of queries to the input bits needed to compute a function. Randomized and quantum query complexities are also defined. The polynomial method — showing that any function computing f must have a polynomial representing it of high degree, and hence high query complexity — is one of the major lower bound techniques. Quantum speedups can be shown by proving separations between classical and quantum query complexity; the quantum query complexity of unstructured search is Θ(√n) by Grover’s algorithm, proved tight by the polynomial method.
Proof complexity studies the length of proofs in proof systems — propositional resolution, cutting planes, Frege systems, and extensions. Lower bounds on proof length imply lower bounds on SAT algorithm running times, connecting proof complexity to practical SAT solving. Resolution lower bounds are proved by width arguments; cutting planes lower bounds by the Stabbing planes technique; the field has made substantial progress on restricted systems while general Frege system lower bounds remain open.
The PCP Theorem and Hardness of Approximation
The PCP theorem is the organizing result of a substantial subfield. Its content — that NP ⊆ PCP(O(log n), O(1)) — says that every NP language has a proof system where the verifier uses O(log n) random bits and reads O(1) proof bits, accepting with probability 1 for yes-instances and rejecting with probability at least 1/2 for no-instances.
The consequence for approximation is direct. If a problem is NP-hard to compute exactly, and if the promise problem distinguishing instances with optimum value V from instances where the maximum achievable is αV is also NP-hard, then no polynomial-time algorithm achieves approximation ratio better than α unless P = NP. The PCP theorem and its relatives provide the machinery for proving such inapproximability results.
The Unique Games Conjecture (UGC) strengthens this further. The conjecture posits that the “unique games” constraint satisfaction problem — where each constraint involves two variables and specifies a unique mapping from the values of one to the values of the other — is NP-hard to approximate in a specific sense. If UGC is true, the Goemans-Williamson algorithm for max-cut (which achieves approximation ratio ≈ 0.878) is optimal, the best possible approximation for vertex cover is 2, and tight inapproximability for dozens of problems follows. UGC is more controversial than P ≠ NP — some researchers believe it is false and that Goemans-Williamson can be beaten — and it drives a productive tension between algorithm designers and complexity theorists.
The 2022 resolution of the parallel repetition theorem’s tight version (Dinur, Filmus, Harsha, and Safra) and recent progress on 2-to-2 games illustrate that the PCP and approximation frontier is actively developing, not settled.
What Studying This Changes
Complexity theory at depth changes how a practitioner understands computational limits in a way that introductory coverage does not.
The first change is seeing the architecture of hardness. At the introductory level, NP-hardness looks like a binary classification: hard or not hard. At depth, the architecture is visible: approximate hardness (PCP), average-case hardness (one-way functions), fine-grained hardness (SETH-based bounds), parameterized tractability (FPT). Each regime has different techniques, different assumptions, and different consequences for algorithm design. The practitioner who has seen this architecture can ask more precise questions: not just “is this NP-hard?” but “is it hard to approximate? hard on average? hard for specific polynomial bounds?”
The second change is understanding why the central questions are hard to prove. The barrier theorems establish that standard techniques cannot resolve P vs. NP. A practitioner who has worked through the natural proofs barrier understands that it is not merely difficult to prove P ≠ NP — it is provably beyond the class of techniques that most researchers use. This understanding changes the research posture: rather than attacking the major open problems directly, serious complexity theorists develop techniques that do not fall into known barriers, or prove more refined results within the scope of current techniques.
The third change is access to the research literature. Complexity theory research papers assume the framework and vocabulary developed in Arora-Barak and related texts. A practitioner who has worked through this material can read and evaluate current papers, follow developments at the research frontier, and understand why specific results are considered significant. Without this foundation, the literature is nearly impenetrable.
Resources
Books and Texts
Arora and Barak’s Computational Complexity: A Modern Approach (2009, free draft at theory.cs.princeton.edu) is the canonical graduate text and the one book that covers the contemporary state of complexity theory comprehensively. It develops the polynomial hierarchy, randomized complexity, interactive proofs and the PCP theorem, circuit complexity, derandomization, communication complexity, hardness of approximation, average-case complexity, and quantum complexity with complete proofs. The writing is clear and the organization reflects the field’s actual conceptual structure rather than historical accident. For any reader who wants to engage with modern complexity theory, Arora-Barak is the required foundation. Reading it cover to cover is not realistic for most learners; working through selected chapters based on one’s interests, returning to fill gaps as they arise, is the standard approach.
Goldreich’s Computational Complexity: A Conceptual Perspective (2008) offers an alternative organization around conceptual commitments rather than results. Where Arora-Barak emphasizes completeness, Goldreich emphasizes conceptual clarity and attempts to develop the subject from first principles. The book is more idiosyncratic and harder to use as a reference, but it illuminates aspects of the field’s structure that Arora-Barak’s comprehensive approach sometimes obscures. Reading both produces a more complete picture than either alone.
Avi Wigderson’s Mathematics and Computation (2019, free at math.ias.edu/avi/book) is a monograph by one of the field’s leading figures that connects complexity theory to mathematics broadly — combinatorics, algebra, geometry, analysis, probability. It is not a textbook (it has no exercises and does not develop proofs systematically) but a meditation on how complexity theory fits into the mathematical landscape. Reading it provides the intellectual context that Arora-Barak does not aim for.
For specific subareas: Kushilevitz and Nisan’s Communication Complexity (1997) for communication complexity; Jukna’s Boolean Function Complexity (2012) for circuit lower bounds; Immerman’s Descriptive Complexity (1999) for the connections between logic and complexity classes; Cygan et al.’s Parameterized Algorithms (2015, free at parameterizedcomplexity.org) for the FPT framework; Bogdanov and Trevisan’s Average-Case Complexity (survey, free) for average-case analysis. Ryan O’Donnell’s Analysis of Boolean Functions (Cambridge, paid; free author PDF available) is the standard route into Fourier analysis on the Boolean cube, with applications to circuit complexity, hardness of approximation, learning theory, pseudorandomness, and social choice. It is a depth resource, not an entry point.
Scott Aaronson’s Quantum Computing Since Democritus (2013) places quantum complexity in a broader context of philosophy, mathematics, and computation. It is accessible to non-specialists and essential for understanding why quantum complexity matters beyond the technical results.
| Book | Role | Type |
|---|---|---|
| Arora & Barak, Computational Complexity (free draft) | Canonical graduate text | Entry |
| Goldreich, Computational Complexity: A Conceptual Perspective | Alternative conceptual organization | Depth |
| Wigderson, Mathematics and Computation (free) | Context and connections to mathematics | Depth |
| Kushilevitz & Nisan, Communication Complexity | Communication complexity | Depth |
| Jukna, Boolean Function Complexity | Circuit lower bounds | Depth |
| O’Donnell, Analysis of Boolean Functions (paid; free author PDF) | Boolean Fourier analysis for TCS | Depth |
| Immerman, Descriptive Complexity | Logic-complexity connections | Depth |
| Cygan et al., Parameterized Algorithms (free) | FPT framework | Depth |
| Bogdanov & Trevisan, Average-Case Complexity (free survey) | Average-case analysis | Depth |
| Aaronson, Quantum Computing Since Democritus | Quantum complexity with context | Depth |
Courses and Lectures
Princeton’s graduate complexity course (based on Arora-Barak, taught by Arora, materials freely available at theory.cs.princeton.edu) is the most polished free course materials for the subject. Arora’s lecture notes develop the material with additional context and worked examples that the textbook compresses.
MIT 6.841 (Advanced Complexity Theory) and Harvard CS 221 (Computational Complexity) have freely available materials that complement Arora-Barak. The MIT materials include lecture notes by Ryan Williams and others that cover fine-grained complexity and recent developments not in the textbook.
Scott Aaronson’s complexity theory course at UT Austin (materials at scottaaronson.com) covers the subject with characteristic engagement. His lectures on the barrier theorems, the PCP theorem, and quantum complexity are particularly strong.
The Computational Complexity Conference (CCC) tutorial talks, available on the ECCC website and YouTube, provide accessible introductions to specific current topics by leading researchers. These are the right entry points for specific subareas at the research frontier.
| Course | Platform | Type |
|---|---|---|
| Princeton graduate complexity (Arora, free) | theory.cs.princeton.edu | Entry |
| Aaronson complexity theory course (free) | scottaaronson.com | Depth |
| MIT 6.841 Advanced Complexity (free) | MIT course site | Depth |
| CCC tutorial talks (free) | ECCC / YouTube | Reference |
Practice, Tools, and Current Sources
The Complexity Zoo (complexityzoo.net) is the essential reference for the catalogue of complexity classes, maintained by the community. Use it to look up classes as they arise in reading; attempting to read it systematically is not productive.
The ECCC (Electronic Colloquium on Computational Complexity, eccc.weizmann.ac.il) is the standard preprint server for complexity theory. Reading the abstracts of recent papers develops a sense of what the field is currently working on.
Blogs: Shtetl-Optimized (Scott Aaronson), Computational Complexity (Lance Fortnow), and Gödel’s Lost Letter and P=NP (Dick Lipton and Ken Regan) are the primary venues for complexity-theoretic discourse aimed at a technically prepared but non-specialist audience. Reading them regularly is how working complexity theorists stay connected to the community’s intellectual life.
The Simons Institute for the Theory of Computing (Berkeley, simons.berkeley.edu) hosts semester-long programs on complexity-related topics and makes all talks available on YouTube. The talks are at varying levels; the tutorials and workshop introductions are particularly useful for learners approaching new subareas.
TCS+ is an online seminar in theoretical computer science with talks aimed at a broad technical audience. It is a good way to follow active research without needing to attend a local theory seminar, though it should be treated as current exposure rather than as a structured learning path.
| Resource | Platform | Type |
|---|---|---|
| Complexity Zoo (free) | complexityzoo.net | Reference |
| ECCC preprint server (free) | eccc.weizmann.ac.il | Reference |
| Aaronson, Fortnow, Lipton-Regan blogs (free) | Various | Reference |
| Simons Institute talks (free) | YouTube / simons.berkeley.edu | Reference |
| TCS+ online seminar (free) | tcsplus.org | Reference |
Traps
| Trap | Why it misleads | Better response |
|---|---|---|
| Treating complexity theory as a classification service | NP-completeness reductions are the entry point, but the subject’s intellectual content is the structure of computational difficulty — why hardness has the form it does, how different kinds of hardness relate, what the barriers to understanding it are. A practitioner who uses complexity only to classify new problems as easy or hard has acquired the application without the subject. | Read Arora-Barak’s introductory chapter and Wigderson’s Mathematics and Computation for the structural perspective before working through specific results. Ask, for each major result, what it reveals about the structure of computational difficulty rather than only what classification it produces. |
| Attempting P vs. NP without preparation | The major open problems attract learners who have just encountered them, before they have the preparation to engage seriously. No progress on P vs. NP has been made by anyone without substantial complexity-theoretic preparation, and the barrier theorems establish that standard techniques are provably insufficient. Premature engagement wastes time and produces discouragement. | Treat P vs. NP as the long-term horizon, not the immediate target. Build preparation by working through Arora-Barak systematically, engaging with the barrier theorems, and developing facility with the actual techniques that contemporary research uses. The problem will be more approachable, and the engagement more productive, after this preparation. |
| Confusing conditional and unconditional results | Complexity theory contains both unconditional results (proved from nothing: the time hierarchy theorem, specific circuit lower bounds) and conditional results (proved assuming P ≠ NP, or SETH, or UGC). Conflating them produces incorrect conclusions: it is not a theorem that NP-hard problems are hard on average, or that SETH-based lower bounds are tight, or that UGC implies the Goemans-Williamson bound is optimal. These are conditional on conjectures that may be false. | Be explicit about the assumption when stating any result. Maintain a mental distinction between what is proved and what is conjectured. The complexity zoo’s distinction between known and conjectured relationships is the right model for how to track these distinctions in reading. |
| Reading without working through proofs | Complexity theory results are stated clearly in Arora-Barak, and it is possible to read the book quickly by reading statements and skipping proofs. The result is a collection of facts without understanding, because the techniques — gap amplification, arithmetization, the switching lemma, polynomial identity testing — are what the subject actually consists of. The proofs are the content. | Work through proofs in detail, at least for the major results. For the PCP theorem, work through the gap amplification technique step by step before reading the full proof. For circuit lower bounds, work through Håstad’s switching lemma with concrete examples. The technique is what transfers to new problems; the specific result does not. |
| Missing the connections to cryptography and algorithms | Complexity theory is not self-contained. The natural proofs barrier connects to the existence of one-way functions. Derandomization connects to pseudorandom generators and hardness-versus-randomness tradeoffs. Hardness of approximation connects to the Unique Games Conjecture and to the design of approximation algorithms. A learner who treats complexity theory as isolated from these connections misses much of its significance. | Study complexity theory alongside Vadhan’s Pseudorandomness for the derandomization connections, alongside Williamson-Shmoys’s Approximation Algorithms for the hardness-of-approximation connections, and alongside cryptography (§4.5) for the one-way functions connections. The connections are not optional supplements but integral to understanding why specific results matter. |
| Stopping at NP and PSPACE | The complexity zoo contains dozens of classes beyond NP and PSPACE that are scientifically significant: #P (counting), BPP and RP (randomness), IP and MA (interaction), BQP and QMA (quantum), the fine-grained classes (ETH, SETH). A learner who knows only NP and PSPACE has the vocabulary for a small fraction of contemporary complexity research. | After Sipser’s coverage of the basics, extend through the major classes in Arora-Barak. BPP and the derandomization conjecture, #P and Toda’s theorem, IP = PSPACE, and the quantum classes are the most important extensions. |
中文
1971 年，Stephen Cook 证明布尔可满足性是 NP 完全的，并提出了 P vs. NP 问题。1972 年，Richard Karp 证明二十一个自然组合问题，其实是同一个问题的不同伪装。不到十年，NP 完全问题目录已经增长到数千个。这一最初成功造成了一种误导性印象：复杂性理论主要是一种把问题分类为容易或困难的技术，是服务于算法设计者的一门辅助学科，让他们知道应该继续寻找算法，还是该放弃。
但复杂性理论在实际研究中是另一种东西。它是对计算困难结构的数学研究——困难有哪些种类，不同种类的困难如何彼此关联，以及为什么关于这种结构的核心问题已经半个世纪没有被解决。这个主题会产生具体结果，例如某个问题属于某个类、某个包含关系是严格的；但这些结果只是理解更深数学结构的载体，而这张结构地图至今仍只被部分绘制出来。使用 NP 完全性结果和从事复杂性理论之间的区别，就像使用地图和绘制地图之间的区别。
本节把计算理论（§3.2）推进到当代研究区域，而 §3.2 的第三层——复杂性——只是对这个区域的引入。前置知识包括 Sipser 水平的可计算性与复杂性、较深入的离散数学（§2.2），以及足以进入研究生水平数学的数学成熟度。它不是 §3.2 那种意义上的主干主题；它面向的是那些想理解复杂性理论当下如何被研究，而不只是把它当成分类系统的读者。
前置知识：计算理论（§3.2）——需要掌握 Sipser 水平的 P、NP 和 NP 完全性。较深入的离散数学（§2.2）。算法（§2.6）。逻辑（§3.1）会通过描述复杂性丰富本节内容。
NP 完全性之后：复杂性理论如何成为一门数学学科
Cook 定理之后的第一个十年，是一个扩张时期。NP 完全性归约迅速传播：调度、组合学、图论、运筹学、生物信息学和密码学中的问题被归约到 SAT 或彼此归约，形成了由 Garey 和 Johnson 1979 年的 Computers and Intractability 组织成参考书的目录。多项式时间归约技术已经成为标准工具。但目录本身不是复杂性理论；它只是复杂性理论的应用。
更深层的工作早已开始。1970 年代初，Ladner 证明，如果 P ≠ NP，那么 NP 中存在既不在 P 中、也不是 NP 完全的问题——这类问题如今被称为 NP-intermediate。这说明 NP 内部结构比“容易/困难”的二分所暗示的更丰富。Stockmeyer 在 1976 年定义的多项式层级，把比 NP 更难、但低于 PSPACE 的问题组织成由交替量词类构成的塔；在合理分离假设下，每一层都包含不在下一层以下的问题。空间复杂性类——L、NL、PSPACE、EXPSPACE——补全了这张图景的另一条轴。到 1980 年，复杂性理论已经拥有一片丰富地理，而不只是一个单一地标。
随机性的进入改变了一切。BPP 类——可以由有界错误的概率多项式时间算法求解的问题——由 Gill 在 1977 年定义。Adleman 在 1978 年证明 BPP ⊆ P/poly，也就是 BPP 包含于多项式大小电路族，从而把随机计算连接到非一致计算。Schwartz-Zippel 多项式恒等性测试算法（1980）表明，随机性可以在特定问题上证明性地快于任何已知确定性算法，由此提出了 BPP 是否等于 P 的问题。今天，多数复杂性理论学者相信 BPP = P——也就是每个随机多项式时间算法都可以去随机化——但没有证明。伪随机生成器用较短种子欺骗多项式时间算法，是去随机化的工具；而它们的存在又与电路下界相连，构成一张条件性结果网络，是本学科中最复杂精细的结构之一。
交互式证明系统改变了人们对验证含义的理解。这类协议中，一个计算受限的验证者会检查一个无限能力证明者提出的主张。IP 类，即可由多项式时间概率交互验证的问题，由 Babai 和 Goldwasser 在 1985 年分别独立定义。Shamir 在 1992 年证明的 IP = PSPACE 定理令人震惊：需要完整多项式空间的问题，可以通过交互在多项式时间内被检查。证明使用了算术化——把逻辑公式转化为低次数多项式——使验证者能够用代数方式抽样检查证明者的主张。算术化后来又作为 PCP 定理的核心技术回归。
PCP 定理由 Arora、Lund、Motwani、Sudan 和 Szegedy 在 1992 年证明，是复杂性理论产生过的最深结果。PCP 意为 Probabilistically Checkable Proof，即概率可检验证明：该定理说明，每个 NP 问题都有一种证明格式，使验证者只需读取常数个随机选择的比特，就能以高概率检查正确性。等价地，近似可满足性——判断一个 3-SAT 公式是否至少能满足其 7/8 的子句——是 NP-hard 的。直接后果是形成了系统化的不可近似性理论：许多优化问题不仅精确求解是 NP-hard 的，而且在任何常数因子内近似也是 NP-hard 的。证明中的 gap amplification 技术——显示可满足实例与远离可满足实例之间的“证明间隙”可以通过局部操作被放大——成为基础工具。Unique Games Conjecture（Khot，2002）断言，一种特定结构的约束满足问题很难近似；如果它成立，就会推出包括 max-cut 在内的几十个优化问题的紧致困难性结果。Unique Games Conjecture 是否为真仍然悬而未决；这个问题推动了算法与复杂性两个方向十多年的工作。
当这个领域开始理解其核心问题为何如此困难时，障碍定理也随之出现。Baker、Gill 和 Solovay 在 1975 年证明，P vs. NP 不能由相对化技术解决——所谓相对化技术，是指无论算法是否能访问 oracle，都统一有效的技术。由于大多数已知技术都会相对化，这一结果排除了大多数标准证明方法。Razborov 和 Rudich 在 1994 年证明了自然证明障碍：如果单向函数存在，那么任何满足两个温和条件（构造性和大性）的证明技术，都无法分离 P 与 NP。由于多数组合式电路下界技术满足这些条件，而单向函数又被广泛认为存在（如果不存在，密码学会崩塌），大多数已知下界技术都被排除。Aaronson 和 Wigderson 在 2008 年证明了代数化障碍：那些“代数相对化”的技术——即在某些代数扩展下统一有效的技术——不能解决 P vs. NP 或若干相关问题。三个障碍合在一起表明，解决 P vs. NP 需要真正新的技术：非相对化、非自然、非代数化。目前还没有已知技术能够做到这一点。
量子复杂性在 1990 年代成为独立子领域。BQP——量子计算机可以在多项式时间内求解的问题——包含一些被认为不在 P 中的问题：Shor 的整数分解算法（1994）说明，RSA 密码学所依赖的整数分解在 BQP 中。BQP 是否包含 NP 仍然未知；多数人相信不包含，也就是说，量子计算机通常不被认为能高效求解 NP 完全问题。NP 的量子类比是 QMA，即 quantum Merlin-Arthur；其中包含局部 Hamiltonian 问题，也就是判断量子系统基态能量的问题。这一问题既有物理意义，也有复杂性理论深度。量子复杂性与经典复杂性之间的关系，是一个重要开放前沿。
细粒度复杂性主要由 Virginia Vassilevska Williams 及其合作者在 2010 年代发展起来，它引入了新的视角：不只是问问题是否为多项式时间，还要问它们的多项式复杂度如何比较。强指数时间假设（SETH）断言，满足 n 个变量的 k-SAT 需要关于 n 的指数时间；它会推出具体的多项式时间算法下界：编辑距离不能在 o(n^{1.5}) 时间内计算，图直径不能在 o(n^2) 时间内计算（在 SETH 下），以及数百个其他紧致下界。这些结果揭示了看似无关的多项式时间问题之间的一张条件等价网络，类似于 NP 完全性网络，但发生在多项式时间内部。SETH 本身是否为真仍然未知。
这段历史确立的是：复杂性理论最深层的主题，不是对具体问题进行分类，而是计算困难本身的结构——不同困难如何关联，为什么在受限模型中有效的技术在一般情况下失效，以及要取得进展需要什么新的数学思想。这个领域对自身局限具有异常强的自觉，这也解释了为什么障碍定理会成为其核心结果之一。
困难性的结构
复杂性类及其关系
复杂性类，是由资源界限和机器模型定义的一组问题。P 是确定性机器可以在多项式时间内判定的问题集合。NP 是非确定性机器可以在多项式时间内判定的问题集合；等价地，它也是拥有多项式时间可验证解的问题集合。PSPACE 是可以用多项式空间判定的问题集合。指数时间类 EXPTIME 和 NEXPTIME 允许指数时间。Oracle 类则允许机器访问一个 oracle。
主要已知关系是：P ⊆ NP ⊆ PSPACE ⊆ EXPTIME，并且 PSPACE ⊆ EXPTIME 是严格的（通过 padding argument）。P ⊆ EXPTIME 的严格性来自时间层级定理，即更多时间可以严格求解更多问题。P ⊊ NP 是否成立，是根本开放问题；NP ⊊ PSPACE 是否成立也仍然开放。多项式层级 PH 是所有 Σ_k^P 和 Π_k^P 层的并集，由交替非确定性量词定义。如果 PH 不坍缩，它就是位于 NP 和 PSPACE 之间、由彼此不同复杂性类组成的无限层级。
随机类 BPP 和 RP 位于 PSPACE 内，并且在广泛相信的假设下位于多项式层级内。计数类 #P——计算非确定性多项式时间机器接受路径数量的问题类——位于 NP 之外（除非 PH 坍缩），并位于 PSPACE 内。Toda 定理（1991）显示，多项式层级包含于 P^{#P}，这使 #P 显得异常强大。
交互式证明类揭示了交互的力量。MA（Merlin-Arthur）是 IP 的一轮版本，其中证明者发送一个多项式长度消息，验证者在多项式时间内决定。AM 是两轮版本。IP = PSPACE 把证明者—验证者层级坍缩到 PSPACE 这一类。MIP（多个交互式证明者）甚至更强：MIP = NEXPTIME（Babai、Fortnow、Lund，1991）。MIP* 允许证明者之间存在量子纠缠，它等于 RE——也就是所有可计算枚举语言的类。这是 Ji、Natarajan、Vidick、Wright、Yuen 在 2020 年得到的结果，震动了整个领域，并作为副产品解决了算子代数中二十年悬而未决的问题，即 Connes 嵌入猜想。
下界：困难的方向
复杂性的上界——证明一个问题属于某个类——通常通过给出算法来建立。下界——证明一个问题需要大量资源——则要求证明没有任何算法能成功，而这才是复杂性理论中真正困难的方向。这个领域的主要开放问题，几乎都是下界问题。
电路复杂性通过布尔电路的组合结构来攻击下界。电路是由 AND、OR 和 NOT 门构成的无环有向图，用来计算布尔函数。大小，也就是门的数量；以及深度，也就是最长路径长度，是其复杂性度量。P/poly 类包含可由多项式大小电路族求解的问题；如果 NP ⊄ P/poly，则可推出 P ≠ NP。对于受限电路类，已经证明了电路下界：AC^0（常数深度、多项式大小、AND 和 OR 门具有无界扇入的电路）不能计算奇偶性，这是 Furst-Saxe-Sipser（1984）和 Håstad（1986）的指数下界结果。TC^0（常数深度阈值电路）不能计算整数乘法，这是 Allender 的结果。这些结果使用的技术——switching lemma、代数论证——无法推广到无受限电路。对一般电路证明超多项式下界，尽管几十年来持续努力，仍然开放。
通信复杂性由 Yao 在 1979 年定义，研究一种两方计算：Alice 拥有输入 x，Bob 拥有输入 y，二者共同计算 f(x, y)，同时最小化通信比特数。通信复杂性下界可以直接用组合论证证明，例如 fooling sets、rank bounds、discrepancy。这些下界可以转移到电路下界、时间—空间权衡以及其他设定中。通信复杂性已经成为该领域最有生产力的技术来源之一，因为它的受限模型可处理，而其界限又能广泛转移。
查询复杂性，也叫 decision tree complexity，研究计算一个函数需要查询多少个输入比特。随机查询复杂性和量子查询复杂性也可以定义。多项式方法——证明任何计算 f 的函数都必须由高次数多项式表示，从而具有高查询复杂性——是主要下界技术之一。量子加速可以通过证明经典查询复杂性与量子查询复杂性之间的分离来展示；无结构搜索的量子查询复杂性由 Grover 算法给出，为 Θ(√n)，而该界限可由多项式方法证明为紧的。
证明复杂性研究证明系统中的证明长度——命题归结、cutting planes、Frege 系统及其扩展。证明长度下界会推出 SAT 算法运行时间下界，从而把证明复杂性连接到实际 SAT 求解。归结下界通过宽度论证证明；cutting planes 下界通过 Stabbing planes 技术证明；该领域在受限系统上取得了大量进展，而一般 Frege 系统下界仍然开放。
PCP 定理与不可近似性
PCP 定理是一个重要子领域的组织性结果。其内容——NP ⊆ PCP(O(log n), O(1))——说明每个 NP 语言都有一个证明系统，其中验证者使用 O(log n) 个随机比特，读取 O(1) 个证明比特；对 yes 实例以概率 1 接受，对 no 实例至少以 1/2 概率拒绝。
它对近似的后果是直接的。如果一个问题精确求解是 NP-hard 的，并且区分最优值为 V 的实例与最大可达值为 αV 的实例这一 promise problem 也是 NP-hard 的，那么除非 P = NP，不存在多项式时间算法能获得优于 α 的近似比。PCP 定理及其相关结果，提供了证明这类不可近似性结果所需的机制。
Unique Games Conjecture（UGC）进一步强化了这一点。该猜想断言，unique games 约束满足问题——其中每个约束涉及两个变量，并指定从一个变量取值到另一个变量取值的唯一映射——在某个特定意义下是 NP-hard 近似的。如果 UGC 为真，那么 Goemans-Williamson 的 max-cut 算法（近似比约为 0.878）就是最优的；vertex cover 的最佳可能近似比是 2；几十个问题的紧致不可近似性也随之推出。UGC 比 P ≠ NP 更有争议——有些研究者认为它是假的，并且认为 Goemans-Williamson 可以被超越——它也在算法设计者与复杂性理论学者之间形成了富有生产力的张力。
2022 年 parallel repetition theorem 紧致版本的解决（Dinur、Filmus、Harsha 和 Safra），以及近期关于 2-to-2 games 的进展，都说明 PCP 与近似前沿仍在活跃发展，并未定型。
学习这个主题会改变什么
深入学习复杂性理论，会以入门覆盖无法做到的方式改变实践者对计算极限的理解。
第一种变化，是看见困难性的架构。在入门层面，NP-hard 看起来像一种二元分类：困难或不困难。深入之后，架构变得可见：近似困难性（PCP）、平均情况困难性（单向函数）、细粒度困难性（基于 SETH 的界限）、参数化可处理性（FPT）。每个区域都有不同技术、不同假设，也对算法设计产生不同后果。看见这种架构的实践者，可以提出更精确的问题：不只是“它是否 NP-hard？”，而是“它是否难以近似？平均情况下是否困难？针对特定多项式界限是否困难？”
第二种变化，是理解为什么核心问题难以证明。障碍定理表明，标准技术不能解决 P vs. NP。认真推导过自然证明障碍的实践者会理解：证明 P ≠ NP 不只是困难；它被证明超出了多数研究者所使用的一类技术的能力范围。这种理解会改变研究姿态：严肃的复杂性理论学者不会直接冲击主要开放问题，而是发展不落入已知障碍的新技术，或者在当前技术范围内证明更精细的结果。
第三种变化，是进入研究文献。复杂性理论研究论文预设 Arora-Barak 以及相关文本发展出来的框架和词汇。认真学习过这些材料的实践者，可以阅读和评估当前论文，跟随研究前沿发展，并理解为什么某些具体结果被认为重要。没有这层基础，相关文献几乎无法进入。
资源
书籍与文本
Arora 和 Barak 的 Computational Complexity: A Modern Approach（2009，theory.cs.princeton.edu 有免费草稿）是经典研究生教材，也是唯一一本全面覆盖当代复杂性理论状态的书。它以完整证明发展多项式层级、随机复杂性、交互式证明与 PCP 定理、电路复杂性、去随机化、通信复杂性、不可近似性、平均情况复杂性和量子复杂性。写作清晰，组织方式反映了这个领域真正的概念结构，而不是历史偶然。对于任何想进入现代复杂性理论的读者，Arora-Barak 是必要基础。对多数学习者来说，从头到尾通读并不现实；根据自己的兴趣选择章节学习，并在遇到缺口时回头补全，是标准做法。
Goldreich 的 Computational Complexity: A Conceptual Perspective（2008）提供了另一种组织方式，它围绕概念承诺而不是结果展开。Arora-Barak 强调完整性；Goldreich 则强调概念清晰，并试图从第一原则发展这门学科。这本书更个人化，也更难作为参考书使用，但它会照亮 Arora-Barak 的综合路径有时会遮蔽的领域结构侧面。两本一起读，会比单独读任何一本得到更完整图景。
Avi Wigderson 的 Mathematics and Computation（2019，可在 math.ias.edu/avi/book 免费获取）是该领域领军人物写的一部专著，把复杂性理论与更广泛的数学连接起来——组合、代数、几何、分析、概率。它不是教材，没有习题，也不系统发展证明，而是一部关于复杂性理论如何嵌入数学景观的思考性作品。阅读它可以获得 Arora-Barak 并不试图提供的智识语境。
具体子领域方面：Kushilevitz 和 Nisan 的 Communication Complexity（1997）用于通信复杂性；Jukna 的 Boolean Function Complexity（2012）用于电路下界；Immerman 的 Descriptive Complexity（1999）用于逻辑与复杂性类之间的连接；Cygan 等人的 Parameterized Algorithms（2015，parameterizedcomplexity.org 免费）用于 FPT 框架；Bogdanov 和 Trevisan 的 Average-Case Complexity（免费综述）用于平均情况分析。Ryan O’Donnell 的 Analysis of Boolean Functions（Cambridge，付费；作者 PDF 免费可得）是进入布尔立方上的 Fourier 分析的标准路径，应用包括电路复杂性、不可近似性、学习理论、伪随机性和社会选择。这是深度资源，不是入门点。
Scott Aaronson 的 Quantum Computing Since Democritus（2013）把量子复杂性放入哲学、数学和计算的更广语境中。它对非专家可读，也是理解量子复杂性为何不只关乎技术结果的关键读物。
| 书籍 | 作用 | 类型 |
|---|---|---|
| Arora & Barak，Computational Complexity（免费草稿） | 经典研究生教材 | 入门 |
| Goldreich，Computational Complexity: A Conceptual Perspective | 另一种概念组织方式 | 深入 |
| Wigderson，Mathematics and Computation（免费） | 语境，以及与数学的连接 | 深入 |
| Kushilevitz & Nisan，Communication Complexity | 通信复杂性 | 深入 |
| Jukna，Boolean Function Complexity | 电路下界 | 深入 |
| O’Donnell，Analysis of Boolean Functions（付费；作者 PDF 免费） | 面向 TCS 的布尔 Fourier 分析 | 深入 |
| Immerman，Descriptive Complexity | 逻辑—复杂性连接 | 深入 |
| Cygan 等，Parameterized Algorithms（免费） | FPT 框架 | 深入 |
| Bogdanov & Trevisan，Average-Case Complexity（免费综述） | 平均情况分析 | 深入 |
| Aaronson，Quantum Computing Since Democritus | 带语境的量子复杂性 | 深入 |
课程与讲座
Princeton 的研究生复杂性课程（基于 Arora-Barak，由 Arora 讲授，材料可在 theory.cs.princeton.edu 免费获取）是这个主题上最完善的免费课程材料。Arora 的讲义加入了额外语境和 worked examples，可以补充教材中压缩处理的部分。
MIT 6.841（Advanced Complexity Theory）和 Harvard CS 221（Computational Complexity）都有免费课程材料，可以补充 Arora-Barak。MIT 材料包括 Ryan Williams 等人的讲义，覆盖细粒度复杂性和教材中没有的新近发展。
Scott Aaronson 在 UT Austin 的复杂性理论课程（材料在 scottaaronson.com）以他一贯的投入方式讲授这个主题。他关于障碍定理、PCP 定理和量子复杂性的讲座尤其强。
Computational Complexity Conference（CCC） 的教程报告可在 ECCC 网站和 YouTube 获取，由该领域一线研究者为具体当前主题提供可进入的介绍。这些是进入研究前沿中具体子领域的合适入口。
| 课程 | 平台 | 类型 |
|---|---|---|
| Princeton graduate complexity（Arora，免费） | theory.cs.princeton.edu | 入门 |
| Aaronson complexity theory course（免费） | scottaaronson.com | 深入 |
| MIT 6.841 Advanced Complexity（免费） | MIT 课程网站 | 深入 |
| CCC tutorial talks（免费） | ECCC / YouTube | 参考 |
实践、工具与当前来源
Complexity Zoo（complexityzoo.net）是复杂性类目录的核心参考，由社区维护。遇到具体复杂性类时用它查询；试图系统阅读它并不高效。
ECCC（Electronic Colloquium on Computational Complexity，eccc.weizmann.ac.il）是复杂性理论的标准预印本服务器。阅读近期论文摘要，可以培养对这个领域当前正在研究什么的感觉。
博客：Shtetl-Optimized（Scott Aaronson）、Computational Complexity（Lance Fortnow）以及 Gödel’s Lost Letter and P=NP（Dick Lipton 和 Ken Regan）是复杂性理论话语面向技术准备充分但非专家读者的主要场所。定期阅读它们，是工作中的复杂性理论学者保持与共同体智识生活连接的一种方式。
Simons Institute for the Theory of Computing（Berkeley，simons.berkeley.edu）会围绕复杂性相关主题举办为期一学期的项目，并在 YouTube 公开所有报告。报告难度不一；教程和 workshop 引入报告尤其适合学习者进入新子领域。
TCS+ 是理论计算机科学在线研讨会，报告面向较广泛的技术听众。它是跟踪活跃研究的好方式，不需要参加本地理论研讨会；不过应把它视为当前暴露，而不是结构化学习路径。
| 资源 | 平台 | 类型 |
|---|---|---|
| Complexity Zoo（免费） | complexityzoo.net | 参考 |
| ECCC preprint server（免费） | eccc.weizmann.ac.il | 参考 |
| Aaronson、Fortnow、Lipton-Regan 博客（免费） | 多种平台 | 参考 |
| Simons Institute talks（免费） | YouTube / simons.berkeley.edu | 参考 |
| TCS+ online seminar（免费） | tcsplus.org | 参考 |
陷阱
| 陷阱 | 为什么会误导 | 更好的回应 |
|---|---|---|
| 把复杂性理论当成分类服务 | NP 完全性归约是入口，但这个主题的智识内容是计算困难的结构——为什么困难会以这种形式出现，不同困难如何关联，理解它们的障碍在哪里。只把复杂性用于把新问题分类为容易或困难的实践者，获得的是应用，而不是这门学科本身。 | 在进入具体结果之前，先读 Arora-Barak 的引言章节和 Wigderson 的 Mathematics and Computation，获得结构性视角。面对每个主要结果时，问它揭示了计算困难结构中的什么，而不只是它给出了什么分类。 |
| 没有准备就试图解决 P vs. NP | 主要开放问题会吸引刚接触它们的学习者，而他们还没有足够准备进行严肃参与。没有深厚复杂性理论准备的人，从未在 P vs. NP 上取得进展；障碍定理还表明，标准技术已经被证明不足。过早投入会浪费时间并制造挫败。 | 把 P vs. NP 视为长期地平线，而不是眼前目标。通过系统学习 Arora-Barak、理解障碍定理，并熟悉当代研究实际使用的技术来建立准备。经过这些准备之后，这个问题会更可进入，参与也更有生产力。 |
| 混淆条件结果与无条件结果 | 复杂性理论既包含无条件结果，也就是不依赖假设的证明，例如时间层级定理、特定电路下界；也包含条件结果，例如假设 P ≠ NP、SETH 或 UGC 后得到的结果。混淆二者会产生错误结论：NP-hard 问题平均情况下困难并不是定理；基于 SETH 的下界紧致并不是定理；UGC 推出 Goemans-Williamson 界限最优，也是条件性结论。这些都依赖可能为假的猜想。 | 陈述任何结果时，都要明确其假设。保持“已证明内容”和“猜想内容”之间的心理区分。Complexity Zoo 对已知关系和猜想关系的区分，是阅读中追踪这些差异的正确模型。 |
| 阅读时不推证明 | Arora-Barak 中的复杂性理论结果表述清楚，因此可以通过只读陈述、跳过证明来快速读完。这样得到的是一组事实，而不是理解，因为技术——gap amplification、算术化、switching lemma、多项式恒等性测试——才是这个主题真正由之构成的东西。证明就是内容。 | 至少对主要结果，要详细推导证明。对于 PCP 定理，先逐步理解 gap amplification 技术，再进入完整证明。对于电路下界，用具体例子推导 Håstad 的 switching lemma。能够迁移到新问题的是技术，而不是某个具体结果。 |
| 错过与密码学和算法的连接 | 复杂性理论不是自足孤岛。自然证明障碍连接到单向函数的存在。去随机化连接到伪随机生成器和 hardness-versus-randomness 取舍。不可近似性连接到 Unique Games Conjecture 和近似算法设计。把复杂性理论当成与这些联系隔绝的学习者，会错过其大部分意义。 | 与 Vadhan 的 Pseudorandomness 一起学习复杂性理论，以理解去随机化连接；与 Williamson-Shmoys 的 Approximation Algorithms 一起学习，以理解不可近似性连接；并与密码学（§4.5）一起学习，以理解单向函数连接。这些连接不是可选补充，而是理解具体结果为何重要的组成部分。 |
| 停留在 NP 和 PSPACE | 复杂性动物园中有许多 NP 和 PSPACE 之外、具有科学意义的类：#P（计数）、BPP 和 RP（随机性）、IP 和 MA（交互）、BQP 和 QMA（量子）、细粒度类（ETH、SETH）。只知道 NP 和 PSPACE 的学习者，只拥有理解当代复杂性研究一小部分内容所需的词汇。 | 在 Sipser 覆盖基础之后，通过 Arora-Barak 扩展到主要复杂性类。BPP 与去随机化猜想、#P 与 Toda 定理、IP = PSPACE，以及量子复杂性类，是最重要的扩展。 |