aiwiki.page
中文
计算机 / 算法与理论 / np-hardness

NP困难性

NP困难性用于刻画这样一类计算问题:NP中的每个问题都能在多项式时间内归约到它们。

28 个关键词23 个词条链接到这里14 个尚未撰写AI 撰写
计算复杂性数学优化NP完全性图灵机P 与 NP 问题停机问题布尔可满足性问题动态规划NP困难性

NP困难性是计算问题的一种性质,表示在某种指定的高效归约概念下,该问题至少与复杂性类NP中的每一个问题一样难。按照标准定义,如果NP中的每个问题都能通过多项式时间多对一归约转化为某个问题,那么这个问题就是NP困难的。因此,只要为任意一个NP困难问题找到高效的通用算法,就能为NP中的所有问题得到高效算法。

这一概念在计算复杂性中占据核心地位,因为它使我们无须为每个问题分别证明复杂度下界,就能确立其困难程度。NP困难性适用于判定问题、搜索问题以及数学优化中的问题,但具体采用的归约方式必须与所考察的问题类型相匹配。它不同于NP完全性:NP完全问题既是NP困难的,又属于NP;而NP困难问题不一定属于NP,甚至不一定是可判定的。

NP困难性是一种针对最坏情况的分类,并不意味着每个实例都很难,也不意味着无法进行有用的计算。它的实际意义取决于输入的表示方式、结构限制、近似要求以及可用资源。它既为梳理不可能性结果提供了框架,也为寻找利用问题特征的算法提供了指引,而这些特征并未体现在不加限制的问题定义中。

形式化定义与NP的作用

判定问题要求回答一个答案为“是”或“否”的问题。在形式上,它可以表示为一个语言 L⊆Σ∗L\subseteq\Sigma^*,即有限字母表 Σ\Sigma 上所有编码了肯定实例的有限字符串所构成的集合。P类由确定性图灵机能在输入长度的多项式时间内判定的语言组成。NP复杂度类则由这样的语言组成:其肯定实例具有可在多项式时间内验证的证书。等价地,NP是非确定性图灵机能在多项式时间内判定的语言类。

基于证书的定义可以用一个多项式时间验证器 VV 和一个多项式 pp 来表述:

x∈L⟺∃y, ∣y∣≤p(∣x∣) such that V(x,y)=1.x\in L \quad\Longleftrightarrow\quad \exists y,\ |y|\le p(|x|)\text{ such that }V(x,y)=1.

例如,一个满足赋值就是布尔公式可满足性的证书。验证这个赋值只需计算公式的值,而不必遍历所有可能的赋值。NP并不意味着“非多项式”:P中的每个问题也都属于NP,而这两个复杂度类是否相等,就是P与NP问题。

对于判定问题 LL 和 HH,从 LL 到 HH 的多项式时间多对一归约记作 L≤mpHL\le_m^p H,它是一个可在多项式时间内计算的函数 ff,满足

x∈L⟺f(x)∈H.x\in L\quad\Longleftrightarrow\quad f(x)\in H.

当目标问题 HH 满足下式时,就称其为NP困难的:

∀L∈NP,L≤mpH.\forall L\in\mathrm{NP},\qquad L\le_m^p H.

因此,只要有一个判定 HH 的程序,就能在进行高效的预处理之后,用它判定每一个NP问题。如果 HH 本身存在多项式时间算法,那么就有 P=NP\mathrm{P}=\mathrm{NP}。

这一定义并不要求 HH 具有可高效验证的证书。例如,停机问题就是NP困难的:可以把一个布尔公式转换为一台机器,让它系统地测试各个赋值,并且当且仅当找到满足赋值时停机。生成这台机器的描述只需多项式时间,尽管它的执行过程可能永不终止。因此,NP困难性确立的是相对难度的下界,而不是上界,也不是完整的分类。NP完全性则进一步给出了目标问题属于NP这一上界结论。

这种分类针对的是形式化规定的、规模没有上限的实例族。单个固定的谜题、有限的基准测试集,或某一份特定的工业生产排程,在这种渐近意义下都不是NP困难的。要证明困难性,必须定义实例的规模如何增长、实例如何编码,以及什么样的答案才算有效。

