很多人看到 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 种”更有可能。