本書是一本全面闡述計算機複雜性理論及其近年來進展的教科書，主要包含算法圖靈機、可計算性等有關計算複雜理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等複雜性理論的基礎知識；P與NP、NP完全等各複雜性類的概念及其之間的關係等複雜性理論的核心內容；隨機算法、近似算法、並行算法及其複雜性理論；以及NP之外如多項式空間等複雜性類的介紹。
本書內容豐富，體系嚴謹，證明簡潔，敘述深入淺出，並配有大量的練習和文獻引用。本書不但適合和作為研究生或本科生高年級學生的教材，也適合從事算法和計算機複雜性研究的人員參考。
書籍信息,內容簡介,圖書目錄,
書籍信息
作者：Christos H. Papadimitriou
定價：59元
印次：1-1
ISBN：9787302089551
出版日期：2004.09.01
印刷日期：2004.09.09
內容簡介
計算機複雜理論的研究是計算機科學最重要的研究領域之一，而Chistos.H.Papadimitriou是該領域最著名的專家之一。
圖書目錄
I.ALGORITHMS.
1.ProblemsandAlgorithms.
2.TuringMachines.
3.Undecidability.
II.LOGIC.
1.BooleanLogic.
2.FirstOrderLogic.
3.UndecidabilityinLogic.
III.PANDNP.
1.RelationsbetweenComplexityClasses.
2.ReductionsandCompleteness.
3.NP-CompleteProblems.
4.coNPandFunctionProblems.
5.RandomizedComputation.
6.Cryptography.
7.Approximability.
8.OnPvs.NP.
IV.INSIDEP.
1.ParallelComputation.
2.LogarithmicSpace.
V.BEYONDNP.
1.ThePolynomialHierarchy.
2.ComputationThatCounts.
3.PolynomialSpace.
4.AGlimpseBeyond.
