计算复杂性理论是研究各种计算模型、探究各种计算问题求解有效算法的存在性、比较计算问题求解的困难程度并据其复杂度进行分类研究的理论。本书对这些基础理论知识进行了全面介绍。在此基础上，引入了格的LLL算法、最近平面算法和格的某些困难问题的相关复杂度研究结果，并进一步介绍计算复杂性在密码学中的应用，尝试为读者呈现计算复杂性理论和密码学相融合的知识体系，特别适合于从事密码学尤其是从事基于格的后量子密码研究的读者。本书可作为计算机科学与技术和网络空间安全专业师生的教材，也可作为相关方向科研人员或工程技术人员的参考书。

第1章 绪论
1.1 计算机与可计算理论
1.2 计算问题
习题
第2章 计算问题的算法实例
2.1 图论中问题与算法
2.2 逻辑中问题与算法
2.2.1 Boolean逻辑
2.2.2 一阶逻辑
2.2.3 REACHABILITY与Hamilton通路问题逻辑表达式
2.3 格问题与算法
2.3.1 2维格求解SVP的Gauss算法
2.3.2 LLL算法
2.3.3 最近平面算法
习题
第3章 计算模型
3.1 图灵机基础
……