paulwei

很多人看到 OpenAI 刚刚用 AI 证伪了指数时间假设（ETH） 所以，OpenAI要毁灭人类现有的社会秩序了吗？未来是不是 Token 够多，我们就能解决任何问题了？ 今天这篇炒的很热的 @OpenAI 的ETH解法论文，普遍大众认知似乎是 1 - PNP问题解决了，所以AI 解决一切万物的时代到来了 2 - 大加速时代来了，万物的解决方案都可以被计算了 仔细花了一个小时细读研究，发现其实并没有大家想的那么夸张。这里简单解释下几个关键概念： ---------------------------------- 首先，到底什么是 P vs NP 问题？ 我在 16 岁左右刚开始学习算法工程时，曾对 P vs NP 特别痴迷。因为如果它被解决，就说明宇宙万物只要使用足够的算力，就能瞬间获取答案。 简单来说，它的核心是：“可以在多项式时间内【验证】有解决方案的问题，是否等于可以在多项式时间内【获得】解决方案？” 即，可以在多项式时间内证明有解决方案的问题，是否等于可以在多项式时间内获得解决方案。 什么是多项式时间？ 简而言之，任何算法都可以边简化为 o(n)，o(n^2) 等等多项式方程，n 是数据的规模，o 则可以通过 n 计算出所需要的计算时间。 换言之，如果 P = NP，则一切事物都可以被计算，相当于人类拿到了宇宙的“作弊码”。 从今往后，只要token够多： • 我们可以瞬间反向推导，研发出治愈任何绝症的特效药。 • 研发火箭，AI 能在几秒钟内穷尽无数可能，抓出那一个完美的发射方案。 • 物流优化、AI 训练、天气预测……全部可以通过砸Token在几秒内解决 ---------------------------------- 但是，如果正如主流科学界认为，P ≠ NP，那么很多问题就没法在多项式时间内，而是在指数时间内完成。 什么是指数时间？ 指数时间就是说 order of complexity 不是o(n^c)，而是 o(2^n)一类的形式。变量 n 每增加 1，计算量就会直接翻倍。 而存在这类指数时间，且无法转化为多项式时间的问题，就意味着有些问题就算你一直烧Token，也不知道什么时候才能获得解法。 现实中，新药研发的蛋白质折叠、保护你网银安全的 RSA 加密算法，全都是顶级的指数时间难题。就算你把全地球的算力烧干，计算机算到太阳系毁灭也拿不到答案。 一旦 P = NP 成立，指数时间问题可以通过算法工程转化为多项式时间问题，人类可以靠AI创造一切，也可以毁灭并破解一切。 ---------------------------------- 那么，这次的ETH问题和PNP问题的联系在哪里呢？ 大家都在提的点，就是ETH问题证明了3SAT这个指数时间问题有更好的解决方案，所以似乎解决了PNP。 但实际上并不是如此。即便3SAT这个指数时间案例被证伪，PNP仍然没有解决。 为什么？因为这次的ETH问题，本质上是将 o(2^n) 指数时间，转化为了 2^{O(n/\sqrt{\log n})} 这个次指数时间，而这仍然不是多项式时间。 随着n的数量增大，order of complexity的结果仍然会爆炸式增加，只是它不是指数性，而是“次指数性”的。本质上，AI 只是把时间从“几百亿年”缩短到了（比如）“几亿年”。 当然，这也不是说这件事情本身不值得警惕。因为 AI 已经提出了一种人类未曾想到的减少指数时间的方案。 那么，随着 AI 进一步发展，很多原本被判了死刑、认为 “不可能算得更快” 的经典难题，全部重新变成了未解之谜。 也就是说，“指数时间无法成为多项式时间” 这一假设，仍然有被推翻的可能，不过，并不是现在。 就像另外一个 “ETH” 的V神 @VitalikButerin 前段时间针对 ECDSA 算法存在被 AI 攻破的可能性这件事情发表的那句话一样： 在任何数学结构上，比起“刚好只有 3 种解决方案”，“存在隐藏的第 4 种”更有可能。