Lance Fortnow 写计算复杂性博客已经二十多年,向来不是一惊一乍的人。他针对这一新说法写的文章,结尾却措辞谨慎:"我还没有亲自验证这个证明,但现在可以放心地认为,指数时间假设已经完蛋了"(Computational Complexity)。
这一说法来自两家实验室。ChatGPT 背后的公司 OpenAI 表示,其模型推翻了指数时间假设(Exponential Time Hypothesis,通常简称 ETH)。几小时后,Claude 的开发商 Anthropic 也发布了自己的推翻证明(这两款助手的对比见这里)。随后,各路头条把这条新闻与数学家之间的争吵以及对全球加密的担忧联系在了一起。我们读了两家实验室自己的文章、专家评论和新闻报道,看法很明确:这个结果很可能是真的,对理论研究者意义重大,但你不需要因此改变保护数据的方式。三条头条里,有两条说的是别的争议,第三条说的是一种趋势。
指数时间假设到底是什么?
先从一个叫 3-SAT 的难题说起。你拿到一长串条件,涉及 n 个真/假开关,每个条件的形式都像"A,或非 B,或 C",你要找出一种开关设置,让所有条件同时成立。验证一个给定的设置很快,找出它才是难点,就像数独:填满的格子很容易检验,空白的却不然。
ETH 由 Russell Impagliazzo 和 Ramamohan Paturi 在 1999 年提出(Francis Zane 也参与其中),它认为任何 3-SAT 算法所需的时间都至少按 2 的 c×n 次方增长,其中 c 是某个大于零的固定常数(Fortnow)。可以想象一把密码锁,每多一个转盘,工作量就乘上一个固定倍数,比如 1.3。ETH 的意思是,这个倍数可以压低,但永远压不到 1。
这次的推翻结论则说,随着公式变大,这个倍数会不断逼近 1。据 Fortnow 介绍,OpenAI 的论文给出的运行时间大约是 2 的 n·log log n/√(log n) 次方。这仍然谈不上快,只是增长得比任何固定倍数都慢。Anthropic 自己的文章也毫不含糊:"这个结果纯属渐近意义上的,并不能说明实际中求解公式会怎样"(Anthropic)。
理论研究者为什么这么在意?因为 ETH 已被数百篇论文当作"这个问题不可能快很多"的依据(OpenAI)。如果这个假设不成立,那些难度论证就得重新检查,不过 Fortnow 指出,"ETH 和 SETH 不成立,并不意味着它们的推论就是错的。"
已验证的比平常多,但离定论还差得远
目前的检验力度,已经超过大多数突破在头一周所得到的。OpenAI 称,其模型在公布前十天就找到了这个反证,并且已用 Lean 形式化,Lean 是一种只接受自己能验证的步骤的证明检查器(OpenAI)。Anthropic 称,它的版本由内部的一个 Claude 模型找到,Lean 文件则由 AI 模型编写(Anthropic)。
此后人类专家也加入了进来。卡内基梅隆大学的 Ryan O'Donnell 发布了重写后的证明阐述,Fortnow 说 Shiva Kintali 也发布了一份,两者都追求简洁而非最优界。Timothy Gowers 评价说:"它居然是错的,这非常出人意料,影响也非常深远"(Business Insider)。
被正式指定负责检查的是 Impagliazzo、Paturi 和 MIT 的 Ryan Williams。Williams 对 TechCrunch 表示,证明中有些部分是常规套路,但"有两三处看起来很陌生"。Business Insider 报道称,Williams 并未认证这一结果,该小组也表示,他们的参与不等于背书。Anthropic 自己的代码库还有一点提醒:Lean 检查的是证明,但"没有任何机器会检查这个文件说的是否与论文一致",所以得有人去读那份简短的陈述文件。他们正是为此才把它写得很短。
我们的看法:两家实验室提出主张,机器检查过的证明加上人工重写在几天内就位,这已经相当有分量。但在专家小组和期刊给出结论之前,它仍然只是一个主张。
数学家之间的争吵是因为这个结果吗?
基本不是。BBC 所说的"数学家之间的决裂"针对的是另一个问题。那篇报道讲的是 Navier-Stokes 方程之争:纽约大学的 Tristan Buckmaster 质疑,他存放在 OpenAI Codex 工具里的草稿,是否可能被用到了 OpenAI 自己的工作中。OpenAI 表示那里没有人看过对方团队的工作,他的 prompt"不可能以任何方式影响该系统"。
Scientific American 那个"抢先"的标题说的是杨-米尔斯(Yang-Mills)问题,这是个物理问题。该杂志称,OpenAI 似乎抢在了 Ethan Sussman 与 Anthropic 的 Levent Alpöge 合作之前给出了证明。Alpöge 在 X 上提出了异议。这些都与 3-SAT 算法是否成立无关。
ETH 的争议在于过程。Williams 曾把 OpenAI 早先的一次发布称为"对数学家的 DDOS 攻击"(X),后来却同意协助这一次。Scientific American 称,OpenAI 对三项成果中两项的处理方式,违反了其自家 AI 与数学专家顾问小组发表的一份澄清声明,而相关的 prompt 和思维链至今未公开。至于 ETH,OpenAI 确实同意公布证明并资助一场会议。
它会破解 RSA 或我手机上的加密吗?
不会,至少这条路走不通。我们敢说得这么干脆,是因为理由很具体。第一,这个算法解决的是 k-SAT。Fortnow 强调它"对子集和问题(Subset Sum)或旅行商问题没有任何新的帮助",因为把它们转化成 3-SAT 会让变量数膨胀得太厉害。第二,RSA 依赖的是把一个巨大的数分解成两个素数的难度(Financial Times 描述了这种方法,但没有点名),这与满足逻辑公式是不同的问题,我们读过的资料也没有一份说新算法能触及它。第三,这个界是渐近意义上的:对任何现存的机器来说,2,048 位密钥的安全性都没有变化。
Williams 向 OpenAI 的科学负责人 Dan Roberts 问到了这个显而易见的担忧。据 TechCrunch 报道,他问现在是否有什么东西不安全了,并转述说,OpenAI 似乎已经检查过,"相当有把握"这并不意味着有什么东西被攻破。这是二手信息,也没有公开发布,请相应看待。Williams 还说,如果算法得到改进,可能意味着某些密钥长度会被视为已被攻破。
这背后确实还有一个悬而未决的问题。Williams 说"每位计算机科学家或许都应该稍微提高一点对 P = NP 可能性的看重",但 John D. Cook 指出,"P = NP 的状态仍然未知"(Business Insider)。Williams 也不认为这个新算法已经是最优的。如果出现更强的算法,情况就会不同。
Financial Times 那篇文章谈的是趋势,不是这个证明
FT 那篇文章谈的是 AI 日益增强的数学能力和一般意义上的加密,而且在我们能读到的正文里,一次也没提到 ETH。文中引用的说法都相当克制。澳大利亚数学家 Geordie Williamson 在帝国理工学院的一次演讲中说,AI 正在造成"对难度这个概念的彻底重构",我们应当预料到冲击。曼彻斯特大学的 Daniel Shiu 称,AI 破解加密对"偏数学的密码形式"是"重大风险",并点名了一些"不太成熟"的抗量子算法。FT 自己也说,AI"还没有破解任何一种核心密码方法"。
Scott Aaronson 补充了一条线索:在 OpenAI 早先列出的 376 篇论文里,密码学明显缺席。他在自己那篇文章的更新中写道,据他的消息来源,AI 公司已开始调查自家模型能否攻破协议。他没有给出名字,我们也给不出。
我们的看法:值得担心的是较新的方案,而不是你浏览器里用的那些。NIST 2024 年的标准包含两个基于格的方案,以及第三个基于另一类数学的签名标准,它作为备份保留,以防前者被证明存在漏洞。
小企业到底该怎么做
基本什么都不用做,也不用着急。下面的决策树把我们认为重要的三种情形分了类。
有一个习惯,无论这件事如何都值得养成。英国监管机构对 FT 表示,针对 AI 和量子对密码学构成的风险,"企业不应等待再行动";BT 则表示,希望自己的密码系统能"随着标准、技术和威胁的演变更容易地更换"。对小商家来说,这意味着保持软件更新,并问问供应商换算法时打算怎么做。我们的信任 AI 工具处理你数据的框架列出了该问供应商的问题,ToolRank 的安全与隐私榜单则按类别列出了相关工具。
在有人说"已成定论"之前,要关注的三件事
请关注三件事。一是 Impagliazzo、Paturi 和 Williams 组成的专家小组的报告,以及 OpenAI 同意资助的那场会议。二是对 Lean 陈述文件的独立审读,因为细微的错误最可能藏在那里。三是期刊同行评议,目前我们没有发现任何迹象。在第一项出现之前,我们的说法是"很可能已被推翻"。