指数时间假设（ETH）：计算复杂性理论中的一个重要假设，通常表述为：3-SAT 不能在亚指数时间（例如 \(2^{o(n)}\)）内求解，其中 \(n\) 是变量数。它常用于推导其他问题的条件性下界，说明某些算法不太可能比特定指数级别更快。
/ˌekspəˈnɛnʃəl taɪm haɪˈpɑːθəsɪs/
The exponential time hypothesis suggests that some NP-complete problems cannot be solved much faster than brute force.
指数时间假设表明，一些 NP 完全问题不太可能比穷举法快很多。
Assuming the exponential time hypothesis, researchers can show that improving the running time of certain parameterized algorithms would contradict known lower-bound expectations.
在指数时间假设成立的前提下，研究者可以证明：若显著改进某些参数化算法的运行时间，将与已知的（条件性）下界预期相矛盾。
该术语由三部分组成：exponential（指数的）+ time（时间，指运行时间复杂度）+ hypothesis（假设）。它并非日常英语短语，而是理论计算机科学中为讨论“指数级运行时间是否不可避免”而形成的专门命名。学术语境中常与 SAT、NP 完全性和下界证明一起出现。
Select Language