大学计算机教育国外著名教材系列：计算复杂性（影印版）

　　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

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