计算复杂性

目录

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优化问题

172多项式谱系

173注解、参考文献和问题

第18章有关计数的计算

181积和式

182P类

183注解、参考文献和问题

第19章多项式空间

191交错和博弈

192对抗自然的博弈和交互协议

193更多的PSPACE完全问题

194注解、参考文献和问题

第20章未来的展望

201指数时间复杂性类

202注解、参考文献和问题

索引