本书是“当代科学前沿论丛”之一，全书共分 个章节，主要对计算机科学中这一重要理论做了全面的介绍，此外，还包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论。书中所有结果均有严格的数学证明，在每章后配有相关练习题。具体内容包括计算复杂性类、多项式时间分层和多项式空间、NP类的结构、概率机与复杂性类、交互证明系统等。该书可供各大专院校作为教材使用，也可供从事相关工作的人员作为参考用书使用。

计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。本书对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论，如计算模型NP-完全性，以及较深入的课题，如线路复杂性、概率复杂性和交互证明系统等。此外，本书还包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论。本书中所有结果均有严格的数学证明，在每章后配有相关练习题。

本书可用作计算机专业、计算数学专业的计算机理论课程的教材，也是有关研究人员不可或缺的参考书。

前言

第一章 计算模型

 1.1 符号行，编码和布尔函数

 1.2 确定型图灵机

 1.3 非确定型图灵机

 练习题

第二章 计算复杂性类

 2.1 时间与空间

 2.2 通用图灵机

 2.3 对角线方法

 2.4 模拟

 练习题

第三章 NP-完全问题

 3.1 NP

 3.2 Cook定理

 3.3 NP-完全问题的例子

 3.4 多项式时间图灵归约

 练习题

第四章 多项式时间分层和多项式空间

 4.1 非确定型带神喻图灵机

 4.2 多项式时间分层

 4.3 PH中的完全问题

 4.4 交替图灵机

 4.5 PSPACE-完全问题

 练习题

第五章 线路复杂性

 5.1 布尔线路

 5.2 单调递增函数与单调线路

 5.3 奇偶性函数与深度有界线路

 5.4 多项式规模布尔线路

 练习题

第六章 NP类的结构

 6.1 NP中的非完全问题

 6.2 单向函数及其在密码学中的应用

 6.3 NC

 6.4 P-完全性

 6.5 NP-完全问题的密度

 6.6 EXP-完全问题的密度

 练习题

第七章 概率机与复杂性类

 7.1 随机算法

 7.2 概率图灵机及其时间复杂性

 7.3 带有界误差的概率机

 7.4 BPP，NP和多项式时间分层

 练习题

第八章 计数复杂性

 8.1 计数类#P

 8.2 #P-完全问题

 8.3 ■P和多项式时间分层

 8.4 #P和多项式时间分层

 练习题

第九章 交互证明系统

 9.1 例子与定义

 9.2 亚瑟默林证明系统

 9.3 AM分层与多项式时间分层

 9.4 IP与AM

 9.5 IP与PSPACE

 练习题

第十章 概率可验证明

 10.1 PCP的定义

 10.2 NEXPPOLY的PCP特征

 10.2.1 主要证明

 10.2.2 多重线性测试系统

 10.2.3 和检验系统

 10.3 NP的PCP特征

 10.3.1 使用O(logn)个随机数码的PCP系统

 10.3.2 低阶测试系统

 10.3.3 两个PCP系统的复合

 10.3.4 阅读常数多神喻数码的PCP系统

 练习题

第十一章 近似解的复杂性

 11.1 胆完全优化问题

 11.2 PCP和不可近似性

 11.3 优化问题的归约

 11.4 难近似的优化问题

 练习题

第十二章 平均NP-完全性理论

 12.1 平均易解性

 12.2 多项式时间归约

 12.3 p-分布

 12.4 平均NP-完全问题

 12.5 扁平分布与随机归约

 12.6 扁平分布下的完全问题

 12.7 可抽样分布

 练习题

参考文献

名词索引(汉英对照)