OpenAI 与 Anthropic 称 AI 模型推翻指数时间假说（ETH），学界如何解读
Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
OpenAI 与 Anthropic 分别发布由 AI 模型给出的证明，并声称这些结果推翻了指数时间假说（ETH），相关主张正引发学界讨论。OpenAI 针对数学、计算机科学和物理学采取不同流程，数学证明先发布到 GitHub，计算机科学界成立工作组并要求公开证明，物理学界的发布方式仍待工作组决定。
文章梳理AI若有效推翻ETH后，可能对依赖该假说的既有论文、密码系统安全、AI证明审查方式及学界公开协作规范产生的具体影响。
OpenAI 昨天公布了针对三个重磅数学难题的解法，这些难题长期困扰着研究人员。其中一项出人意料的成果否定了指数时间假设（ETH）——这是计算机科学中一项长期存在的假设，对我们理解哪些问题难以计算发挥着重要作用。
与这家前沿实验室此前发布证明时一样，科学界的反应不一，有人兴奋，有人失望。Anthropic 数学家 Levent Alpöge 认为，OpenAI 的这些解法是基于既有工作得出的。数小时后，Anthropic 也发布了自己对 ETH 的反驳。
不过，OpenAI 的发布流程正在演变。这一次，该实验室针对涉及的三个学科领域，以不同方式安排成果发布：数学家们看到研究成果被直接放到 GitHub 上；计算机科学家组成工作组，要求公开分享这些证明，并要求 OpenAI 资助一场讨论这些证明的会议；物理学家则组成工作组，将决定其研究结果的发布方式。
麻省理工学院教授 Ryan Williams 正在组织计算机科学界对这项新发现的回应。Williams 的研究聚焦于这些计算复杂性问题。过去，他曾批评 OpenAI 的做法，称其今年 10 月初一次性倾倒证明是“对数学家的 DDOS 攻击”。
不过，他告诉 TechCrunch，他同意与前沿实验室合作，以帮助引导对本领域至关重要的想法。该实验室请他与 UC San Diego 的计算机科学家 Russell Impagliazzo 和 Ramamohan Paturi 一同帮助解读这一解答，后二人于 1999 年首次发表了 ETH。
他们的第一步是发布一封公开信，呼吁对这些问题感兴趣的科学家提供反馈，并讨论 AI 参与其工作时应遵循的规范。
“某些部分 [OpenAI 的证明] 或许可以说是常规的，但确实也有两三部分看起来像是外星人写的。而正是我看到的这些部分让我觉得，哇，这是整个学界需要共同研究的东西，”Williams 告诉 TechCrunch。
你支持 P vs NP 吗？
ETH 属于一类更广泛的问题，这类问题统称为 P vs NP，几十年来一直激发着计算机科学及其他许多领域的兴趣。简而言之，研究人员试图弄清，任何解法可以轻松验证（NP）的问题，其解法是否也能轻松求得（P）。
一个简单的例子是数独游戏：一旦有了谜题的答案，就可以迅速验证，但找到答案却非常耗时。这种情况在一系列重要问题中都成立，而这一洞见也构成了密码系统的基础：当你拥有编码消息的密钥时，可以将其还原，但真正破解一个有效的加密体系所需的时间太久，难以派上用场。
不过，科学家尚未证明这种情况是否始终成立。“P = NP 所表达的是，不仅当数独答案存在时你可以验证它们，还可以直接生成它们，”Williams 说。“P = NP 断言，这对每一个能够快速验证的问题都成立——如果能快速验证，就能快速求解。所以这简直好得让人难以置信。”
正因如此，大多数科学家都假定 P ≠ NP。ETH 为此提供了证据。其基本含义是，在某一类棘手逻辑谜题中，随着变量数量增加，即使是最快的计算机算法，找到一个解也需要指数级更多的时间。
OpenAI 和 Anthropic 声称，它们的模型提出了能够在“亚指数”时间内解决这些谜题的算法，这意味着其速度超过了人们此前认为可能达到的速度。如果属实，他们或许已经证明 EFT 为假——用科学术语来说，就是推翻了它——并可能为普遍实现 P = NP 的算法开辟一条道路。
“每位计算机科学家或许都应当更看重 P = NP 的可能性，不过每个人看重的程度可能不同，”Williams 说。“我的确认为，这多少让我们对自己曾经对……[困难 NP 问题]的可解性所抱有的许多直觉产生了质疑。我还认为，这大概也不会是最终答案。我不认为 OpenAI 的算法有可能就是所能获得的最佳算法。”
计算机科学家接下来的工作
Williams 说，过去十年中，ETH 因其长期有效而被纳入许多科学论文；如果 AI 实验室关于已证明 ETH 错误的主张经得起检验，这些论文就需要重新审视。
“这也是为什么我请求或推动 OpenAI 支持举办一场关于此事的会议——这将影响许多研究者的成果。我们需要弄清楚，好吧，除了理解这些算法之外，接下来会发生什么；我们还需要理解，我们此前所依据的基础今后应该是什么？”他说。
在科学层面的担忧之前，还有网络安全方面的问题。Williams 说，一种改进后的算法可能意味着，依赖特定密钥长度的加密系统会被视为已被攻破。因此，他问 OpenAI 科学负责人 Dan Roberts 的首批问题之一就是：“他们是否检查过这会不会影响任何加密系统……现在是否有什么东西不安全了？显然，他们进行了检查，并有合理把握认为这不会……意味着出现任何破解。”
这种以 AI 驱动科学发现的新范式仍处于发展之中，但 Williams 表示，尽管存在切实的担忧，他仍持乐观态度，尤其是对培养下一代科学家方面的担忧。作为一名从事高等数学的计算机科学家，他适应这种变化或许比纯数学家更容易。
不过，他表示，AI 正“迫使人们对自己的工作类型稍微提出更高要求，并更深入地思考：好吧，如果我以前研究的所有东西现在对 AI 来说都是唾手可得的，那么我怎样才能提高我想提出的那类科学问题的门槛？”
通过我们文章中的链接购买时，我们可能会获得少量佣金。这不会影响我们的编辑独立性。
来源：TechCrunch · techcrunch.com