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