概念SETH / Strong Exponential Time Hypothesis

强指数时间假设

指数时间假设的加强版本，断言k-SAT问题的求解时间下界随k增加趋近于2^n，即无法显著快于暴力枚举。是细粒度复杂性中许多核心猜想的基础。

时间轴 (近 90 天)

10月26日

强指数时间假设（SETH）由Impagliazzo、Paturi和Zane在2001年提出。

待验证50%

10月26日

SETH断言：对于任意δ<1，存在一个足够大的k，使得k-SAT问题无法在O(2^{δn})时间内求解。

待验证50%

10月26日

SETH比ETH更强，ETH只要求3-SAT不存在2^{o(n)}算法，而SETH对一般k-SAT给出了更精细的指数下界。

待验证50%

10月26日

若ETH被证伪，SETH自然不成立；但反之不成立——SETH被证伪不一定推翻ETH。

待验证50%

10月26日

若ETH成立，则编辑距离问题不存在O(n^{2-ε})算法；若SETH成立，则动态时间规整等问题也有类似下界。

待验证50%

强指数时间假设（SETH）由Impagliazzo、Paturi和Zane在2001年提出。

SETH断言：对于任意δ<1，存在一个足够大的k，使得k-SAT问题无法在O(2^{δn})时间内求解。

SETH比ETH更强，ETH只要求3-SAT不存在2^{o(n)}算法，而SETH对一般k-SAT给出了更精细的指数下界。

若ETH被证伪，SETH自然不成立；但反之不成立——SETH被证伪不一定推翻ETH。

若ETH成立，则编辑距离问题不存在O(n^{2-ε})算法；若SETH成立，则动态时间规整等问题也有类似下界。