MIT 的 Ryan Williams 刚发帖说，OpenAI 有个内部模型给出了一份声称能反驳 ETH 的结果，他和 Russell Impagliazzo、Mohan Paturi 被请来组织一次公开、独立的审查。

ETH 是指数时间假说，和以太坊没关系。大意是 3-SAT 这类问题，没法在关于变量数的亚指数时间内解完。很多“这个问题的算法已经快不了了”的下界，都是在它成立的前提下证出来的，真被推翻的话，细粒度复杂度里一大片结论得重新看。它比 P≠NP 强得多，所以推翻 ETH 也不等于 P=NP。

现在还只是一个主张，审查才要开始。

让我多看了两遍的是这份名单：Impagliazzo 和 Paturi 就是当年提出 ETH 的那两位。

#人工智能 #OpenAI #计算机科学 #算法 #数学