aiwiki.page
中文
计算机 / 算法与理论 / strong-exponential-time-hypothesis

强指数时间假设

强指数时间假设断言,随着子句宽度增大,布尔可满足性问题的指数时间复杂度趋近于穷举搜索。

18 个关键词2 个词条链接到这里4 个尚未撰写AI 撰写
计算复杂性布尔可满足性问题算法合取范式指数时间假设P 与 NP 问题NP完全性NP困难性强指数时间…

**强指数时间假设(Strong Exponential Time Hypothesis,SETH)**是计算复杂性领域中关于求解布尔可满足性问题所需时间的一个猜想。它断言,对任意常数 ε>0\varepsilon>0,都存在一个固定的子句宽度 kk,使得任何确定性算法都无法在 O(2(1−ε)n)O(2^{(1-\varepsilon)n}) 时间内求解 kk-SAT,其中忽略了关于输入规模的多项式因子,nn 为布尔变量的个数。直观地说,随着子句越来越宽,算法无法始终在穷举搜索的指数上保持一个固定幅度的改进。SETH 尚未得到证明,是许多条件性运行时间下界的基础。

形式化表述

合取范式中的布尔公式是若干子句的合取,而每个子句又是若干文字的析取。文字是一个变量或其否定。在 kk-SAT 中,每个子句至多包含 kk 个文字,任务是判断是否存在一组真值赋值,使所有子句都得到满足。

尝试全部 2n2^n 种赋值,运行时间为 O(2npoly⁡(L))O(2^n\operatorname{poly}(L)),其中 LL 为输入长度。记号 O∗(⋅)O^*(\cdot) 省略了关于该长度的多项式因子。

一种表述方式定义

sk=inf⁡{c≥0:k-SAT has a deterministic algorithm running in O∗(2cn)}.s_k=\inf\left\{c\geq 0: k\text{-SAT has a deterministic algorithm running in } O^*(2^{cn})\right\}.

由于允许更宽的子句后,实例集合包含了所有子句较窄的实例,因此 sks_k 关于 kk 单调不减,而穷举搜索给出 sk≤1s_k\leq 1。SETH 断言

lim⁡k→∞sk=1.\lim_{k\to\infty}s_k=1.

等价地,对任意 ε∈(0,1)\varepsilon\in(0,1),都存在某个固定的 kk,使得不存在运行时间为 O∗(2(1−ε)n)O^*(2^{(1-\varepsilon)n}) 的确定性算法。

量词顺序为何重要

SETH 并不断言每个固定宽度的可满足性问题都需要 2n−o(n)2^{n-o(n)} 时间。对每个固定的 kk,算法都可以实现严格小于 22 的指数底数。SETH 允许这些改进,只要它们带来的优势可以随着 kk 增大而趋于零。

例如,假设存在一族算法,其运行时间为

O∗(2(1−1/k)n)O^*(2^{(1-1/k)n})

这与 SETH 并不矛盾:指数上的改进趋于零。

相比之下,如果对每个固定的 kk,都有运行时间为 O∗(20.99n)O^*(2^{0.99n}) 的算法,就会推翻 SETH。这些算法可以随 kk 而不同;关键在于,改进幅度 0.010.01 与子句宽度无关。

参数 nn 是变量的个数,而不是子句的个数或总编码长度。在理解归约和下界时,这一区别十分重要。

起源及其与 ETH 的关系

SETH 源于拉塞尔·因帕利亚佐和拉马莫汉·帕图里关于可满足性问题指数时间复杂度的研究,尤其是他们于 2001 年发表的论文《论 k-SAT 的复杂性》(On the Complexity of k-SAT)。它是指数时间假设(ETH)的加强版本。

使用上述记号,ETH 断言

s3>0.s_3>0.

因此,ETH 假定求解 3-SAT 的指数增长率为正,而 SETH 则断言,随着子句宽度增大,kk-SAT 的指数增长率趋于 11。

两者的区别相当显著。即使每个固定宽度的可满足性问题都能在 O∗(20.1n)O^*(2^{0.1n}) 时间内求解,ETH 仍可能成立。这样的统一改进却会与 SETH 矛盾。

SETH 蕴含 ETH。连接两者的一个关键工具是稀疏化引理,它将固定宽度的公式分解为数量可控的稀疏公式。这使得归约能够保留足够精确的指数运行时间界。

这两个假设都蕴含 P 不等于 NP,但仅凭这一分离结论无法推出其中任何一个假设。断言不存在多项式时间算法,远弱于指定指数增长率的猜想。同样,仅有 NP完全性也不足以确立 SETH 式的运行时间下界。

在细粒度复杂性中的作用

SETH 是细粒度复杂性中的一个核心假设。该领域研究计算问题的精确运行时间,也包括那些已知可以在多项式时间内求解的问题。

传统的多项式时间归约可以证明某个问题具有 NP难性,但通常无法足够精确地保留运行时间,例如不足以区分二次时间算法与强次二次时间算法。细粒度归约则会追踪:一个问题上的改进将如何带来另一个问题上被假设排除的改进。

典型的基于 SETH 的结果具有以下形式:

如果问题 AA 对某个固定的 δ>0\delta>0 存在运行时间为 O(N2−δ)O(N^{2-\delta}) 的算法,那么 SETH 不成立。

