計算復雜性是計算機科學中思考為什麼有些問題
用計算機難以解決的領域，是理論計算機科學研究的
重要內容。克裡斯特斯H.帕帕季米特裡烏所著的《計
算復雜性》重點介紹復雜性的計算、問題和邏輯。本
書包含五部分：第一部分介紹算法，包括問題與算法
、圖靈機、不可判定性；第二部分介紹邏輯學，包括
布爾邏輯、一階邏輯和邏輯中的不可判定性；第三部
分介紹P和NP，包括復雜性類之間的關繫、歸約和完
備性、NP完全問題、coNP和函數問題、隨機計算、密
碼學、可近似性等；第四部分介紹P內部的計算復雜
性，包括並行計算、對數空間；第五部分介紹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.1 NP中的問題
9.2 可滿足性問題的不同版本
9.3 圖論問題
9.4 集合和數字
9.5 注解、參考文獻和問題
**0章 coNP和函數問題
10.1 NP和coNP
10.2 素性
10.3 函數問題
10.4 注解、參考文獻和問題
**1章 隨機計算
11.1 隨機算法
11.2 隨機復雜性類
11.3 隨機源
11.4 電路復雜性
11.5 注解、參考文獻和問題
**2章 密碼學
12.1 單向函數
12.2 協議
12.3 注解、參考文獻和問題
**3章 可近似性
13.1 近似算法
13.2 近似和復雜性
13.3 不可近似性
13.4 注解、參考文獻和問題
**4章 關於P和NP
14.1 NP的地圖
14.2 同構和稠密性
14.3 諭示
14.4 單調電路
14.5 注解、參考文獻和問題
第四部分 P內部的計算復雜性類
**5章 並行計算
15.1 並行算法
15.2 計算的並行模型
15.3 NC類
15.4 RNC算法
15.5 注解、參考文獻和問題
**6章 對數空間
16.1 L?=NL問題
16.2 交錯
16.3 無向圖的可達性
16.4 注解、參考文獻和問題
第五部分 NP之外的計算復雜性類
**7章 多項式譜繫
17.1 優化問題
17.2 多項式譜繫
17.3 注解、參考文獻和問題
**8章 有關計數的計算
18.1 積和式
18.2 P類
18.3 注解、參考文獻和問題
**9章 多項式空間
19.1 交錯和博弈
19.2 對抗自然的博弈和交互協議
19.3 *多的PSPACE**問題
19.4 注解、參考文獻和問題
第20章 未來的展望
20.1 指數時間復雜性類
20.2 注解、參考文獻和問題
索引