计算复杂性理论导引

本书介绍了计算复杂性理论的一些基础知识，如计算模型Turing机、复杂性的度量与本质关系、P等不等于NP问题、空间复杂性等，还选择了一些适合密码学及信息安全专业学习的高级专题，如随机化算法、电路复杂性、交互式证明等进行了介绍。本书的编写尽量少使用计算机专业术语，涉及的计算问题相对集中，避免学生因相关数学知识储备不够而造成困惑。对较难的定理证明，给出直观分析以增进学生的理解和消化。设置了合适数量和难度的习题，习题中的知识点也非常重要，通过给出适当提示，引导学生完成。本书可作为密码学、信息安全及相关专业的“计算复杂性理论”课程的教材。