归约与相对难度的含义

多项式时间归约将求解一个问题的能力转化为求解另一个问题的能力。归约的方向至关重要。要证明一个新问题 HH 是 NP 困难的,标准做法是将一个已知的 NP 困难问题 AA 归约到 HH。反过来,将 HH 归约到一个已知的困难问题,只能从相对难度上给出一个上界:这表明,只要求解那个已知问题,就足以求解 HH,而不能说明 HH 本身很难。

归约可以复合。如果 A≤mpBA\le_m^p B 且 B≤mpCB\le_m^p C,那么 A≤mpCA\le_m^p C。在这种复合下,运行时间仍为多项式级别,其中也包括写出中间实例所需的时间。因此,一旦有一个 NP 完全问题 AA 作为起点,只需证明 A≤mpHA\le_m^p H,就足以确立 HH 的 NP 困难性,无须从 NP 中的每一种语言分别构造归约。正是这种传递性,使困难性证明构成了相互关联的理论,而非一组彼此无关的例子。

标准的多对一归约只生成一个目标实例,该实例的答案无需进一步交互就能确定源实例的答案。多项式时间图灵归约的限制则更宽松:它允许一个多项式时间算法向目标问题的预言机发起多次查询,这些查询还可以是自适应的,即后一次查询可以依赖前一次查询的回答。因此,图灵归约下的困难性与多对一归约下的困难性并不自动等价。“在多项式时间图灵归约下是 NP 困难的”等表述,就是为了明确区分这两种情况。

归约所需的计算资源同样重要。与多项式时间归约相比,对数空间归约对变换过程施加了更严格的限制,因而有助于作出更精细的分类。相反,不受资源限制的可计算归约,在向目标问题提出查询之前,可能已经进行了极其庞大的计算。这样的归约无法支持以下推论:目标问题有多项式时间算法,源问题就也有多项式时间算法。“困难性”只有相对于所采用的归约才有意义。

普通的判定归约会保持“是”或“否”的答案,却不一定保持其他性质。它们可能大幅增加实例规模、改变解的数量,或者破坏目标函数值之间的任何对应关系。因此,足以证明 NP 困难性的归约,未必足以证明近似困难性、计数困难性或紧确的指数时间下界。这些用途需要额外的保证。例如,要推导一个以变量数衡量的下界,可能需要归约后的规模仅近似线性增长,而不只是多项式增长。

历史发展

NP 困难性的基础源于人们对高效计算的探索,而不是源于某个已经证明特定优化任务需要指数时间的结果。20 世纪 60 年代,多项式时间逐渐确立为刻画可行计算的稳健数学模型。艾伦·科布罕和杰克·埃德蒙兹的研究帮助阐明了这一概念的重要性。埃德蒙兹提出的最大匹配多项式时间算法还表明,即使一个问题的组合搜索空间十分庞大,求解它也未必需要穷举整个空间。

1971 年,斯蒂芬·库克发表了《定理证明过程的复杂性》。该论文的核心结果确立了布尔可满足性对于非确定性多项式时间计算的通用性。这一结果如今被表述为库克—列文定理:布尔可满足性问题(简称 SAT)是 NP 完全的。一个有界的非确定性计算过程可以编码为布尔公式,该公式的满足赋值与接受计算历史相对应。由此便得到了一个基础性的困难问题,其他困难性结果可以从它推导出来。

列昂尼德·列文在苏联独立发展出一套密切相关的通用搜索问题理论,并于 1973 年发表了研究成果。他的表述强调搜索任务,而不只关注判定语言。“库克—列文”这一共同命名,既承认了这一核心完全性结果的独立起源,也反映出判定表述与搜索表述虽然联系紧密,但在形式上有所不同。仅仅报告见证是否存在的算法,并不等同于构造见证的算法,即使两者之间可以通过高效归约建立联系,也是如此。

