計算複雜性理論

本書是一本全面闡述計算機複雜性理論及其近年來進展的教科書，主要包含演演算法圖靈機、可計算性等有關計算複雜理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等複雜性理論的基礎知識；P與NP、NP完全等各複雜性類的概念及其之間的關係等複雜性理論的核心內容；隨機演演算法、近似演演算法、并行演演算法及其複雜性理論；以及NP之外如多項式空間等複雜性類的介紹。

本書內容豐富，體系嚴謹，證明簡潔，敘述深入淺出，並配有大量的練習和文獻引用。本書不但適合和作為研究生或本科生高年級學生的教材，也適合從事演演算法和計算機複雜性研究的人員參考。