《複雜性理論(影印版)》一書視隨機化為一個關鍵概念，強調理論與實際套用的相互作用。《複雜性理論(影印版)》論題始終強調複雜性理論對於當今計算機科學的重要意義，包含各種具體套用。
基本介紹
- 書名：複雜性理論
- 頁數： 308頁
- 裝幀：精裝
- 開本：16
圖書信息,作者簡介,內容簡介,目錄,
圖書信息
出版社: 科學出版社; 第1版 (2006年1月1日)
叢書名: 國外數學名著系列
正文語種: 簡體中文, 英語
ISBN: 7030166922, 9787030166920
條形碼: 9787030166920
尺寸: 24.6 x 17.4 x 1.9 cm
重量: 640 g
作者簡介
作者：(德)韋格納
內容簡介
《複雜性理論(影印版)》內容簡介：複雜性理論主要研究決定解決算法問題的必要資源，以及利用可用資源可能得到的結果的界，而對這些界的深入理解可以防止尋求不存在的所謂有效算法。複雜性理論的新分支隨著新的算法概念而不斷湧現，其產物——如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