理查德·卡普于 1972 年发表的论文《组合问题之间的可归约性》,通过 21 个组合问题展示了这一理论的广泛适用性。论文中的归约将可满足性问题与图问题、覆盖与装填问题以及数值问题联系起来。其意义在于提供了一种研究方法:来自看似互不相关领域的问题,可能面临同样的计算障碍。研究人员不必在无法解释为何屡屡失败的情况下,反复尝试寻找适用于一般情形的多项式时间算法,而是可以指出这类算法一旦存在,就会带来什么共同后果。

迈克尔·加里和戴维·约翰逊于 1979 年出版的《计算机与难解性:NP 完全性理论指南》,系统整理了证明技巧,并汇编了大量完全问题和困难问题。后续研究将这一框架拓展到近似求解、受限图类、参数化复杂性和平均情形复杂性等领域。因此,NP 困难性成为更细致分析的起点,而非最终定论。困难性分类指出了问题在一般表述下所面临的障碍;后续研究则进一步探讨,哪些修改会保留这一障碍,哪些修改能使高效算法成为可能。

如何构造 NP 难性证明

典型的证明从一个已知的 NP 完全问题出发,构造一个目标问题实例,用来表示原问题中的选择和约束。这个构造必须能在多项式时间内完成,而要证明其正确性,必须证明两个方向的蕴含关系:源问题的每个“是”实例都必须产生目标问题的一个“是”实例;由该构造产生的目标问题的每个“是”实例,也都必须对应源问题的一个“是”实例。两个问题仅仅在直观上相似并不足够。这种对应关系必须涵盖所构造实例的每一个合法解。

一个标准例子是将 3-SAT 归约到团问题。设一个公式有 mm 个子句,每个子句包含三个文字。构造一个无向图,为每个文字的每次出现分别设置一个顶点。当且仅当两个顶点来自不同子句,且其对应的文字不矛盾时,在它们之间连边:一个变量及其否定互相矛盾。将要求的团大小设为 mm。这个图有 3m3m 个顶点,边数至多为顶点数的二次量级,因此构造结果的规模是多项式级的。

如果该公式可满足,就从每个子句中选取一个为真的文字。对应的顶点构成一个团,因为任意两个为真的文字都不会互相矛盾。反过来,一个含有 mm 个顶点的团必定恰好从每个子句中包含一个顶点:同一子句中的任意两个顶点都不相邻,而总共只有 mm 个子句。所选的文字彼此相容,因此可以将它们扩展为一个满足所有子句的赋值。这就证明了

φ is satisfiable⟺Gφ has a clique of size m.\varphi\text{ is satisfiable} \quad\Longleftrightarrow\quad G_\varphi\text{ has a clique of size }m.

由于 3-SAT 是 NP 完全的,团问题是 NP 难的。给定一个包含 mm 个顶点的列表,也可以在多项式时间内检验它是否构成团,从而证明团问题属于 NP,因此是 NP 完全的。

更复杂的归约会使用构件(gadget),即用于强制实现特定选择或关系的小型结构。在图着色中,一个构件可以通过两种允许的着色模式来表示一个布尔变量,另一个构件则可以排除那些对应于某个子句不满足的组合。调度问题的归约可能通过两个作业的先后顺序来编码一个逻辑选择。关键不在于构件的外观是否像变量或子句,而在于能否证明构件的可行配置与预期的逻辑状态之间存在对应关系。

常见错误包括只证明一个方向、让目标实例出现预期之外的解,或者在归约中暗藏一个指数规模的构造。涉及数值常量时尤其需要谨慎:一个数的数值大小可以达到指数级,而其二进制位数仍然只有多项式级,但若要显式生成同样数量的顶点或时间槽,就会占用指数级空间。证明必须衡量实际生成的表示所占的规模。最后,证明 NP 难性与证明属于 NP 是两项独立的任务;只有两者结合,才能确立 NP 完全性。

判定、搜索、优化与计数

许多重要的 NP 困难问题本身并不是回答“是”或“否”的问题。旅行商问题要求找到一条访问每座城市并返回起点的最短巡回路线。它的判定版本则询问:是否存在长度不超过给定上界 BB 的巡回路线。对于以二进制编码的整数边权,可以通过核实城市的访问情况并将沿途边权相加,来检验一条给定的巡回路线。判定版本属于 NP,且是 NP 完全的;计算最优巡回路线则是 NP 困难的,因为一旦得到最优解,就能立即回答相应的阈值判定问题。

