指数时间假设
计算复杂性理论中关于精确算法复杂度的核心假设，断言3-SAT问题不存在时间复杂度为2^{o(n)}的算法，为NP难问题提供细粒度下界框架
核心事实
时间轴 (近 90 天)
复杂度组声明了一个确定性算法，能精确计算任意合取范式公式的可满足解数量，快到足以推翻指数时间假设（ETH）。
ETH的核心断言是：3-SAT问题不存在在亚指数时间内求解的算法，具体形式为2^Ω(n)。
SETH比ETH更强，ETH只要求3-SAT不存在2^{o(n)}算法，而SETH对一般k-SAT给出了更精细的指数下界。
若ETH被证伪，SETH自然不成立；但反之不成立——SETH被证伪不一定推翻ETH。
若ETH成立，则编辑距离问题不存在O(n^{2-ε})算法；若SETH成立，则动态时间规整等问题也有类似下界。
证伪ETH的途径主要有两种：一是构造出具体的亚指数算法；二是通过某种非构造性论证证明此类算法必然存在。
指数时间假设（ETH）由Impagliazzo和Paturi于1999年提出。
ETH的基本形式断言：对于3-SAT问题，任何算法在最坏情况下的时间复杂度至少为2^{δn}，其中n为变量数，δ为某个正常数。
ETH至今未被证明或证伪，但已成为参数化复杂性、精确算法设计等领域的基石假设。
模型在Kakeya猜想、ETH和QCD上的结果目前仍处于需要外部验证的阶段。
还有 1 条时间轴事件
全部知识事实 (11)
ETH至今未被证明或证伪，但已成为参数化复杂性、精确算法设计等领域的基石假设。
75%部分验证指数时间假设（ETH）由Impagliazzo和Paturi于1999年提出。
75%待验证复杂度组声明了一个确定性算法，能精确计算任意合取范式公式的可满足解数量，快到足以推翻指数时间假设（ETH）。
50%待验证ETH的核心断言是：3-SAT问题不存在在亚指数时间内求解的算法，具体形式为2^Ω(n)。
50%待验证若ETH被证伪，SETH自然不成立；但反之不成立——SETH被证伪不一定推翻ETH。
50%待验证若ETH成立，则编辑距离问题不存在O(n^{2-ε})算法；若SETH成立，则动态时间规整等问题也有类似下界。
50%待验证证伪ETH的途径主要有两种：一是构造出具体的亚指数算法；二是通过某种非构造性论证证明此类算法必然存在。
50%待验证SETH比ETH更强，ETH只要求3-SAT不存在2^{o(n)}算法，而SETH对一般k-SAT给出了更精细的指数下界。
50%待验证模型在Kakeya猜想、ETH和QCD上的结果目前仍处于需要外部验证的阶段。
50%待验证ETH的基本形式断言：对于3-SAT问题，任何算法在最坏情况下的时间复杂度至少为2^{δn}，其中n为变量数，δ为某个正常数。
50%待验证OpenAI近期分享了其在Kakeya猜想、指数时间假设（ETH）和量子色动力学（QCD）上的模型结果。
50%