简介
本书是一本介绍计算复杂性理论的基础教材, 内容包括时间复杂性、空间复杂性、NP-理论、多项式谱 系、电路复杂性、随机计算及去随机、计数复杂性、交互证明系统、PCP 定理、近似计算与不可近似性。 本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解（更多）计算复杂性理论的教师 和科研工作者。本书可用于以下课程：（1）面向高年级本科生、研究生的“计算复杂性理论导论”课程， 内容涵盖前3 章；（2）面向研究生的“计算复杂性理论高等议题”课程，内容涵盖后3 章；（3）面向高年 级本科生、研究生的“算法理论”课程，涵盖第 4 章、第 6 章中有关随机算法和去随机、近似算法和不 可近似性的内容；（4）面向高年级本科生、研究生的“计算理论”课程，以第 1 章的内容为核心，并根 据学分多少和授课对象不同做适当补充。
编辑推荐
本教材可作为以下课程的主参考书：（1）面向高年级本科生、研究生的“计算复杂性理论导论”课程；（2）面向研究生的“计算复杂性理论高等议题”课章；（3）面向高年级本科生、研究生的“高等算法”课程；（4）面向高年级本科生、研究生的“计算理论”课程。
更多出版物信息
- 版权： 清华大学出版社
- 出版： 2023-05-01
- 更新： 2023-11-24
- 书号：9787302627982
- 中图：TP301.5-43
- 学科：工学控制科学与工程工学计算机科学与技术
