计算复杂性

出版时间：2004-9  出版社：清华大学出版社  作者：帕帕李米特里乌  
Tag标签：无  

内容概要

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

书籍目录

PART I：ALGORITHMS1 Problems and Algorithms1.1 Graph reachability1.2 Maximum flow and matching1.3 The traveling salesman problem1.4 Notes，references，and problems2 Turing machines2.1 Turing machine basics2.2 Turing machines as algorithms2.3 Turing machines with multiple strings2.4 Linear speedup2.5 Space bounds2.6 Random access machines2.7 Nondeterministic machines2.8 Notes，references，and problems3 Undecidability3.1 Universal Turing machines3.2 The halting problem3.3 More undecidability3.4 Notes，references，and problemsPART II：LOGIC4 Boolean logic4.1 Boolean Expressions4.2 Satisfiability and validity4.3 Boolean functions and circuits4.4 Notes，references，and problems5 First-order logic5.1 The syntax of first-order logic5.2 Models5.3 Valid expressions5.4 Axioms and proofs5.5 The completeness theorem5.6 Consequences of the completeness theorem5.7 Second-order logic5.8 Notes，references，and problems6 Undecidability in logic6.1 Axioms for number theory6.2 Computation as a number-theoretic concept6.3 Undecidability and incompleteness6.4 Notes，references，and problemsPART III：P AND NP7 Relations between complexity classes7.1 Complexity classes7.2 The hierarchy theorem7.3 The reachability method7.4 Notes，references，and problems8 Reductions and completeness8.1 Reductions8.2 Completeness8.3 Logical characterizations8.4 Notes，referencess，and problems9 NP-complete problems9.1 Problems in NP9.2 Variants of satisfiability9.3 Graph-theoretic problems9.4 Sets and numbers9.5 Notes，references，and problems10 coNP and function problems10.1 NP and coNP10.2 Primality10.3 Function problems10.4 Notes，references，and problems11 Randomized computation11.1 Randomized algorithms11.2 Randomized complexity classes11.3 Random sources11.4 Circuit complexity11.5 Notes，references，and problems12 Cryptography12.1 One-way functions12.2 Protocols12.3 Notes，references，and problems13 Approximability13.1 Approximation algorithms13.2 Approximation and complexity13.3 Nonapproximability13.4 Notes，references，and problems14 On P vs.NP14.1 The map of NP14.2 Isomorphism and density14.3 Oracles14.4 Monotone circuits14.5 Notes，references，and problemsPART IV：INSIDE P15 Parallel computation15.1 Parallel algorithms15.2 Parallel models of computation15.3 The class NC15.4 RNC algorithms15.5 Notes，references，and problems16 Logarithmic space16.1 The L=NL problem16.2 Alternation16.3 Undirected reachability16.4 Notes，references，and problemsPART V：BEYOND NP17 The polynomial hierarchy17.1 Optimization problems17.2 The hierarchy17.3 Notes，references，and problems18 Computation that counts18.1 The permanent18.2 The Class P18.3 Notes，references，and problems19 Polynomial space19.1 Alternation and games19.2 Games against nature and interactive protocols19.3 More PSPACE-complete problems19.4 Notes，references，and problems20 A glimpse beyond20.1 Exponential time20.2 Notes，references，and problemsIndexAuthor index

用户评论 (总计1条)

•   　　内容非常全面，证明非常多，但是基本是首先用自然语言阐述思想，其次才用形式化证明，因此一改传统上复杂性证明的晦涩难懂的特点。此外，注重证明方法和技巧的介绍。附有很多习题均来自实际的复杂性研究的课题或者以发表的论文，因此想从事复杂性研究的读者可以通过做这些习题获得很大的提升余地。
  　　
  　　这本书应该是我见过的最权威，最全面，最系统，也是叙述最好的复杂性理论的书。作者Papadimitriou是UCSD的教授，也是复杂性研究领域的权威。