国外数学名著系列：复杂性理论（影印版）

　　1 Introduction
　　2 Algorithmic Problems & Their Complexity
　　3 Fundamental Complexity Classes
　　4 Reductions-Algorithmic Relationships Between Problems
　　5 The Theory of NP-Completeness
　　6 NP-complete and NP-equivalent Problems
　　7 The Complexity Analysis of Problems
　　8 The Complexity of Approximation Problems-Classical Results
　查看完整　　

　　    复杂性理论主要研究决定解决算法问题的必要资源，以及利用可用资源可能得到的结果的界，而对这些界的深入理解可以防止寻求不存在的所谓有效算法。复杂性理论的新分支随着新的算法概念而不断涌现，其产物——如NP一完备性理论——已经影响到计算机科学的所有领域的发展。《复杂性理论（影印版）》视随机化为一个关键概念，强调理论与实际应用的相互作用。《复杂性理论（影印版）》论题始终强调复杂性理论对于当今计算机科学的重要意义，包含各种具体应用。

　　1 Introduction
　　2 Algorithmic Problems & Their Complexity
　　3 Fundamental Complexity Classes
　　4 Reductions-Algorithmic Relationships Between Problems
　　5 The Theory of NP-Completeness
　　6 NP-complete and NP-equivalent Problems
　　7 The Complexity Analysis of Problems
　　8 The Complexity of Approximation Problems-Classical Results
　　9 The Complexity of Black Box Problems
　　10 Additional Complexity Classes
　　11 Interactive Proofs
　　12 The PCP Theorem and the Complexity of Approximation Problems
　　13 Further Topics From Classical Complexity Theory
　　14 The Complexity of Non-uniform Problems
　　15 Communication Complexity
　　16 The Complexity of Boolean Functions
　　Final Comments
　　A Appendix
　　A.1 Orders of Magnitude and O-Notation
　　A.2 Results from Probability Theory
　　References
　　Index
^ 收 起　　

　　    复杂性理论主要研究决定解决算法问题的必要资源，以及利用可用资源可能得到的结果的界，而对这些界的深入理解可以防止寻求不存在的所谓有效算法。复杂性理论的新分支随着新的算法概念而不断涌现，其产物——如NP一完备性理论——已经影响到计算机科学的所有领域的发展。《复杂性理论（影印版）》视随机化为一个关键概念，强调理论与实际应用的相互作用。《复杂性理论（影印版）》论题始终强调复杂性理论对于当今计算机科学的重要意义，包含各种具体应用。