計算複雜性理論[Christos H. Papadimitriou著書籍]

本書是一本全面闡述計算機複雜性理論及其近年來進展的教科書，主要包含算法圖靈機、可計算性等有關計算複雜理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等複雜性理論的基礎知識；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.