复杂性理论(影印版)(精)/国外数学名著系列

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

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

1 Introduction
1.1 What Is Complexity Theory?
1.2 Didactic Background
1.3 Overview
1.4 Additional Literature
2 Algorithmic Problems & Their Complexity
2.1 What Are Algorithmic Problems?
2.2 Some Important Algorithmic Problems
2.3 Measuring Computation Time
2.4 The Complexity of Algorithmic Problems
3 Fundamental Complexity Classes
3.1 The Special Role of Polynomial Computation Time
3.2 Randomized Agorithms
3.3 The Fundamental Complexity Classes for Algorithmic Problems
3.4 The Fundamental Complexity Classes for Decision Problems
3.5 Nondeterminism as a Special Case of Randomization
4 Reductions-Algorithmic Relationships Between Problems
4.1 When Are Two Problems Algorithmically Similar?
4.2 Reductions Between Various Vaariants of a Problem
4.3 Reductions Between Related Problems
4.4 Reductions Between Unrelated Problems
4.5 The Special Role of Polynomial Reductions
5 The Theory of NP-Completeness
5.1 Fundamental Considerations
5.2 Problems in NP
5.3 Alternative Characterizations of NP
5.4 Cook s Theorem
6 NP-complete and NP-equivalent Problems
6.1 Fundamental Considerations
6.2 Traveling Salesperson Problems
6.3 Knapsack Problems
6.4 Partitioning and Scheduling Problems
6.5 Clique Problems
6.6 Team Building Problems
6.7 Championship Problems
7 The Complexity Analysis of Problems
7.1 The dividing Line Between Easy and Hard
7.2 Pseudo-polynomial Algorithms and Strong NP-comleteness
7.3 An Overview of the NP-competeness Proofs Considered
8 The Complexity of Approximation Problems-Classical Results
8.1 Complexity Classes
8.2 Approximation Algorithms
8.3 The Gap Technique
8.4 Approximation-Preserving Reductions
8.5 Complete Approximation Problems
9 The Complexity of Black Box Problems
9.1 Black Box Optimization
9.2 Yao s Minimax Principle
9.3 Lower Bounds for Black Box COmplexity
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

要使我国的数学事业更好地发展起来，需要数学家淡泊名利并付出更艰苦地努力。另一方面，我们也要从客观上为数学家创造更有利的发展数学事业的外部环境，这主要是加强对数学事业的支持与投资力度，使数学家有较好的工作与生活条件，其中也包括改善与加强数学的出版工作。... 从出版方面来讲，除了较好较快地出版我们自己的成果外，引进国外的先进出版物无疑也是十分重要与必不可少的。从数学来说，施普林格(Springer)出版社至今仍然是世界上最具权威的出版社。科学出版社影印一批他们出版的好的新书，使我国广大数学家能以较低的价格购买，特别是在边远地区工作的数学家能普遍见到这些书，无疑是对推动..