第十卷 · 计算理论

计算理论回答两个问题：什么能算（可计算性），以及能算的东西要多少资源（复杂度）。本卷是第一卷计算模型与第四卷 NP 完全性的严格版本。

本卷结构

• 第一部分 · 自动机与可计算性：有限自动机与正则语言、上下文无关文法与下推自动机、图灵机、可计算性与停机问题。
• 第二部分 · 复杂度：P、NP 与归约、复杂度类全景。

前置

第一卷第二部分；离散数学。