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