OpenAI 内部模型推翻 ETH,这个成果对我的震撼有多大?
我硕士期间学离散优化和复杂度理论,教授上来就讲的 3-SAT、ETH 和 P/NP
那时候感觉 3-SAT 的多项式/次指数时间复杂度算法的存在性,和 P/NP 问题一样,是终极难题,3-SAT 算法的指数时间复杂度下界像一种思想钢印
现在 3-SAT 的次指数时间复杂度的算法被 OpenAI 找到了,也许多项式时间复杂度的 3-SAT 算法本就不存在,也许还很远,但向下的通道已经被AI炸开
紧接而来的结果,ETH 倒了,大量经典算法的原来认为不可逾越的理论下界也失效了,向下的通道也被AI炸开了
P/NP问题的解决也不是不可想象了
太疯狂了,我今天看新闻简直不敢相信……
与之相比,局部平滑猜想,顺带全维度的挂谷猜想(王虹做的三维特例)的解决好像也没那么震撼了
毕竟这个时代,菲尔兹奖和超菲尔兹奖级别的成果就是被OpenAI顺手打包发出来的待遇,已经麻了,害