概念ETH / Exponential Time Hypothesis
指数时间假设（ETH）
计算复杂性理论中的核心假设，断言3SAT问题不存在亚指数时间算法，即其复杂度下界至少为2^{Ω(n)}。
核心事实
时间轴 (近 90 天)
10月30日
OpenAI称其系统证明了指数时间假设（ETH）不成立。
待验证50%
10月28日
OpenAI公布了一项数学证明，据称推翻了指数时间假设（ETH）。
待验证50%
10月28日
OpenAI的证明给出了形如 2^n / sqrt(log n) 的算法复杂度上界，该函数属于亚指数范畴，与ETH的断言相矛盾。
待验证50%
10月28日
ETH被推翻并不直接推出P=NP，但移除了一个重要的理论障碍。
待验证50%
10月27日
P≠NP和指数时间假设（ETH）是复杂性理论中未经证明的假设，作为许多结论的推理基石。
待验证50%
10月26日
指数时间假设（ETH）由Impagliazzo和Paturi于1999年提出。
已验证80%