OpenAI推翻了计算机科学的基石假设

近日，美国人工智能（AI）公司OpenAI称，其AI模型反驳了指数时间假设（ETH）——一个支撑了计算机科学近30年的基础性假设。 ETH于1999年由美国加利福尼亚大学圣地亚哥分校的Russell Impagliazzo和Ramamohan Paturi提出。ETH涉及理论计算机科学中一个经典难题——可满足性问题。假设有一组开关和一张规则列表，每条规则指定3个开关及其各自的位置，只要其中至少一个被指定位置，该规则就得到满足。那么，是否存在一种设置开关的方法，使每条规则都得到满足？这个谜题听起来抽象，但具有现实相关性，因为从芯片设计到调度，再到密码学领域的许多实际问题都可以转化为这种形式。 这是个极其复杂的问题，因为每个开关可以开或关，每增加一个开关，可能的组合数量就会翻倍，即组合数量呈指数增长。10个开关可以给出约1000种组合，而到几百个开关时，组合数量已经超过可观测宇宙中的原子数。因此，寻找满足所有规则的组合或证明不存在解，成了一项艰巨任务。尽管有人找到了无需逐一验证组合的捷径，但仍没有方法能避免解题时间和精力上的指数级增长。Impagliazzo和Paturi提出的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说。