计算复杂性

　　目录
　　Computational Complexity
　　出版者的话
　　译者序
　　前言
　　部分算法
　　第1章问题与算法
　　11图的可达性问题
　　12流问题
　　13旅行商问题
　查看完整　　

　　计算机复杂理论的研究是计算机科学*重要的研究领域之一，而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注解、参考文献和问题
　　索引
　　 
^ 收 起　　

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