图片来源：ISTOCK IMAGES

本报讯 10月26日，美国人工智能（AI）公司OpenAI称，其AI模型推翻了指数时间假设（ETH）—— 一个支撑了计算机科学近30年的基本假设。

ETH于1999年由美国加州大学圣地亚哥分校的Russell Impagliazzo和Ramamohan Paturi提出。ETH涉及理论计算机科学的一个经典难题——可满足性问题。假设有一组开关和一张规则列表，每条规则指定了3个开关及其各自的位置，只要其中至少一个开关处于该位置，规则就得到满足。那么，是否存在一种设置开关的方法，使每条规则都得到满足？这个难题听起来很抽象，但具有现实意义，因为从芯片设计到调度问题，再到密码学的许多实际问题，都可以转化为这种形式。

这是个极其复杂的问题，因为每个开关可以开或关，每增加一个开关，可能的组合数量就会翻倍，即组合数量呈指数级增长。10个开关可以给出约1000种组合，而到几百个开关时，组合数量已经超过了可观测宇宙中的原子数量。因此，寻找满足所有规则的组合或证明不存在解决方案，就成了一项艰巨任务。尽管巧妙的捷径无需逐一验证每一种组合，但仍没有任何方法能避免时间和精力呈指数级增长的趋势。ETH就主张永远不会有这样的捷径。

然而，OpenAI使用检查数学证明的编程语言Lean验证了ETH的结果并提出反驳，表明存在能够更高效地找到满足所有规则的解决方案。推翻ETH是朝着解决著名P与NP问题迈出的重要一步。该问题是美国克雷数学研究所公布的千禧年大奖难题之一。

这次，OpenAI没有把ETH的研究成果直接发布在网上，而是请美国麻省理工学院的计算机科学家Ryan Williams作为外部专家，主导该成果的理解、验证与对外发布工作。Williams说，他招募了ETH的提出者Impagliazzo和Paturi组团完成这项工作。OpenAI没有要求他们签署保密协议，也没有为这项工作提供报酬。Impagliazzo说，OpenAI发来的第一版研究成果“完全无法阅读”，因此团队在公开发布所有内容前，制作了一份更易理解的版本。

据悉，OpenAI的ETH团队计划成立一个工作组，制作一份完全可读的证明，随后在年底前举行一次虚拟评审会议，并在2027年举行一次线下会议。

无论结果如何，近期OpenAI等AI公司抛出了一系列数学成果、解决了数百道数学问题，速度之快让一些学者在震惊的同时也感到担忧。“这确实让你开始思考数学、算法，以及整个学术界的未来。”荷兰埃因霍温理工大学的Bart Jansen说。（徐锐）