計算復雜性

目錄
Computational Complexity
出版者的話
譯者序
前言
第一部分算法
第1章問題與算法
11圖的可達性問題
12最大流問題
13旅行商問題
14注解、參考文獻和問題
第2章圖靈機
21圖靈機概述
22視為算法的圖靈機
23多帶圖靈機
24線性加速
25空間界
26隨機存取機
27非確定性機
28注解、參考文獻和問題
第3章不可判定性
31通用圖靈機
32停機問題
33更多不可判定性問題
34注解、參考文獻和問題
第二部分邏輯學
第4章布爾邏輯
41布爾表達式
42可滿足性與永真性
43布爾函數與電路
44注解、參考文獻和問題
第5章一階邏輯
51一階邏輯的語法
52模型
53永真的表達式
54公理和證明
55完備性定理
56完備性定理的推論
57二階邏輯
58注解、參考文獻和問題
第6章邏輯中的不可判定性
61數論公理
62作為一個數論概念的計算
63不可判定性與不完備性
64注解、參考文獻和問題
第三部分P和NP
第7章復雜性類之間的關系
71復雜性類
72譜系定理
73可達性方法
74注解、參考文獻和問題
第8章歸約和完備性
81歸約
82完全性
83邏輯特征
84注解、參考文獻和問題
第9章NP完全問題
91NP中的問題
92可滿足性問題的不同版本
93圖論問題
94集合和數字
95注解、參考文獻和問題
第10章coNP和函數問題
101NP和coNP
102素性
103函數問題
104注解、參考文獻和問題
第11章隨機計算
111隨機算法
112隨機復雜性類
113隨機源
114電路復雜性
115注解、參考文獻和問題
第12章密碼學
121單向函數
122協議
123注解、參考文獻和問題
第13章可近似性
131近似算法
132近似和復雜性
133不可近似性
134注解、參考文獻和問題
第14章關于P和NP
141NP的地圖
142同構和稠密性
143諭示
144單調電路
145注解、參考文獻和問題
第四部分P內部的計算復雜性類
第15章并行計算
151并行算法
152計算的并行模型
153NC類
154RNC算法
155注解、參考文獻和問題
第16章對數空間
161L=?NL問題
162交錯
163無向圖的可達性
164注解、參考文獻和問題
第五部分NP之外的計算復雜性類
第17章多項式譜系
171優(yōu)化問題
172多項式譜系
173注解、參考文獻和問題
第18章有關計數的計算
181積和式
182P類
183注解、參考文獻和問題
第19章多項式空間
191交錯和博弈
192對抗自然的博弈和交互協議
193更多的PSPACE完全問題
194注解、參考文獻和問題
第20章未來的展望
201指數時間復雜性類
202注解、參考文獻和問題
索引