齣版者的話
譯者序
前言
第一部分算法
第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注解、參考文獻和問題
索引
· · · · · · (收起)