计算机科学不仅是代码，更是底层逻辑的探索。P vs NP、深度学习泛化理论、量子纠错的工程化门槛，这三大未解难题分别代表了计算理论、机器学习与物理实现的终极困惑，直接决定了现代技术的边界与未来。
智能速览
学术界普遍相信 P ≠ NP，但受限于三道证明屏障无法证实。
Google Willow 芯片验证了量子纠错阈值定理，迈出关键一步。
单向函数的存在性仍无法证明，却是密码学安全的绝对基石。
电路下界与去随机化研究近期取得突破，为解决大问题提供新思路。
深度学习缺乏坚实的泛化理论，良性过拟合现象引发学界关注。
精华内容
计算机科学的终极挑战并非单纯的工程实现，而是对计算本质的追问，从算法极限到智能原理，这些理论难题构成了数字时代的地基。
P vs NP 的绝望鸿沟
P vs NP 问题问的是，那些容易被验证答案的问题，是否也容易被求解。尽管 80% 的研究者相信 P 不等于 NP，但证明它难如登天。
学术界发现了三道难以逾越的证明屏障：相对化、自然证明和代数化，这意味着现有的数学工具几乎全部失效。如果 P = NP，世界将天翻地覆：密码学全面崩溃，蛋白质折叠自动求解，数学定理证明机器化。但这种可能性微乎其微，因为这意味着数千个看起来完全不同的困难问题，其背后共享同一个计算困难的核心。
量子纠错的里程碑
量子计算正从理论走向工程现实。Google 的 Willow 芯片首次展示了低于阈值的量子纠错，逻辑量子比特的寿命超过了物理量子比特，验证了长达 30 年的阈值定理。
这表明，通过增加物理量子比特数量，可以指数级降低错误率。结合量子 LDPC 码的突破，构建容错量子计算机的路径变得清晰，尽管距离通用的容错量子计算仍有距离，但地基已经打好。
密码学的隐秘基石
单向函数的存在性是那“半个”未解问题，也是现代密码学的命门。如果单向函数不存在，所有加密代码都将失去根基。虽然 P ≠ NP 是单向函数存在的必要条件，但并不充分。
近期研究将单向函数与时间有界 Kolmogorov 复杂度的平均困难性联系起来，为证明其存在提供了新视角。现实中，NIST 发布的后量子密码标准基于格问题，目前仍被认为是安全的，尽管偶尔出现的攻击算法尝试曾引发短暂恐慌。
AI 的理论缺失
深度学习在实践中大获成功，但在理论上却充满谜团。经典理论认为参数远超样本数的模型会过拟合，但现实中它们泛化良好。
这种“良性过拟合”和“Grokking”现象表明，模型能先死记硬背再突然学会泛化。目前的理论解释多局限于线性模型，对于像 Transformer 这样的大规模非线性架构，我们仍缺乏一个能完美解释其为何有效的数学框架。
这些未解难题之所以迷人，在于它们连接着看似不相关的数学对象。2023 到 2025 年的进展表明，正面强攻往往无效，创造性的迂回才是关键。随着 AI 开始介入数学证明的辅助，人机协作或许能成为攻克这些终极谜题的新契机。
