ETH 被证伪，P=NP 还会远吗
OpenAI 挑战指数时间假设（ETH），究竟意味着什么？有些计算难题，到底是本就无解，还是我们没找到对的方法？OpenAI 10/26 发布的关于指数时间假设（ETH）的最新进展，把这个经典问题再次推到了聚光灯下。ETH 长期以来是计算机理论的基石之一：它认为对于 3-SAT 问题，在变量数规模下，最坏情况不存在次指数时间算法。过去，很多关于“算法极限在哪里”的判断，都建立在这假设之上。而这次新出现的算法，针对固定宽度 SAT 问题，实现了在次指数时间内精确计算出满足条件的解的数量。它的核心思路极为巧妙：将逻辑规则转化为多项式，通过计算特定点上的值与导数，再利用插值法精准还原出原问题的答案。这意味着，图算法、约束推理等领域的许多理论下界，都需要被重新审视；那些曾经被认为“无法再加速”的计算难题，迎来了全新的探索方向。 ETH 被证伪，P=NP 还会远吗[吐舌] OpenAI 人工智能 算法