计算复杂性

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

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 problemsPART 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 problemsPART 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 problemsPART 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 problemsPART 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 problemsIndexAuthor index

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