包邮计算复杂性导论

内容简介

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

节选

作者简介

堵丁柱(1948～)，中国科学院应用数学所研究员，美国明尼苏达大学计算机科学系教授等，著有《计算复杂性导论》。