本书深入浅出地介绍了研究可计算性的四个主要模型以及四个模型彼此之间的关系:介绍了计算复杂性的基本概念和重要的研究方法与一些研究成果。内容涉及递归函数、图灵机、λ演算、马尔可夫算法、计算复杂度的分类、NP完全理论、非一致复杂性等。分述于十章,书中附有习题。
本书可作为广大有志于突破计算复杂性研究僵局——“P=NP?”的科技工作者,计算机科学和元计算机科学工作者,数学和元数学工作者以及大专院校的教师和学生的入门书、教材和参考书,亦可作为计算机基础理论的参考书。

**章 概论
**节 相关定义
第二节 可计算性
第三节 计算复杂性
第四节 对可计算性定义的质疑
练习题
第二章 一般递归函数
**节 初始函数
第二节 合成法生成新函数
第三节 算子法构造函数
练习题
第三章 图灵机
**节 图灵机的基本模型
第二节 图灵机基本模型的功能
第三节 图灵机基本模型的修改
第四节 图灵机和判定问题
第五节 图灵机和递归函数
练习题
第四章 r演算
**节 r演算的语法
第二节 三个重要的组合算子
第三节 r演算系统的扩充
第四节 组约
第五节 其他重要的组合算子
第六节 r可定义的函数和归函数
练习题
第五章 马尔可夫算法
**节 演算和算法
第二节 马尔可夫算法
第三节 图灵可计算的函数
第四节 图灵机和巴尔可夫算法
第五节 马尔可夫算法和递归函数
练习题 马尔可夫算法和递归函数
第六章 计算复杂性
**节 函数的计算杂性
第二节 图灵机的计算复杂性
第三节 可构造的函数
练习题
第七章 计算复杂性的分类
**节 时间复杂类和空间复杂类
第二节 三个NP问题
练习题
第八章 NP完全理论
**节 多项式可计算的函数
第二节 多项式时间的多一化归和NP完全集
第三节 多项式同构和P≠NP
第四节 稀疏的NP完全集和N=NP
第五节 多项式时间图灵化归和NP=co-NP
练习题
第九章 非一致复杂性
**节 布尔代数和布尔线路
第二节 布尔线路和图灵机
第三节 多项式超前函数
第四节 布尔单行函数
练习题
第十章 谓词的可计算性
**节 一阶语言L的语法和语义
第二节 一阶谓词演算系统K
第三节 数论谓词的判定性
第四节 摹状词和摹状算子
参考文献