計算複雜性 计算复杂性

<內容簡介>

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

<章節目錄>

出版者的話
譯者序
前言
第一部分算法
第1章問題與算法
1.1圖的可達性問題
1.2最大流問題
1.3旅行商問題
1.4註解、參考文獻和問題
第2章圖靈機
2.1圖靈機概述
2.2視為算法的圖靈機
2.3多帶圖靈機
2.4線性加速
2.5空間界
2.6隨機存取機
2.7非確定性機
2.8註解、參考文獻和問題
第3章不可判定性
3.1通用圖靈機
3.2停機問題
3.3更多不可判定性問題
3.4註解、參考文獻和問題
第二部分邏輯學
第4章布爾邏輯
4.1布爾表達式
4.2可滿足性與永真性
4.3布爾函數與電路
4.4註解、參考文獻和問題
第5章一階邏輯
5.1一階邏輯的語法
5.2模型
5.3永真的表達式
5.4公理和證明
5.5完備性定理
5.6完備性定理的推論
5.7二階邏輯
5.8註解、參考文獻和問題
第6章邏輯中的不可判定性
6.1數論公理
6.2作為一個數論概念的計算
6.3不可判定性與不完備性
6.4註解、參考文獻和問題
第三部分P和NP
第7章複雜性類之間的關係
7.1複雜性類
7.2譜系定理
7.3可達性方法
7.4註解、參考文獻和問題
第8章歸約和完備性
8.1歸約
8.2完全性
8.3邏輯特徵
8.4註解、參考文獻和問題
第9章NP完全問題
9.1NP中的問題
9.2可滿足性問題的不同版本
9.3圖論問題
9.4集合和數字
9.5註解、參考文獻和問題
第10章coNP和函數問題
10.1NP和coNP
10.2素性
10.3函數問題
10.4註解、參考文獻和問題
第11章隨機計算
11.1隨機算法
11.2隨機複雜性類
11.3隨機源
11.4電路複雜性
11.5註解、參考文獻和問題
第12章密碼學
12.1單向函數
12.2協議
12.3註解、參考文獻和問題
第13章可近似性
13.1近似算法
13.2近似和復雜性
13.3不可近似性
13.4註解、參考文獻和問題
第14章關於P和NP
14.1NP的地圖
14.2同構和稠密性
14.3諭示
14.4單調電路
14.5註解、參考文獻和問題
第四部分P內部的計算複雜性類
第15章並行計算
15.1並行算法
15.2計算的並行模型
15.3NC類
15.4RNC算法
15.5註解、參考文獻和問題
第16章對數空間
16.1L=？NL問題
16.2交錯
16.3無向圖的可達性
16.4註解、參考文獻和問題
第五部分NP之外的計算複雜性類
第17章多項式譜系
17.1優化問題
17.2多項式譜系
17.3註解、參考文獻和問題
第18章有關計數的計算
18.1積和式
18.2P類
18.3註解、參考文獻和問題
第19章多項式空間
19.1交錯和博弈
19.2對抗自然的博弈和交互協議
19.3更多的PSPACE完全問題
19.4註解、參考文獻和問題
第20章未來的展望
20.1指數時間複雜性類
20.2註解、參考文獻和問題
索引

<作者介紹>

作者：（美國）克裡斯特斯H.帕帕季米特裡烏（Christos H.Papadimitriou）譯者：朱洪彭超卜天明克裡斯特斯H.帕帕季米特裡烏（Christos H.Papadimitriou）是當今計算機科學界最活躍和有影響力的科學家之一。Papadimitriou擁有普林斯頓大學博士學位，現為加州大學伯克利分校計算機科學系教授。他曾在哈佛大學、麻省理工學院、雅典工藝大學、斯坦福大學、加州大學聖地亞哥分校任教。他是美國科學院院士、美國工程院院士和美國人文科學院院士。他於2002年獲得高德納獎，2012年獲得哥德爾獎。他的主要研究領域是算法和復雜性，以及它們在優化、數據庫、人工智能、經濟和因特網等方面的應用，曾撰寫此領域教科書5本，發表論文數篇。