![複雜性理論[出版物]](/img/7/696/nBnauM3X2UjN3IzNzYDO5ATM4QTMzMzN4IDM0QTNwAzMwIzL2gzLygzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg "複雜性理論[出版物]")
內容簡介
複雜性理論主要研究決定解決算法問題的必要資源，以及利用可用資源可能得到的結果的界，而對這些界的深入理解可以防止尋求不存在的所謂有效算法。複雜性理論的新分支隨著新的算法概念而不斷湧現，其產物——如NP一完備性理論——已經影響到計算機科學的所有領域的發展。
圖書目錄
1 Introduction
2 Algorithmic Problems & Theircomplexity
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
