计算复杂性

目录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和conp102素性103函数问题104注解、参考文献和问题第11章随机计算111随机算法112随机复杂性类113随机源114电路复杂性115注解、参考文献和问题第12章密码学121单向函数122协议123注解、参考文献和问题第13章可近似性131近似算法132近似和复杂性133不可近似性134注解、参考文献和问题第14章关于p和np141np的地图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注解、参考文献和问题索引