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

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