P vs NP · 计算复杂性根基

P vs NP问题问的是：凡是能快速验证答案对错的问题，是否也能快速求解？这是理论计算机科学的核心问题，直接决定密码学安全性根基、优化算法的理论上限、以及'创造答案'与'识别答案'之间是否存在本质鸿沟。克莱数学研究所2000年将其列为七个千禧年大奖难题之一，悬赏100万美元；除庞加莱猜想已被佩雷尔曼攻克外，其余六题(含P vs NP)截至2026年仍全部悬空。攻破意味着要么证明存在通用高效算法解决所有NP问题（现有密码学体系随之崩塌），要么证明这种算法不可能存在（为计算复杂性划定永久边界）。

难在这是一个「证明不存在」的问题——要排除所有可能的聪明算法。更狠的是，领域已经严格证明了三大类已知技术天花板：相对化（1975）、自然证明（1994）、代数化（2008）都够不着答案，等于给「已知路线全部封死」出具了数学证明。当前卡在缺少一种能绕开这三重障碍的全新数学工具，而没人知道它长什么样。

Mulmuley 的几何复杂性理论（GCT）纲领——用代数几何与表示论绕开障碍，是唯一自带长期路线图的进攻方案（进展极慢）；计算复杂性理论社区在电路下界、元复杂性（meta-complexity）等方向持续推进，Simons 理论计算研究所（伯克利）多次组织专题项目。

读计算复杂性理论（Arora–Barak 教材是标准地图），研究生进理论计算机科学强组。切入点选可积累的子问题：受限电路模型的下界、证明复杂性、元复杂性（「判断问题难不难」本身有多难）——这些是当前最活跃、且被认为可能通向主问题的前沿；有代数天赋者可入 GCT 方向。