复杂性理论

图书标准信息

• 作者 [德]韦格纳 著
• 出版社 科学出版社
• 出版时间 2006-01
• 版次 1
• ISBN 9787030166920
• 定价 66.00元
• 装帧 精装
• 开本 16开
• 纸张 胶版纸
• 页数 308页
• 字数 380千字
• 正文语种 简体中文，英语

【内容简介】

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

【目录】

1Introduction
2AlgorithmicProblems&TheirComplexity
3FundamentalComplexityClasses
4Reductions-AlgorithmicRelationshipsBetweenProblems
5TheTheoryofNP-Completeness
6NP-completeandNP-equivalentProblems
7TheComplexityAnalysisofProblems
8TheComplexityofApproximationProblems-ClassicalResults
9TheComplexityofBlackBoxProblems
10AdditionalComplexityClasses
11InteractiveProofs
12ThePCPTheoremandtheComplexityofApproximationProblems
13FurtherTopicsFromClassicalComplexityTheory
14TheComplexityofNon-uniformProblems
15CommunicationComplexity
16TheComplexityofBooleanFunctions
FinalComments
AAppendix
A.1OrdersofMagnitudeandO-Notation
A.2ResultsfromProbabilityTheory
References
Index