时间复杂度基础
从多带图灵机、时间函数与通用图灵机出发，梳理停机问题、线性加速、确定性与非确定性时间复杂度类、SAT、时间层次定理和多项式时间归约。
阅读笔记武汉大学计算机学院课程笔记
计算理论导引
本系列以计算复杂性理论为专题，按照“复杂度基础—证明工具—NP 完全性归约”的顺序组织为 3 章。本站版本保留原有手写页、证明整理稿与公式图片，并统一章节导航和内容层级。
经典定理与证明工具
集中整理停机问题不可判定性、线性加速与时间层次定理，并进一步介绍可达性的 NL 完全性、对数空间归约的传递性和 NP 的验证器定义。
阅读笔记NP 完全性问题的归约证明
以 3-SAT 为起点，按“属于 NP”和“构造多项式时间归约”两步，整理 0-1 线性规划、Set Packing、Exact Cover、3-Dimensional Matching、Feedback Node Set 与 Clique 的证明。
阅读笔记