计算复杂性理论是用数学方法研究计算机解决各种算法问题难易程度的理论。本书对这一理论的基础知识做了全面介绍, 力争帮助读者掌握该理论的思想方法, 为进一步开展计算机科学的相关领域的学习和研究奠定了基础。本书首先介绍计算复杂性理论的概述、一些计算问题和逻辑, 然后详细介绍计算模型、P vsNP问题、归约和NP完备性理论等; 接着针对信息安全专业特点, 详细介绍随机化算法、(非) 一致电路; 最后简单介绍几个较深入的课题: 交互语言类、计数复杂类、概率可验证语言类等。