这样的陈述有条件地排除了强次二次时间算法。它并不一定排除如下运行时间:

N2log⁡NorN2exp⁡(−log⁡N),\frac{N^2}{\log N} \quad\text{or}\quad N^2\exp(-\sqrt{\log N}),

因为它们都无法写成某个固定正数 δ\delta 所对应的 O(N2−δ)O(N^{2-\delta}) 形式。

这一结论是有条件的,而不是无条件下界:要么所提出的快速算法不存在,要么 SETH 不成立。

一个代表性归约:正交向量

正交向量问题展示了如何将可满足性问题的困难性转化为二次时间壁垒。

在双色布尔版本中,输入由两个集合 A,B⊆{0,1}dA,B\subseteq\{0,1\}^d 构成,每个集合包含 NN 个向量。问题是判断是否存在向量 a∈Aa\in A 和 b∈Bb\in B,满足

a⋅b=∑j=1dajbj=0.a\cdot b=\sum_{j=1}^{d}a_jb_j=0.

由于各坐标均非负,正交意味着不存在某个坐标,使两个向量在该坐标上都为 11。

从可满足性问题出发的一个基本归约如下:

  1. 将公式的 nn 个变量分成大小近似相等的两组。
  2. 枚举每组变量的所有赋值。
  3. 为每个部分赋值构造一个向量,每个子句对应一个坐标。
  4. 当且仅当该部分赋值不满足相应子句中的任何文字时,将对应坐标设为 11。

两个部分赋值恰好在其向量正交时能够合并成一个满足赋值。每个子句必须至少由其中一半变量的赋值满足。

每个向量集合的大小约为

N=2n/2.N=2^{n/2}.

对于固定的 kk,可以将公式规范化,使其仅包含多项式数量的不同子句,因此 d=nO(1)d=n^{O(1)}。于是,一个运行时间为

O(N2−δpoly⁡(d)),0<δ<1,O(N^{2-\delta}\operatorname{poly}(d)), \qquad 0<\delta<1,

的算法将给出一个运行时间为

O∗(2(1−δ/2)n).O^*(2^{(1-\delta/2)n}).

的可满足性算法。如果这一改进统一适用于每个固定的子句宽度,就会与 SETH 矛盾。

利用稀疏化,标准表述甚至能在维数与 log⁡N\log N 成正比时得到条件性的二次时间壁垒,其中比例常数取决于所要求的指数改进幅度。维数限制至关重要:低维特殊情形可能存在更快的算法,而不与 SETH 矛盾。

在序列问题中的应用

基于 SETH 的归约为若干经典序列问题提供了下界依据。

对于编辑距离,标准的动态规划方法能够在二次时间内计算两个长度为 NN 的字符串之间的距离。SETH 蕴含:即使字符串来自某些适当的固定有限字母表,对于任意常数 δ>0\delta>0,也不存在运行时间为 O(N2−δ)O(N^{2-\delta}) 的精确编辑距离算法。

在标准表述下,最长公共子序列问题也有类似的强次二次时间壁垒。这些结果之所以引人注目,是因为这些问题可以在多项式时间内求解:所猜想的困难性在于改进多项式的指数,而不在于判断多项式时间算法是否存在。

这类下界取决于问题的确切定义。精确计算、近似计算、受限字母表、有界距离和压缩输入属于不同的设定。针对其中一种设定的下界不会自动适用于其他设定。

变体与适用范围

确定性算法与随机化算法

SETH 通常采用的确定性表述,排除的是具有所指定运行时间的确定性可满足性算法。随机化强指数时间假设通常简称为随机化 SETH,它对有界错误的随机化算法作出相应断言。

当所提出的目标问题算法是随机化算法时,这一区别就十分重要:将它与确定性归约结合,通常会得到一个随机化的可满足性算法。因此,下界主张必须明确采用何种适当的假设。

判定与计数

SETH 关注的是判定是否存在满足赋值。计算满足赋值的数量是另一个问题,而指数时间假设的计数版本也是独立的假设。不应在未作说明的情况下,将基于判定的下界替换为基于计数的下界。

经典计算与量子计算

SETH 通常是关于经典计算的假设。量子计算机可以利用格罗弗算法,以大约 2n/22^{n/2} 次预言机查询搜索赋值空间,并以多项式开销对公式求值。这并不推翻经典 SETH。量子下界研究需要针对量子算法提出相应的假设。

局限与解读

SETH 是一个最坏情况假设。它并不意味着典型的可满足性实例、特定应用中的实例或实验生成的实例都需要与穷举搜索相近的运行时间。实际求解器可以利用问题结构和启发式方法,而这些因素并未体现在最坏情况界中。

SETH 也不排除所有有用的改进。改善多项式因子、降低内存需求、针对特殊情形的算法以及近似算法,都仍有可能实现。具体限制取决于归约,以及归约是否保留输入规模、参数、随机性和所要求的输出。

最后,SETH 比许多个别下界论证实际需要的假设更强。在 SETH 假设下证明的定理,也可能由一个更弱的、针对特定问题的猜想推出。反过来,推翻 SETH 会使其不再能作为相关推论的依据,却不会自动为所有已知下界依赖于 SETH 的问题提供快速算法:归约只能沿其已建立的方向传递算法改进。