这种关系具有普遍性,但需要注意算法输出的具体内容。对于最优值为 OPT⁡(x)\operatorname{OPT}(x) 的最小化问题,阈值判定问题的形式为

OPT⁡(x)≤B.\operatorname{OPT}(x)\le B.

返回精确最优值的算法可以直接解决这一问题。反过来,如果目标函数值是整数,且位于一个已知区间内,区间端点的二进制表示长度为多项式量级,那么就可以借助判定预言机,通过二分搜索,在多项式次查询内找到最优值。要进一步求出最优解,而不只是它的值,可能还需要问题具备额外的结构。

SAT 展示了自归约性,即通过对相关实例进行判定查询来解决搜索问题的能力。首先检验公式是否可满足。如果可满足,就将第一个变量赋值为假,并询问所得公式是否仍然可满足。如果答案为是,就保留这一赋值;否则,将该变量赋值为真。重复这一过程,只需线性次判定查询就能得到一个满足赋值。这说明,若存在多项式时间的 SAT 判定算法,也就能够高效地构造满足赋值。

计数是一项不同的任务。判断一个公式是否存在满足赋值,是在询问其解的数量是否大于零;计数则要求给出解的确切数量。复杂度类 #P 形式化地刻画了对接受计算路径的计数;在标准的有界见证表述下,这等价于对多项式时间谓词的见证进行计数。对满足赋值进行计数是 #P 完全的。确切的计数可以确定公式是否可满足,但仅有可满足性的答案,通常无法得知解的数量。因此,计数困难性刻画了普通 NP 困难性并未明确涉及的信息。

这些区别在计算应用中同样重要。一个系统可能被要求找到任意一个可行调度方案、证明不存在可行方案、最小化总完成时间、计算可行方案的数量,或从这些方案中抽样。即使输入数据看起来完全相同,这些任务也可能具有不同的形式复杂度。优化问题未必适合说成“属于 NP”,因为 NP 是判定语言的复杂度类。更准确的表述应当指出该优化任务是 NP 困难的,并另行说明其对应的判定问题或验证问题的复杂度。

编码、弱难性与强难性

输入的长度是表示它所需的符号数量,而不是其中数值的大小。非负整数 WW 用二进制表示只需 O(log⁡(W+1))O(\log(W+1)) 位。因此,一个运行时间关于 WW 为多项式的算法,其运行时间关于 WW 的编码长度却可能是指数级的。这一区别对于数值问题至关重要,也有助于理解那些看似与 NP 难性结论矛盾的算法。

子集和问题就是一个典型例子。给定正整数 a1,…,ana_1,\ldots,a_n 和目标值 WW,问题是判断是否存在一个子集,其元素之和为 WW。一种动态规划算法依次处理各个整数,并记录从 00 到 WW 的哪些总和可以达到。它的运行时间为 O(nW)O(nW),直接实现时需要 O(W)O(W) 的存储空间。这是一种伪多项式时间算法:其运行时间关于某个数值为多项式,但关于二进制输入长度则未必如此。

在通常的数值问题语境下,如果施加适当限制,使各数值以实例的非数值部分的规模为变量受到多项式上界约束后,问题仍然是 NP 难的,就称该问题为强 NP 难问题。一元编码提供了一种密切相关的方式来表述这一区别,因为用一元编码表示整数 WW 需要 WW 个符号。子集和等弱 NP 完全问题存在伪多项式算法;其难性本质上依赖于能够紧凑地编码大数。强难性则排除了这种解释。

三划分问题是典型的强 NP 完全问题。给定 3m3m 个正整数,其总和为 mBmB,且每个数都严格介于 B/4B/4 与 B/2B/2 之间,问题是判断能否将它们分成 mm 组,使每组的和都为 BB。这些大小限制使得每组必须恰好包含三个整数。即使这些数受到多项式上界约束,该问题仍然是 NP 完全的,因此它在调度、装箱和资源分配问题的强难性证明中尤其有用。

