☆☆☆☆☆
简体网页||繁体网页



点击这里下载

类似图书 点击查看全场最低价

---

内容简介

　　复杂性理论主要研究决定解决算法问题的必要资源，以及利用可用资源可能得到的结果的界，而对这些界的深入理解可以防止寻求不存在的所谓有效算法。复杂性理论的新分支随着新的算法概念而不断涌现，其产物——如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

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

类似图书 点击查看全场最低价