計(jì)算復(fù)雜性

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