指数时间假设(ETH)是计算复杂性中的一个猜想,断言无法在关于变量数的次指数时间内判定三合取范式布尔公式的可满足性。更确切地说,其标准表述断言,求解3-SAT所能达到的最优指数增长率存在一个正的下界。ETH加强了 这一猜想:它不仅排除了多项式时间算法,还排除了范围广泛得多的一类运行时间。它被广泛用于为精确算法和参数化问题建立条件性下界。
形式化定义
布尔可满足性问题询问:是否存在一种对布尔公式中变量的真值赋值,使该公式为真。在 -SAT 中,公式采用合取范式:它是若干子句的合取,每个子句则是至多 个文字的析取。文字是一个变量或其否定。
设 表示变量数, 表示输入长度。对于每个固定的 ,定义最优指数增长率为
ETH断言
因此,存在常数 ,使得不存在能在 时间内判定所有3-SAT实例的确定性算法。
ETH通常被概括为:3-SAT不存在运行时间为 的算法,其中默认省略了关于输入长度的多项式因子。其正增长率表述明确了量词关系:它不仅排除单个次指数时间算法,也排除能够达到任意小的正指数增长率的一系列算法。
诸如 或 这样的运行时间都是关于 的次指数时间;如果能对不加限制的3-SAT达到这样的运行时间,就会推翻ETH。相比之下, 仍然是指数时间,其本身并不违背这一假设。
这里的时间复杂度按最坏情况衡量。ETH并不直接说明典型公式、某个特定应用中的实例,或从某个指定概率分布中抽取的公式有多难求解。
历史发展
罗素·因帕利亚佐(Russell Impagliazzo)和拉马莫汉·帕图里(Ramamohan Paturi)在关于 -SAT复杂性及改进精确指数时间算法的研究中提出了ETH,相关工作于2001年以期刊论文形式发表。
提出这一假设的动机在于,NP完全性对计算难度的刻画还很粗略。假设 ,则NP完全问题不可能存在多项式时间算法,但仅凭这一假设,无法区分 、 和 等运行时间。
ETH为研究这些差异提供了一个框架。其中一项核心支撑性结果是由因帕利亚佐、帕图里和弗朗西斯·赞恩(Francis Zane)提出的稀疏化引理。它使得研究者能够在同时控制变量数和子句数的前提下,将可满足性问题的下界转移到其他问题上。
稀疏化与规模度量的选择
指数下界在很大程度上取决于如何定义输入规模。一个含 个变量的3-SAT公式,其子句数可能远大于 。因此,如果某个归约的输出规模取决于子句数,它就可能无法保留以变量数表示的下界。
稀疏化引理解决了这一问题。对于每个固定的 和每个 ,一个含 个变量的 -CNF公式都可以表示为至多
个 -CNF公式的析取,其中每个公式至多含有 个子句,而 仅依赖于 和 。计算这一分解所需的时间为 乘以输入长度的一个多项式。
原公式可满足,当且仅当分解中至少有一个公式可满足。因此,足够快的稀疏公式求解算法也能导出足够快的一般公式求解算法。
特别地,ETH意味着:只要适当选取稀疏性常数,即使将3-SAT限制在线性子句数的公式上,也仍然不存在次指数时间算法。这使得许多下界论证可以使用 而非仅使用 来度量规模,其中 为子句数。
稀疏化并不是简单地删除冗余子句。它会生成多个公式,这些公式的析取保持了原公式的可满足性。
与其他复杂性假设的关系
P与NP
ETH蕴含P与NP问题的否定答案:
如果 ,那么3-SAT就存在多项式时间算法,其最优指数增长率也就为零。
反方向的蕴含关系尚不清楚。 这一断言并未排除3-SAT存在次指数但超多项式时间算法的可能性。
强指数时间假设
强指数时间假设(SETH)对随子句宽度增大而变化的 -SAT作出了更强的断言:
等价地,对于每个 ,都存在一个固定的 ,使得 -SAT无法在以下时间内求解:
SETH并不断言3-SAT基本上需要 的时间。对于固定且较小的子句宽度,算法可以比穷举枚举快得多,而不违背这一假设。
借助稀疏化引理以及有界宽度可满足性问题之间的归约,可以证明SETH蕴含ETH。反方向的蕴含关系尚不清楚。ETH通常支持对指数部分的增长阶建立下界,而SETH则可以支持关于指数运行时间的底数或多项式运行时间的指数的更精细断言。
随机化与计数变体
标准ETH针对的是确定性判定算法。要排除有界错误的随机化算法,需要采用该假设的随机化版本,通常称为随机化ETH或rETH。
计数指数时间假设通常记作 ETH,关注精确计算满足赋值的数量。它断言,计算3-CNF公式的满足赋值数量存在一个正的指数下界。快速的精确计数算法也能用于判定可满足性,但仅有计数问题的困难性,并不能确立判定问题具有相应的困难性。
通过归约建立条件性下界
ETH的主要用途,是通过计算归约将3-SAT的猜想困难性转移到其他问题上。
假设某个归约将一个含 个变量的稀疏3-SAT公式映射为问题 的一个等价实例,其规模为 。那么,若 存在运行时间为 的算法,就能得到一个运行时间为 的3-SAT算法,从而与ETH矛盾。
归约导致的规模增长至关重要。如果归约产生的实例规模为 ,那么它直接支持的下界所排除的运行时间就变为
通常的NP难性证明往往允许实例规模发生多项式增长。这类证明并不能自动建立紧的指数时间下界。
精确指数时间算法
ETH可用于证明许多图问题和组合问题不存在次指数时间的精确算法。例如,从稀疏3-SAT出发的标准线性规模归约表明,在ETH成立的前提下,一般的顶点覆盖问题不存在运行时间为 的算法,其中 为图的顶点数。
这一结果并不排除将运行时间从 改进到 ,也不排除在受限图类上存在更快的算法。理解下界时,必须注意其具体的实例限制和规模参数。
参数化复杂度
在参数化复杂度中,运行时间同时用输入规模 和参数 表示。典型的固定参数运行时间具有如下形式:
其中 是可计算函数。
与仅将问题归类为参数化难相比,ETH能够建立更强的定量障碍。一个标准例子是团问题:在ETH成立的前提下,对于任意可计算函数 ,都无法在以下时间内判定一个图是否含有大小为 的团:
这排除了将 的指数中通常对 的线性依赖改为次线性依赖的可能性。
ETH还支持以树宽等图结构参数表示的下界。这些下界有助于判断,动态规划算法对参数的指数依赖是否能够得到实质性改进。
适用范围与局限
ETH仍是一个未经证明的猜想。“在ETH成立的前提下”得到的结论是条件性定理:若某个算法突破了所述界限,它将推翻ETH,而不是与一个已证明的无条件下界相矛盾。
理解这类结果时,有几项重要区别需要注意:
- 最坏情况与典型表现。 ETH并不妨碍算法在许多实际实例上高效运行。
- 一般输入与受限输入。 特殊的结构限制可能使次指数时间或多项式时间算法成为可能。
- 判定与近似。 精确判定问题的下界并不自动适用于近似算法。
- 计算模型。 标准ETH本身并不排除具有相同运行时间的随机化算法或量子算法。
- 参数选择。 以变量数、子句数、顶点数、边数或某个结构参数表示的下界,不能与使用另一种度量的下界互换。
这些限定条件本身就是基于ETH的下界的数学内容的一部分:归约、计算模型、输入限制和规模度量共同决定了结果究竟排除了哪些算法。