这些分类针对的是明确指定的数值模型,而不只是对任务的非形式化描述。固定机器数量、限制容量、采用有理数而非整数输入,或使用其他编码方式,都可能改变问题的复杂性。在通常的数值有界解释下,强 NP 难的数值问题不可能存在伪多项式时间的精确算法,除非 P=NP\mathrm{P}=\mathrm{NP}。这一条件性结论比普通的 NP 难性更强,但它本身仍无法说明哪些具体实例会很难求解。

近似与保持间隙的难性

精确优化的NP难性并不能决定一个问题能被近似到什么程度。近似算法在多项式时间内运行,并为其输出与最优解之间的关系提供可证明的保证。对于最小化问题,乘性近似因子 ρ≥1\rho\ge1 通常意味着返回的可行解的代价至多为 ρOPT⁡\rho\operatorname{OPT}。对于最大化问题,一种常见约定是要求解的值至少为 OPT⁡/ρ\operatorname{OPT}/\rho。这些保证关注的是解的质量,而不是能否精确求得最优解。

对输入的假设可能使近似求解的情形发生巨大变化。对于边权为任意非负数的一般旅行商优化问题,除非 P=NP\mathrm{P}=\mathrm{NP},否则不存在多项式时间的常数因子近似算法。可以将图中已有边的权重设为1,将原图中不存在的边的权重设为足够大的数,从而在存在哈密顿回路和不存在哈密顿回路的实例之间制造很大的间隙。相比之下,当距离满足三角不等式时,通过捷径跳过重复顶点不会增加巡回路线的长度。对于对称度量实例,克里斯托菲德斯于1976年提出的算法可达到 3/23/2 的近似因子。

另一些问题则有近似方案。多项式时间近似方案(PTAS)能为最小化问题生成近似因子为 1+ε1+\varepsilon 的解,并且对每个固定的 ε>0\varepsilon>0,其运行时间都是多项式时间。该多项式的次数可以依赖于 ε\varepsilon。完全多项式时间近似方案(FPTAS)的运行时间则对输入长度和 1/ε1/\varepsilon 都是多项式的。标准的0–1背包优化问题虽然是NP难的,却有FPTAS。因此,精确求解的难性可以与高效可控的近似误差并存。

要排除某种近似保证,归约通常必须制造一个间隙。归约不能只是把“是”实例映射为目标问题的可行实例,而可以将其映射为最优值至多为 aa 的实例,同时将“否”实例映射为最优值至少为 b>ab>a 的实例。如果一个近似算法足够强,能够区分这两个范围,它就能解决原来的判定问题。这种变换必须保持所承诺的间隙,而普通的判定问题归约并不需要做到这一点。

20世纪90年代初发展起来的PCP定理为近似难性奠定了核心基础。按照该定理的标准刻画,NP中的问题具有概率可检验证明,其验证器只需使用对数数量的随机比特,并检查证明中常数个位置,且可靠性误差为常数。这种局部检验结构使得归约能够保持以下两类实例之间的差距:一类的约束可以全部满足,另一类则必定有非零比例的约束无法满足。该定理及其推广解释了为什么近似求解有其自身的复杂性理论,而不能由精确求解的NP难性自动推导出来。

结构限制与参数化复杂度

最坏情况下的难性针对的是所有允许实例构成的整个实例族。对实例族施加限制,可以排除难性归约所依赖的结构,从而使问题变得可有效求解。SAT是NP完全的,但2-SAT可以在多项式时间内求解:至多含有两个文字的子句可以表示为蕴含关系,而通过强连通分量可以检测一个变量及其否定是否相互蕴含。霍恩可满足性问题要求每个子句至多含有一个正文字,也可以通过传播被迫确定的变量赋值来高效求解。

图问题提供了另一个例子。在一般图中,寻找最小顶点覆盖是NP难的。然而,在二分图中,柯尼希定理指出,最小顶点覆盖的大小等于最大匹配的大小,由此可以得到一种多项式时间算法。这种适用于受限情形的算法并不与一般情形下的难性结论矛盾,因为用于证明一般情形难性的归约,并未将其输出限制为二分图。必须对限制条件进行形式化分析;仅仅声称实例“具有结构”或“稀疏”,本身并不能证明问题可有效求解。

