OpenAI攻破ETH？P=NP或颠覆加密世界

OpenAI又搞大新闻了。这次不是新模型，而是一篇数学证明——据称推翻了计算复杂性理论中的核心假设“指数时间假设”（Exponential Time Hypothesis, ETH）。消息一出，技术圈炸锅：如果为真，意味着P=NP不再遥不可及，现有加密体系可能一夜崩塌。

什么是指数时间假设？

要理解这次冲击，得先搞懂3SAT问题。简单说，3SAT是给出一堆布尔变量组（每组三个），问是否存在一组赋值让所有组同时为真。UP主用一个直观例子演示：初始 A或B或C，随便猜C为真就满足；再加一组 非A或D或E，变量增至五个，猜的次数明显变多；再加第三组，变量到七个，手动验证已相当费劲。

规律很明显：每增加一个变量，验证所需尝试次数呈指数级膨胀。ETH的核心断言正是——3SAT不存在亚指数时间算法，其复杂度下界约为2^n。即便经过算法优化把底数降到1.3，1.3^2500依然是个天文数字，远超宇宙原子总数，现有计算机根本不可能穷举。

NP完全问题是计算复杂性理论中的核心概念，指NP类中最难的一类问题，且任何NP问题都可以在多项式时间内归约到它们。典型的NP完全问题包括3SAT、旅行商问题、背包问题等。它们的关键性质是彼此等价：只要找到其中一个问题的多项式时间算法，就能通过归约解决所有NP问题。因此，证明某个NP完全问题不存在多项式时间算法，就等于证明P≠NP。3SAT作为第一个被证明为NP完全的问题（Cook-Levin定理），常被用作研究复杂性下界的标准载体。

OpenAI的证明动了谁的奶酪？

据该视频分析，OpenAI此次公布的三项发现中，与复杂度理论相关的一项给出了形如 2^n / sqrt(log n) 的算法复杂度上界。这依然是指数级，但已进入“亚指数”区间——恰好与ETH“禁止亚指数算法”的断言相矛盾。

换句话说，如果证明无误，ETH被推翻。UP主将其类比为OpenAI此前在整数乘法上的突破：起初只是微小的下界改进，随后数周内引发一连串优化。他担心ETH的这次“松动”会重演同样剧本，逐步逼近多项式时间。

这里需要厘清一个关键概念：ETH为真则P≠NP；ETH被推翻并不直接推出P=NP，但确实移除了一个重要的理论障碍。用视频里的话说，“这是迈向P=NP的一步”。

亚指数时间指复杂度增长慢于任何指数函数但快于任何多项式函数的算法运行时间，常见形式如2^{n^ε}（ε<1）或2^{n/log n}。指数时间假设（ETH）断言3SAT不存在亚指数时间算法，即其复杂度下界至少为2^{Ω(n)}。如果能在2^{n}/sqrt(log n}时间内解决3SAT，这虽然仍是指数级，但已经打破了ETH的断言，因为该函数属于亚指数范畴。这一区分至关重要：亚指数算法并不等同于多项式算法，但它表明指数下界并非铁板一块，可能为后续优化打开缺口。

如果P=NP，世界会怎样？

P vs NP是计算机科学最大的未解之谜。NP类问题有个古怪特性：验证答案很容易，求解却极难。数独就是典型——检查一个填好的盘面是否合法只需扫一眼，但要从零解出却可能耗费大量时间。

NP完全问题是NP中最难的一类，且彼此可相互转化——旅行商问题可以编码成3SAT。这意味着一旦任何一个NP完全问题被多项式时间算法攻克，所有NP问题都将迎刃而解。

正面看，蛋白质折叠若属NP完全问题，药物研发周期可能从数十年压缩到一年，癌症等疾病治疗或迎来质变。但硬币的另一面更令人不安：RSA公钥加密依赖大整数分解的困难性，SHA-256、HMAC、伪随机数生成器乃至区块链安全，都建立在计算复杂性假设之上。若P=NP成真，这些加密手段将在多项式时间内被攻破，互联网信任根基瞬间瓦解。

RSA加密的安全性基于大整数分解的困难性，即给定两个大素数的乘积，很难在多项式时间内分解出这两个素数。SHA-256是一种密码学哈希函数，其安全性依赖于寻找碰撞或原像的计算困难性。HMAC是基于哈希函数的消息认证码，用于验证消息完整性。这些密码学原语的安全性都建立在某些计算问题不存在多项式时间算法（即P≠NP或相关假设）之上。如果P=NP，则存在多项式时间算法可以破解这些方案，互联网的安全基础设施将面临根本性挑战。

理性看待：别急着恐慌

需要强调，目前这仍是一篇待同行评议的证明，且亚指数算法离多项式时间还有巨大鸿沟。复杂度理论史上不乏“颠覆性证明”最终被证伪的先例。但这次事件传递的信号值得重视：AI正在从工具角色转向数学发现的生产者，其产出速度已让理论界应接不暇。对普通用户而言，短期内不必担心银行卡密码泄露；对密码学从业者，或许是时候加速布局后量子加密了。

同行评议是学术出版中的质量保障机制，由同一领域的独立专家对论文的方法、结果和结论进行审查，以评估其正确性和重要性。对于数学证明，同行评议尤为关键，因为证明可能包含微妙的逻辑漏洞或错误。历史上，许多声称解决重大数学难题的证明在评议过程中被发现有误。因此，在OpenAI的证明通过严格的同行评议之前，其结论应被视为待验证的假设，而非既定事实。