知识/定理
计算复杂性理论（1970s–80s）：按所需资源分类问题——P、NP、随机化、近似、并行等复杂度类体系。
公式
复杂度类 P⊆NP、BPP、#P；归约与完备性：$\text{SAT}\in\text{NP}\text{-c}$。
证明思路
（归约/类论）以「资源上界」定义类，用归约建立类的内部结构。
应用/例子
算法设计、密码学安全假设、近似算法、机器学习理论。
意义/影响
把「可算」细化到「算得多快」——计算机科学的核心学科。
DOXA · 数学编年史 · 知识详情
1980s ｜ 理论计算机界 ｜ 离散·组合 ｜ 概念
计算复杂性理论（1970s–80s）：按所需资源分类问题——P、NP、随机化、近似、并行等复杂度类体系。
复杂度类 P⊆NP、BPP、#P；归约与完备性：$\text{SAT}\in\text{NP}\text{-c}$。
（归约/类论）以「资源上界」定义类，用归约建立类的内部结构。
算法设计、密码学安全假设、近似算法、机器学习理论。
把「可算」细化到「算得多快」——计算机科学的核心学科。