计算复杂度理论
概述
计算复杂度理论是计算机科学的核心分支，研究算法解决问题所需的资源（时间、空间），以及问题之间的内在难度关系。Cook 1971年的 NP 完全性论文建立了该领域的核心框架。
关键内容
历史发展
- 1965年：Hartmanis 和 Stearns 发表《On the computational complexity of algorithms》，正式建立时间复杂度框架
- 1965年：Cobham 和 Edmonds 提出"多项式时间 = 可行计算"的标准
- 1971年：Cook 定义 NP 完全性，证明 SAT 是 NP 完全的
- 1972年：Karp 证明21个经典问题的 NP 完全性
- 1973年：Levin 独立发现相同结果
核心复杂度类
| 类 | 定义 |
|---|---|
| P | 确定性图灵机多项式时间可解 |
| NP | 非确定性图灵机多项式时间可解 |
| co-NP | NP 的互补类 |
| PSPACE | 多项式空间可解 |
| EXP | 指数时间可解 |
| BPP | 有界误差概率多项式时间 |
| BQP | 量子多项式时间 |
核心问题
- P vs NP：千禧年数学问题，悬赏100万美元
- NP vs co-NP：同样未解
- P vs PSPACE：未解
研究方向
- 近似算法理论
- 参数化复杂度
- 随机化复杂度
- 通信复杂度和电路复杂度
- 平均情况复杂度
跨领域影响
来源
- raw/books/计算机科学/08-cook-np-completeness.md
- 01-turing-on-computable-numbers — 图灵机理论基础
相关
- NP 完全性 — 核心概念
- Cook NP 完全性论文 — 奠基文献
- Stephen Cook — 奠基者
- P vs NP — 最重要的未解问题
- 图灵机 — 定义基础
- λ 演算 — 计算理论的另一核心分支
- 论可计算数及其在判定问题上的应用 — 理论基础
- 阿兰·麦席森·图灵 — 奠基人
- 可计算性理论 — 前身理论