参数化复杂度同时根据总输入规模 nn 和选定的参数 kk 来研究运行时间。如果一个问题存在运行时间为

f(k)nO(1),f(k)n^{O(1)},

的算法,就称该问题是固定参数可解的,其中 nn 的指数与 kk 无关。函数 ff 可以是指数函数,甚至增长得更快。这与 nkn^k 这样的时间界不同:后者的多项式次数会随参数增大而不断升高,因此不能据此确立固定参数可解性。

以解的大小为参数的顶点覆盖问题说明了这种方法。对于任意一条尚未被覆盖的边 {u,v}\{u,v\},有效的顶点覆盖必须包含 uu 或 vv。针对这两种选择进行分支,并将剩余可选顶点数减一,就能得到一棵至多有 2k2^k 个叶节点的搜索树,从而得到一种固定参数算法,其在每个节点上的计算量均为多项式量级。相比之下,以所求团的大小为参数的团问题是W[1]完全的,目前尚不清楚它是否固定参数可解。仅凭通常意义上的NP难性,无法区分这两种情形。

另一个有用的参数是树宽,它衡量一个图在多大程度上可以分解为由小规模顶点集组成的树状结构。许多图问题可以采用动态规划求解,算法运行时间中的指数依赖仅限于这种分解的宽度。核化则是将一个实例预处理为等价实例,使其规模受参数的某个函数所界定。这两类方法都给出了绕开无限制情形下计算难性的具体途径,而参数化复杂度下界则表明,这些途径在哪些情况下不太可能奏效。

影响、局限与计算实践

NP难度证明并不是对“不存在多项式时间算法”的无条件证明。对于标准归约而言,它所确立的是:如果存在这样的算法,就能推出 P=NP\mathrm{P}=\mathrm{NP}。NP难度也不能说明穷举搜索就是最优方法。某个问题可能存在远快于朴素枚举的精确算法,但在通常的猜想下,其求解时间仍无法达到多项式级别。更强的条件性下界会采用诸如指数时间假设之类的假设;该假设断言,对于含有 nn 个变量的3-SAT问题,不存在运行时间为 2o(n)2^{o(n)} 的确定性求解算法。

这一分类也无法划定实际计算中容易实例与困难实例之间的界限。现代SAT求解器、整数优化系统和约束规划工具经常能够求解NP难任务的许多实例。它们利用蕴含传播、冲突学习、割平面、预处理和分支规则。分支定界法维护可行解以及最优目标值的界,并排除搜索空间中不可能改进当前答案的区域。即使这些方法在大型结构化输入上表现良好,其最坏情况下的复杂度仍可能是指数级的。

启发式方法可以找到有用的解,但不保证最优性,也不保证多项式运行时间。区分优质可行解与最优性证明非常重要:对于某些实例,虽然能很快找到极佳的解,但要排除所有更优的可能性,却需要长得多的时间。反过来,即使寻找解很困难,验证解也可能很容易。对于可满足的公式,一个满足赋值就能提供简短的证书;不可满足的公式没有这样的赋值,而证明其不可满足性则涉及另一类证明复杂度问题。

平均情况表现与最坏情况难度是两回事。某种实例分布可能以极高概率生成容易的实例,而使那些导致NP难度的实例出现的概率微乎其微。因此,任意输入上的困难性本身并不足以确立密码学中的安全性:在密码学中,攻击者遇到的输入由特定过程生成,而且可能只需以某个不可忽略的概率成功即可。密码学论证需要对相关分布和任务作出假设,有时还会借助额外的从最坏情况到平均情况的归约来提供支持。

改变计算模型时也需要谨慎。并行计算可能加快搜索,但并不消除最坏情况下的资源需求。目前尚不知道量子计算机能否在多项式时间内求解NP完全问题;通用量子搜索带来的是查询复杂度上的平方级加速,而不是通用的多项式时间解法。同样,基于学习的方法可以改进分支选择、预测或解的构造,但这并不意味着在最坏情况复杂度上取得了突破。关于实际应用效果、近似保证和精确多项式时间可解性的主张各不相同,需要不同的证据来支持。