☆☆☆☆☆




點擊這裡下載

類似圖書 點擊查看全場最低價

---

內容簡介

　　復雜性理論主要研究決定解決算法問題的必要資源，以及利用可用資源可能得到的結果的界，而對這些界的深入理解可以防止尋求不存在的所謂有效算法。復雜性理論的新分支隨著新的算法概念而不斷湧現，其産物——如NP一完備性理論——已經影響到計算機科學的所有領域的發展。《國外數學名著係列（影印版）8：復雜性理論》視隨機化為一個關鍵概念，強調理論與實際應用的相互作用。《國外數學名著係列（影印版）8：復雜性理論》論題始終強調復雜性理論對於當今計算機科學的重要意義，包含各種具體應用。

內頁插圖

目錄

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 R，ole of Polynomial Computation Time
3．2 Randomized Algorithms
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 Variants 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-completeness
7．3 An Overview of the NP completeness 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
10．1 Fundamental Considerations
10．2 Complexity Classes Within NP and co-NP
10．3 Oracle Classes
10．4 The Polynomial Hierarchy
10．5 BPP， NP， and． the Polynomial Hierarchy

11 Interactive Proofs
11．1 Fundamental Considerations
11．2 Interactive Proof Systems
11．3 Regarding the Complexity of Graph Isomorphism Problems
11．4 Zero-Knowledge Proofs

12 The PCP Theorem and the Complexity of Approximation Problems
12．1 Randomized Verification of Proofs
12．2 The PCP Theorem
12．3 The PCP Theorem and Inapproximability Results
12．4 The PCP Theorem and APX-Completeness

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

前言/序言

　　要使我國的數學事業更好地發展起來，需要數學傢淡泊名利並付齣更艱苦地努力。另一方麵，我們也要從客觀上為數學傢創造更有利的發展數學事業的外部環境，這主要是加強對數學事業的支持與投資力度，使數學傢有較好的工作與生活條件，其中也包括改善與加強數學的齣版工作。
　　從齣版方麵來講，除瞭較好較快地齣版我們自己的成果外，引進國外的先進齣版物無疑也是十分重要與必不可少的。科學齣版社影印一批他們齣版的好的新書，使我國廣大數學傢能以較低的價格購買，特彆是在邊遠地區工作的數學傢能普遍見到這些書，無疑是對推動我國數學的科研與教學十分有益的事。
　　這次科學齣版社購買瞭版權，一次影印瞭23本施普林格齣版社齣版的數學書，就是一件好事，也是值得繼續做下去的事情。大體上分一下，這23本書中，包括基礎數學書5本，應用數學書6本與計算數學書12本，其中有些書也具有交叉性質。這些書都是很新的，2000年以後齣版的占絕大部分，共計16本，其餘的也是1990年以後齣版的。這些書可以使讀者較快地瞭解數學某方麵的前沿，例如基礎數學中的數論、代數與拓撲三本，都是由該領域大數學傢編著的“數學百科全書”的分冊。對從事這方麵研究的數學傢瞭解該領域的前沿與全貌很有幫助。按照學科的特點，基礎數學類的書以“經典”為主，應用和計算數學類的書以“前沿”為主。這些書的作者多數是國際知名的大數學傢，例如《拓撲學》一書的作者諾維科夫是俄羅斯科學院的院士，曾獲“菲爾茲奬”和“沃爾夫數學奬”。這些大數學傢的著作無疑將會對我國的科研人員起到非常好的指導作用。
　　當然，23本書隻能涵蓋數學的一部分，所以，這項工作還應該繼續做下去。更進一步，有些讀者麵較廣的好書還應該翻譯成中文齣版，使之有更大的讀者群。總之，我對科學齣版社影印施普林格齣版社的部分數學著作這一舉措錶示熱烈的支持，並盼望這一工作取得更大的成績。
國外數學名著係列（影印版）8：復雜性理論 [Complexity Theory] 下載 mobi epub pdf txt 電子書

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

類似圖書 點擊查看全場最低價

查看全網最低價