计算复杂性(原版影印科技书）

本书涵盖了从计算复杂性理论的基础知识到近年新成果的所有内容。本书统一介绍了计算复杂性，将计算、应用和逻辑融为一体。

本书全面且通俗易懂地阐述了算法和复杂性理论——这是计算机科学家在过去半个世纪中为研究计算机算法的性能和局限性而开发的一系列优雅的概念和方法。本书涵盖的主题包括：约简和NP完全性、密码学？？和协议、随机算法、优化问题的近似性、电路复杂性、P=NP问题的“结构”方面、并行计算、多项式层次等等。本书以相当浅显易懂的方式呈现了一些复杂的最新成果，而更多的成果则以详尽的注释、习题和提示的形式展开。本书内容丰富，涵盖了可计算性、逻辑、数论、组合学和概率等多个领域的所有必要数学前提。

克里斯托斯·帕帕迪米特里奥（Christos Papadimitriou），美国国家科学院院士、国家工程院院士、美国人文与科学院院士，伯克利加州大学计算机科学系C. Lester Hogan教授、西蒙斯计算理论研究所高级科学家，他因在复杂度理论等方面的贡献于2002年获得高德纳奖，2012年获得哥德尔奖。

第一部分 算法
第1章 问题与算法
第2章 图灵机
第3章 不可判定性
第二部分 逻辑学
第4章 布尔逻辑
第5章 一阶逻辑
第6章 逻辑中的不可判定性
第三部分 P和NP
第7章 复杂性类之间的关系
第8章 归约和完备性
第9章 NP完全问题
第10章 coNP和函数问题
第11章 随机计算
第12章 密码学
第13章 可近似性
第14章 关于P和NP
第四部分 P内部的计算复杂性类
第15章 并行计算
第16章 对数空间
第五部分 NP之外的计算复杂性类
第17章 多项式谱系
第18章 有关计数的计算
第19章 多项式空间
第20章 未来的展望