计算复杂性理论的研究是计算机科学*重要的研究领域之一，而Christos H．Papadmitriou是该领域***的专家之一。本书是一本全面阐述计算复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂性理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。
本书内容丰富，体系严谨，证明简洁，叙述深入浅出，并配有大量的练习和文献引用。本书不但适合作为研究生或本科高年级学生的教材，也适合从事算法和计算机复杂性研究的人员参考。

PART I:ALGORITHMS
1 Problems and Algorithms
1.1 Graph reachability
1.2 Maximum flow and matching
1.3 The traveling salesman problem
1.4 Notes,references,and problems
2 Turing machines
2.1 Turing machine basics
2.2 Turing machines as algorithms
2.3 Turing machines with multiple strings
2.4 Linear speedup
2.5 Space bounds
2.6 Random access machines
2.7 Nondeterministic machines
2.8 Notes,references,and problems
3 Undecidability
3.1 Universal Turing machines
3.2 The halting problem
3.3 More undecidability
3.4 Notes,references,and problems
PART II:LOGIC
4 Boolean logic
4.1 Boolean Expressions
4.2 Satisfiability and validity
4.3 Boolean functions and circuits
4.4 Notes,references,and problems
5 First-order logic
5.1 The syntax of first-order logic
5.2 Models
5.3 Valid expressions
5.4 Axioms and proofs
5.5 The completeness theorem
5.6 Consequences of the completeness theorem
5.7 Second-order logic
5.8 Notes,references,and problems
6 Undecidability in logic
6.1 Axioms for number theory
6.2 Computation as a number-theoretic concept
6.3 Undecidability and incompleteness
6.4 Notes,references,and problems
PART III:P AND NP
7 Relations between complexity classes
7.1 Complexity classes
7.2 The hierarchy theorem
7.3 The reachability method
7.4 Notes,references,and problems
8 Reductions and completeness
8.1 Reductions
8.2 Completeness
8.3 Logical characterizations
8.4 Notes,referencess,and problems
9 NP-complete problems
9.1 Problems in NP
9.2 Variants of satisfiability
9.3 Graph-theoretic problems
9.4 Sets and numbers
9.5 Notes,references,and problems
10 coNP and function problems
10.1 NP and coNP
10.2 Primality
10.3 Function problems
10.4 Notes,references,and problems
11 Randomized computation
11.1 Randomized algorithms
11.2 Randomized complexity classes
11.3 Random sources
11.4 Circuit complexity
11.5 Notes,references,and problems
12 Cryptography
12.1 One-way functions
12.2 Protocols
12.3 Notes,references,and problems
13 Approximability
13.1 Approximation algorithms
13.2 Approximation and complexity
13.3 Nonapproximability
13.4 Notes,references,and problems
14 On P vs.NP
14.1 The map of NP
14.2 Isomorphism and density
14.3 Oracles
14.4 Monotone circuits
14.5 Notes,references,and problems
PART IV:INSIDE P
15 Parallel computation
15.1 Parallel algorithms
15.2 Parallel models of computation
15.3 The class NC
15.4 RNC algorithms
15.5 Notes,references,and problems
16 Logarithmic space
16.1 The L=NL problem
16.2 Alternation
16.3 Undirected reachability
16.4 Notes,references,and problems
PART V:BEYOND NP
17 The polynomial hierarchy
17.1 Optimization problems
17.2 The hierarchy
17.3 Notes,references,and problems
18 Computation that counts
18.1 The permanent
18.2 The Class P
18.3 Notes,references,and problems
19 Polynomial space
19.1 Alternation and games
19.2 Games against nature and interactive protocols
19.3 More PSPACE-complete problems
19.4 Notes,references,and problems
20 A glimpse beyond
20.1 Exponential time
20.2 Notes,references,and problems
Index
Author index