开发者惊传指数时间假设 ETH 被推翻，SAT 复杂度常识或遭颠覆

akbirthko · x · 2026-10-27

工程师 Eric Zhang（ekzhang1）发推称，本想安静过一晚，却看到「ETH 为假」的消息，深感震撼。

他感叹：有些第一堂 CS 课就学的知识会让人习以为常——比如 SAT 求解需要指数时间——自己从未质疑过这一点，以为更聪明的人早就反复审视过。这里的 ETH 指理论计算机科学中的指数时间假设（Exponential Time Hypothesis），若被证伪将动摇大量基于其上的复杂度下界结论。该说法目前仅为转发链中的消息，细节与正式证明情况尚待确认。