指数时间假设（ETH）

指数时间假设简称ETH,由因帕利亚佐和帕图里在二十世纪末提出。它断言存在一个正常数,使得含n个变量的3-SAT问题不能在2的该常数乘以n次方以内的时间内求解,换言之3-SAT需要真正的指数时间。

概述

P不等于NP只排除了多项式时间算法,却没有说明NP难问题究竟需要多久。ETH是一个更细的定量猜想,它把注意力放在指数的底数和指数上,从而能推导出诸如某问题不存在次指数算法之类的精确结论。

核心特点

• ETH断言3-SAT不存在时间为2的o(n)次方的算法,这里n是变量数目。
• 强指数时间假设SETH更进一步,断言一般的k-SAT随着子句长度k增大,最优底数趋近于2,即无法明显优于暴力枚举。
• 稀疏化引理保证可以把ETH中的度量从变量数换成子句数而结论不变。
• 借助保持子指数关系的归约,ETH的下界可传递到许多其他问题上。

应用场景

ETH是精细复杂度理论的支柱,用来证明具体问题的紧下界。例如在ETH成立的前提下,可证明许多图论和调度问题不存在次指数算法,一些参数化问题不存在特定形式的FPT算法。SETH则被用于证明诸如编辑距离、正交向量等多项式时间问题的下界,解释了为何这些问题多年来无人能显著加速。

常见问题

问:ETH被证明了吗?答:没有。它和P不等于NP一样是未被证明的假设,但被广泛相信成立,研究者常以它为前提推导条件下界。

问:ETH和SETH有什么区别?答:ETH只要求3-SAT需要指数时间,而SETH对随着子句长度增长的最优指数底数给出了更苛刻的上界,SETH比ETH更强,若SETH成立则ETH必成立。