计算复杂性

　　计算机复杂理论的研究是计算机科学*重要的研究领域之一，而Chistos.H.Papadimitriou是该领域*著名的专家之一。本书是一本全面阐述计算机复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。

暂缺《计算复杂性》作者简介

目录
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注解、参考文献和问题
索引