计算复杂性导论 pdf是一本可用作计算机专业、计算数学专业的计算机理论课程的教材，作者为读者全方位的讲解了计算机科学，感兴趣的朋友欢迎下载学习！
《计算复杂性导论》是2002年高等教育出版社出版的图书，作者是堵丁柱、葛可一、王杰。本书对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论，如计算模型NP-完全性，以及较深入的课题，如线路复杂性、概率复杂性和交互证明系统等。
1.计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论
2.包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论
3.所有结果均有严格的数学证明，在每章后配有相关练习题
计算复杂性导论目录1，计算模型
2，计算复杂性类
3，NP-完全问题
4，多项式时间分层和多项式空间
5，线路复杂性
6，NP类的结构
7，概率机与复杂性类
8，计数复杂性
9，交互证明系统
10，概率可验证明
11，近似解的复杂性
12，平均NP-完全性理论