本书是一本介绍计算复杂性理论的基础教材, 内容包括时间复杂性、空间复杂性、NP-理论、多项式谱 系、电路复杂性、随机计算及去随机、计数复杂性、交互证明系统、PCP 定理、近似计算与不可近似性。 本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解（更多）计算复杂性理论的教师 和科研工作者。本书可用于以下课程：（1）面向高年级本科生、研究生的“计算复杂性理论导论”课程， 内容涵盖前3 章；（2）面向研究生的“计算复杂性理论高等议题”课程，内容涵盖后3 章；（3）面向高年 级本科生、研究生的“算法理论”课程，涵盖第 4 章、第 6 章中有关随机算法和去随机、近似算法和不 可近似性的内容；（4）面向高年级本科生、研究生的“计算理论”课程，以第 1 章的内容为核心，并根 据学分多少和授课对象不同做适当补充。

傅育熙 单位：上海交通大学 职务、职称：教授 性别：男 年龄：59。傅育熙，1992年获英国曼彻斯特大学计算机博士学位，1994年起在上海交通大学计算机系任职，现为上海交通大学特聘教授。研究领域为理论计算机科学，研究内容涉及程序理论、并发理论、等价性验证、可达性理论、交互理论。是国家杰出青年基金获得者、上海市优秀学科带头人。2000-2009年任上海交通大学计算机系主任，2001-2013年任上海交通大学软件学院院长。学术兼职有：上海高校软件理论研究中心主任、国务院学位委员会第六届学科评议组成员（2010-2014）、上海市计算机学会理事长（2015-2018）、教育部计算机类专业教学指导委员会副主任（2013-2017，2018-2022）。是Mathematical Structures in Computer Science的编委。

前 言 当学生时没学懂的地方，教这门课时学懂了；看书时忽略的细节，备课时注意到了；备课时自信能讲好一个定理的证明，上课时挂板了；上课时高调阐述一个得意的观点，回答学生提问时心虚了。十年后，当准备为这门课写自己的教材时，终于知道，关于这门课，知道得太少了。为写教材，花了一年多时间查阅文献，才发现，有个别地方，过去十年一直在误导学生。 解惑之道，是一条往返于细节与真理之间的路。这条路，教师多走几遍，学生就多获益几许。要做到在讲堂上从心所欲，教师须经历读书、教书、写书的全过程。编写本书，有几层考虑。其一，我非常想进一步提高“计算复杂性理论”这门课的课堂教学水平。2020 年秋季学期，当第十几次给高年级本科生和研究生讲授这门课时，我已没了以往的激情，这不是个好兆头。为求改变，我边讲课，边把课上所讲内容写下来。2021 年春季学期，我讲授“计算复杂性理论高等议题”这门课。我对这部分内容远不如我对秋季学期讲的那部分内容熟悉，我还是认真做了讲课笔记。之后的一年，我对这些笔记改头换面，补充了所有课上没讲的证明，增加了不少这门课以前没有涉及的内容，在结构上做了变动，直至最后，对这本书的定位也做了些许调整。在本书完稿之前，我已确信我能把这门课讲授得更好。考虑之二，中国的计算机专业教育急需一本系统介绍计算复杂性理论的中文教材。中国的计算机专业教育是全球最大的专业教育，如果它的学生还要为教材发愁，如果它的学生使用的大多数教材都是国外学者撰写的，我们有什么理由说我们的计算机专业教育是好的。出版社的编辑告诉我，百分之九十五以上的中国学生更愿意使用中文教材。我认为他们有绝对的权利要求好的中文教...