NP完全性是计算复杂性中的一种分类,用于刻画NP中最难的判定问题。NP是这样一类问题:对于答案为“是”的实例,存在可在多项式时间内验证的证书。一个问题若属于NP,且NP中的每个问题都能通过多项式时间归约转化为该问题,就称其为NP完全问题。因此,只要任意一个NP完全问题存在多项式时间算法,NP中的所有问题就都有多项式时间算法。
这一概念将看似无关的问题联系起来,包括逻辑公式的可满足性、图着色、选择彼此兼容的任务、路线设计,以及某些调度和分配问题。它的重要性不在于证明这些问题无法求解,而在于精确确立了它们在最坏情况下计算难度之间的关系。是否存在某个NP完全问题具有多项式时间算法,与尚未解决的P与NP问题等价。
这一理论起源于20世纪70年代初斯蒂芬·库克、列昂尼德·列文和理查德·卡普的研究工作。如今,它既为复杂性理论提供了数学基础,也提供了一个实用框架,帮助人们理解:为什么某些计算任务难以找到普遍适用的高效解法,却仍可采用有用的精确算法、近似方法,以及针对受限实例的算法。
形式化定义与计算基础
复杂性理论通常将判定问题表示为语言 ,其中 是有限字母表,而一个字符串属于 ,就表示它所编码的实例的答案为“是”。输入规模是这种编码的长度,不一定是问题中数值的大小,也不一定是问题所涉及的现实对象的数量。例如,图可以用邻接矩阵或边列表编码;整数可以用二进制或一进制表示。当这些编码方式的长度之间不存在多项式关系时,采用哪种编码就会影响复杂性分析。
P复杂度类由可用确定性图灵机在多项式时间内判定的语言组成。也就是说,存在某个常数 ,使得运行时间以 之类的量为上界,其中 是输入长度。NP复杂度类可以通过多项式时间验证来定义。如果存在确定性的多项式时间验证器 和多项式 ,使得下式成立,那么语言 就属于NP:
字符串 称为证书,也称见证。对于布尔可满足性问题,一个满足赋值就是一份证书:在该赋值下计算公式的值,所需时间是公式长度的多项式。验证器不必找到这个赋值,只需检查提供给它的赋值即可。对于答案为“否”的实例,任何长度在允许范围内的证书都不能使验证器接受。
等价地,NP是非确定性多项式时间图灵机所接受的语言构成的复杂度类。非确定性是一种数学模型:机器在每一步可能有多种后续选择,只要至少存在一条接受的计算路径,就判定为接受。它不是通常意义上的随机性,NP这两个字母也不代表“非多项式”。P中的每个问题都属于NP,因为多项式时间判定算法可以充当验证器,而完全忽略所提供的证书。
按照标准定义,当语言 满足两个条件时,就称其为NP完全的:,并且每个语言 都能通过多项式时间多对一归约归约到 。仅第二个条件就称为NP难性。NP难问题不一定属于NP,不一定是判定问题,甚至可能是不可判定的。相比之下,NP完全性始终要求答案为“是”的实例具有可在多项式时间内验证的证书。因此,标准的NP完全问题都是可判定的:仅通过穷举所有多项式长度的证书,就能得到一种有限的判定方法,尽管它通常需要指数时间。
多项式时间归约与完全性的含义
从语言 到语言 的多项式时间多对一归约,是一个可在多项式时间内计算的函数 ,满足
这一关系记作 。该函数将 的每个实例转换为 的一个实例,同时保持肯定答案和否定答案不变。如果 有高效的判定算法,那么求解 时,可以先计算 ,再运行该判定算法。
多项式时间这一要求在两个方面至关重要。首先,转换本身不能耗用归约原本要证明无法保证获得的计算资源。其次,转换的输出长度必须是多项式级的,因为多项式时间机器不可能显式写出长度为指数级的输出。这些条件确保,将归约与 的多项式时间算法复合后,得到的仍是 的多项式时间算法。
归约具有传递性。如果 且 ,那么 。这给出了证明一个新问题为 NP 完全问题的标准方法:通过描述适当的证书和验证器,证明该问题属于 NP;通过将一个已知的 NP 完全问题归约到这个新问题,证明其具有 NP 难性。这两部分在逻辑上相互独立:一个令人信服的难度证明构造,并不能自动证明该问题属于 NP。
归约的方向至关重要。要证明问题 很难,必须将一个已知很难的问题转换为 ,而不是反过来。从 到可满足性问题的归约,或许能说明可满足性问题的求解器也能用来求解 ,但仅凭这一点,并不能说明 是 NP 难的。许多容易的问题也能归约到可满足性问题。
此外还有其他归约概念。多项式时间图灵归约允许算法多次查询另一个问题的求解器,还可以根据先前的回答来决定后续查询。对数空间归约则对转换过程施加了更严格的资源限制。除非另有说明,NP 完全性通常指的是多项式时间多对一归约意义下的完全性。
完全性所确立的是多项式时间可解性层面的等价关系,而不是运行时间完全相同。将输入规模从 扩大到 的归约,虽然保持了多项式时间可解性,却可能大幅改变指数时间算法的实用价值。因此,标准理论并不意味着所有 NP 完全问题都具有相同的最优指数运行时间、实际求解难度或近似求解表现。
历史发展与库克—列文定理
NP 完全性的概念背景源于形式化计算模型和资源受限复杂性研究的发展。艾伦·图灵等研究者在 20 世纪 30 年代奠定了可计算性理论的基础。后续研究根据求解所需的时间和存储空间,对可计算问题作了进一步区分。到了 20 世纪 60 年代,多项式时间成为衡量计算是否切实可行的核心形式化标准,艾伦·科布汉姆和杰克·埃德蒙兹的工作在这方面尤为突出。
1971 年,斯蒂芬·库克发表了《定理证明过程的复杂性》,证明了如今构成库克—列文定理核心的结论。列昂尼德·列文在一个侧重搜索问题的框架中,独立得出了密切相关的完全性结果,并于 1973 年发表。按照如今通行的标准表述,该定理指出:布尔可满足性问题是 NP 完全的。
证明的核心构造是用布尔公式表示一个步数有界的计算过程。假设一台非确定性机器至多运行 步,其中 是多项式。它的计算过程可以用一张计算表来描述:一个轴表示时间,另一个轴表示纸带位置。布尔变量用于编码纸带符号、机器状态以及读写头的位置。由于在多项式步数内至多只能访问多项式数量的纸带单元,这张计算表的规模也是多项式级的。
构造中的约束确保四项要求得到满足:每个位置的描述都合法,第一行编码输入和初始配置,相邻两行遵循机器的转移规则,并且出现接受配置。转移规则具有局部性:一个单元的描述能否改变,仅取决于前一配置中一个范围有限的邻域。凭借这种局部性,这些约束可以表示为一个多项式规模的布尔公式。当且仅当机器存在一个接受计算过程时,该公式才可满足。
这一构造的意义在于其普遍性。这个公式并非针对某一项特定的组合任务设计,而是能够编码 NP 中任意问题的验证器或非确定性机器。因此,可满足性问题为整个 NP 类提供了一种共同的计算表示。
理查德·卡普于 1972 年发表的论文《组合问题之间的可归约性》拓展了这一方法,通过归约证明了 21 个问题的完全性。这些问题既包括图问题和集合问题,也包括整数规划以及与调度有关的问题表述。由此形成的归约网络表明,完全性是一种广泛存在的现象,而非逻辑公式所特有的性质。随后,迈克尔·加里和戴维·约翰逊于 1979 年出版的《计算机与难解性》系统整理了大量 NP 完全性研究成果,推动这一理论成为算法分析中的标准工具。
归约实例:从可满足性到团
一个经典例子展示了如何将逻辑问题转化为图问题。在3-可满足性问题(简称3-SAT)中,输入是一个合取范式的布尔公式,每个子句都包含三个文字。文字是一个变量或其否定。问题是:是否存在某种真值赋值,使每个子句都为真。一般的可满足性问题可以通过引入辅助变量归约为这种形式;所得公式与原公式具有相同的可满足性,而不需要进行指数规模的展开。
对于一个包含子句 的公式,构造一个无向图,为每个文字的每次出现各设置一个顶点。属于同一子句的顶点之间不连边。属于不同子句的两个顶点,当且仅当它们对应的文字不矛盾时才连边:标记为 的顶点与标记为 的顶点之间不连边。将目标团的大小设为 。团问题中的“团”是一个顶点集合,其中任意两个顶点之间都有边相连。
例如,考虑公式
构造出的图有九个顶点,同一文字的多次出现也分别对应不同的顶点。真值赋值 满足这个公式。从第一个子句中选取一次出现的 ,从第二个子句中选取 ,从第三个子句中选取 ,便得到三个两两相容的顶点,因此构成一个大小为三的团。
正确性证明分为两个方向。如果公式可满足,就从每个子句中选取一个为真的文字。任意两个选出的文字都不可能互相矛盾,因为它们在同一赋值下都为真。因此,它们对应的顶点两两相邻。反过来,一个大小为 的团必定从每个子句中恰好选取一个顶点,因为它不可能包含来自同一子句的两个顶点。选出的文字两两不矛盾,因此可以让它们同时为真,再将这一赋值扩展为对所有变量的完整赋值。这样,每个子句都包含一个选出的真文字。
对于一个3-SAT公式,这一构造会产生 个顶点,边数至多为二次量级。因此,该构造可以在多项式时间内完成。由于3-SAT是NP完全的,这一归约证明了团问题的NP难性。要证明团问题属于NP,只需检查给出的顶点是否互不相同、数量是否达到目标大小,以及所需的每条边是否都存在。
相关归约将这一构造与独立集和顶点覆盖联系起来。一个图中的团就是其补图中的独立集。在任意图中,一个顶点集合是独立集,当且仅当它的补集是顶点覆盖。这些关系可以传递判定问题的难度,但并不会自动以同样的方式保留近似保证。
代表性问题与精确表述的重要性
NP 完全问题广泛存在于图论、逻辑、调度和离散优化等领域。一个问题的复杂度分类取决于其确切的输入、约束条件以及所要回答的问题。在图着色中,判定任意给定图是否存在使用三种颜色的合法着色,是 NP 完全问题;而判定两种颜色是否足够,则可以在线性时间内完成。当颜色数量作为输入的一部分时,一般的图着色判定问题也是 NP 完全问题。
哈密顿回路问题询问一个图是否包含恰好访问每个顶点一次的回路。给出一个候选的顶点排列,就能提供一份可在多项式时间内核验的证书。旅行商问题有一种相关的判定形式:给定边的费用和界限 ,是否存在总费用不超过 的巡回路线?当整数或有理数费用采用适当的编码时,这一判定问题是 NP 完全问题。寻找费用最低的巡回路线则是优化问题,通常称其为 NP 难问题,而不称其为 NP 完全语言。
从它与最短路径问题的关系中,可以看出这种区别。在包括边权非负在内的常见假设下,求两个顶点之间的最短路径可以在多项式时间内完成。然而,如果要求一条简单路径访问每个顶点,问题就会发生根本变化。区别不在于一个问题涉及路线而另一个不涉及,而在于是否存在访问所有顶点这一全局约束。尽管有向无环图中的最长路径可以高效计算,但在一般图上,求最长简单路径的各种形式同样是困难的。
在整数规划中,变量必须取整数值。对于含有二元变量的一般约束系统,判定其是否存在可行解是 NP 完全问题,而变量取有理数值的线性规划则可以在多项式时间内求解。不过,如果将整数变量的个数固定,就存在运行时间关于输入长度为多项式的算法,但其对维数的依赖一般并非多项式。因此,结构上的限制可以使问题脱离一般情形下的困难范畴。
约束满足问题框架使这些区别得以系统化。变量从指定的取值域中取值,约束则限定允许的取值组合。允许使用的约束语言不同,就会产生不同的计算问题。布尔 2-SAT 可以在多项式时间内求解,而 3-SAT 是 NP 完全问题。对于有限取值域和固定的有限约束语言,安德烈·布拉托夫与德米特里·茹克于 2017 年分别独立证明的约束满足二分定理表明,每个此类问题要么可在多项式时间内求解,要么是 NP 完全问题。
这些例子说明,声称某个问题具有计算困难性时,必须指明一个形式化问题,而不能只笼统地指向某个应用领域。“调度是 NP 完全的”这一说法,遗漏了机器、作业时长、优先关系约束、是否允许抢占以及目标等关键信息。具体的调度问题可能是多项式时间可解的,也可能是弱 NP 完全或强 NP 完全的。
数值编码、伪多项式时间与强 NP 完全性
数值问题凸显了正确衡量输入长度的重要性。在子集和问题中,输入由非负整数 和目标值 组成,问题是能否从中选出一个子集,使其元素之和恰好等于 。一种标准的动态规划算法会记录不超过 的哪些总和可以达到。它的运行时间为 ,直接实现所需的存储空间为 。
这并不能证明,对于采用二进制编码的输入,该问题可以在多项式时间内求解。用二进制表示 只需要 位,因此 的数值可能相对于其表示长度呈指数级增长。如果一个算法的运行时间是数值大小的多项式,但不一定是其位长度的多项式,就称其为伪多项式时间算法。例如,循环十亿次,对于一个仅需约 30 个二进制位表示的数而言,可能只是关于该数数值的线性时间操作。
子集和问题及与之相关的划分问题,是弱 NP 完全数值问题的典型例子。当相关数值受到足够严格的限制,或采用一元编码表示时,它们的伪多项式时间算法就会成为多项式时间算法。在一元编码中,一个数由长度与其数值成正比的字符串表示。一般而言,从二进制编码转换为一元编码并不是多项式时间变换,因此在复杂性论证中,不能随意替换这两种编码。
强 NP 完全性刻画的是这样一种困难性:即使数值被限制在实例的组合规模的多项式范围内,困难性依然存在。对于标准的数值问题表述,相应的采用一元编码的问题仍然是 NP 完全的。这排除了这样一种解释:问题之所以困难,仅仅是因为二进制记数法能够紧凑地表示非常大的数。
一个核心例子是三划分问题(3-PARTITION)。其输入由 个正整数组成,总和为 ,且每个数均满足
问题是能否将这些数分成 个互不相交的组,使每组之和都为 。上述界限使得每组必须恰好包含三个整数。即使将数值限制在多项式范围内,该问题仍然是 NP 完全的,因此它尤其适合用于证明装箱和调度问题的强 NP 困难性。
这种区别会影响算法的设计与分析。假设 ,强 NP 完全的数值问题就不可能具有上述类型的伪多项式时间算法,因为在那些数值有界、且已足以确立 NP 困难性的实例上,这样的算法将成为多项式时间算法。相比之下,伪多项式时间算法往往能为弱 NP 完全问题提供实用的精确求解方法,有时还能转化为近似方案。因此,编码分析并非只是形式上的细节核算;它能够揭示哪些数值参数会使算法具有实际可行性。
精确算法与实际计算
NP 完全性是一种针对最坏情况的分类,并不意味着每个实例都需要大量计算。在假设 的前提下,不存在能求解某个 NP 完全问题所有实例的多项式时间算法。但这并不意味着每个实例都很难、每种输入分布在平均意义下都很难,或指数时间方法在实际规模下毫无用处。实例的结构、常数因子、预处理以及所需的输出,都可能成为决定实际性能的主要因素。
精确算法往往能比朴素枚举取得显著改进。对于一个含有 个变量的布尔公式,直接的算法会检查全部 种赋值。更精巧的方法则会剪去这一搜索空间中的大部分区域。在可满足性求解中,1962 年提出的戴维斯–普特南–洛格曼–洛夫兰过程将分支搜索与单元传播等化简规则相结合。现代冲突驱动子句学习求解器会分析失败的搜索路径,推导出能够排除类似失败情况的子句,并采用变量选择策略和重启机制。
对于优化问题,分支定界法会维护迄今找到的最佳可行解,并为尚未探索的子问题所能达到的解的质量确定界限。如果某个子问题不可能改进当前最优解,就将其舍弃。整数规划求解器将这类搜索与线性规划松弛、割平面、预求解变换以及专门的启发式方法相结合。这些方法并未消除最坏情况下的困难性,却能求解规模远超无结构穷举搜索处理能力的实例。
运行时间界也揭示了同属 NP 完全这一标签所掩盖的差异。赫尔德–卡普动态规划算法能在 时间内求解旅行商问题,远优于枚举顶点的所有排列。用于子集和问题的折半搜索算法将输入分为两组,再组合两组的子集和;忽略多项式因子及依赖具体实现的权衡,其运行时间约为 。这类改进可以显著扩大可处理的输入规模。
形式验证、电子设计自动化和规划等领域的应用,往往会产生具有丰富内部结构的可满足性实例。重复的子电路、受限的交互关系以及较强的传播能力,会使这些实例不同于为最坏情况构造的实例。反过来,规模虽小但结构经过精心设计的实例,也可能难倒原本表现出色的求解器。在所有问题表述中,并不存在一个能统一划分容易实例与困难实例的规模阈值。
另一个区别在于如何为无解提供证书。满足赋值是证明公式可满足的简短证书,但不可满足的公式没有可供展示的满足赋值。求解器可以转而生成能够独立核查的不可满足性证明。这类证明的大小取决于证明系统和具体实例;可满足性问题属于 NP,并不保证每个不可满足的公式都有多项式大小的证明。
近似求解与通常意义下NP完全性的局限
许多应用追求的是较好的可行解,而非精确的最优解。近似算法为其输出与最优值之间的关系提供数学保证。对于最小化问题,近似比为 的算法返回的解,其代价至多为最优值的 倍,通常有 。对于最大化问题,这种保证通常表述为:返回的解值至少为最优值除以 。
通常意义下的NP完全性并不能决定问题的可近似性。两个NP难的优化问题,其近似求解的表现可能大不相同。最小顶点覆盖问题有一个简单的2倍近似算法:先找出一个极大匹配,再选取所有匹配边的两个端点。这些端点覆盖了每一条边,否则就可以用某条未被覆盖的边扩充该匹配。任何顶点覆盖都必须包含每条匹配边的至少一个端点,因此,算法返回的顶点覆盖大小至多为最优值的两倍。
在度量旅行商问题中,代价具有对称性、非负性,并满足三角不等式。该问题有克里斯托菲德斯于1976年提出的近似比为 的算法。其基本结构是将最小生成树、奇数度顶点上的最小权匹配,以及对欧拉遍历的捷径化处理结合起来。相比之下,如果没有度量假设,那么任何具有固定常数近似比的多项式时间近似算法都将意味着 。这些问题的判定版本仍然是NP完全的,但额外的几何或度量结构改变了高效近似计算所能达到的效果。
PCP定理在20世纪90年代为证明近似求解的局限奠定了重要基础。该定理的一种标准表述通过证明验证器来刻画NP:验证器使用对数数量的随机位,并且只检查常数个证明位。尽管验证器检查的内容极其有限,完备性和可靠性条件仍使其能够区分真命题与假命题。
通过适当的归约,这种证明检验的视角可以导出间隙问题:是实例存在解的质量高于某一阈值,而否实例则不存在解的质量高于另一个更低的阈值。如果某个近似算法强到足以跨越这一间隙,就能用它判定一个NP完全问题。这类保持间隙的归约,比仅保持精确可行性的归约要求更高。
近似方案又带来了另一层区分。多项式时间近似方案对于每个固定的精度参数 ,运行时间都是多项式的;而完全多项式时间近似方案的运行时间则同时是输入长度和 的多项式。标准的0–1背包优化问题存在后一种方案。在一些额外的标准条件下,包括整数目标值具有适当的界限,强NP难性通常可以排除这类方案的存在,除非 。因此,精确求解的难度、近似比,以及运行时间对精度的依赖,都需要分别分析。
参数化复杂度与更精细的运行时间假设
参数化复杂度同时根据输入总长度 和选定的结构参数 来研究运行时间。如果一个问题可以在如下时间内求解,就称其为固定参数可解的:
其中,多项式的指数与 无关。函数 可以增长得很快。这一框架将实例中难以处理但规模较小的特征,与可能很大的整体规模区分开来。
顶点覆盖是一个基本例子。对于一条尚未被覆盖的边 ,任何顶点覆盖都必须包含 或 。针对这两种选择进行分支搜索,并相应减少剩余可选顶点数,就能得到运行时间为 的算法。因此,即使图的顶点很多,只要已知它仅需一个较小的顶点覆盖,求解仍可能是可行的。这与 NP 完全性并不矛盾,因为 可以随输入规模增长。
预处理也可以通过核化进行形式化分析:在多项式时间内,将实例 转换为一个等价实例,且后者的总大小由 的某个函数所界定。借助基于线性规划的构造,顶点覆盖问题可以得到至多包含 个顶点的核。对于其他一些问题,目前尚无已知的类似压缩方法;而在比仅仅假设 更强的假设下,条件性下界可以排除多项式大小的核。
另一个重要参数是树宽,它衡量一个图在多大程度上可以分解成彼此重叠、按树状结构组织的部分。对于许多 NP 完全图问题,给定树分解后,就可以通过动态规划求解,其运行时间对分解的宽度呈指数依赖,而对图的大小呈多项式依赖。这解释了为什么稀疏、具有局部组织结构的实例可能比任意实例更容易求解。不过,仅有稀疏性并不能保证树宽较小,也不能保证问题易解。
参数化困难性用于区分哪些情形不太可能存在这样的算法。以目标团的大小为参数时,团问题是 W[1] 类的完全问题。通过枚举检查顶点子集,可以得到形如 的算法,但它并不是固定参数算法,因为其多项式指数依赖于 。固定参数可解类是否等于 W[1],目前仍未解决。
细粒度假设提出了比 更强的计算能力限制。指数时间假设的一种标准表述断言:若以变量数为 ,则 3-SAT 不存在运行时间为 的算法。强指数时间假设则指出,随着子句宽度增大,不可能始终将可满足性问题求解时间的指数底数从穷举搜索的 降低一个固定的幅度。通过在归约中精细控制实例大小,可以利用这些假设来论证具体的运行时间下界,而普通的 NP 完全性无法给出这样的下界。
与其他复杂度类的关系及未决问题
最核心的未决问题仍然是是否有 。如果任何一个NP完全语言属于P,那么由归约的传递性可得 。反之,如果 ,则没有任何NP完全语言属于P。NP完全性本身并不能证明其中任何一种情况。即使几十年来接连尝试的算法思路都失败了,也不能据此证明复杂度下界。
补复杂度类 coNP复杂度类 由NP中各语言的补语言组成。不可满足性问题是coNP完全的:其肯定实例是不存在满足赋值的公式。目前尚不清楚是否有 。如果某个NP完全问题属于coNP,那么NP与coNP就会相同。P与NP相等会推出NP与coNP相等,但目前并不知道NP与coNP相等是否能推出 。
完全性并不意味着NP中的每个问题都必定要么容易求解,要么是NP完全的。1975年证明的拉德纳定理指出,如果 ,那么NP中存在既不属于P、也不是多项式时间多对一归约意义下的NP完全语言。这样的语言称为NP中间语言。整数分解和图同构经常被作为尚未确定具有NP完全性的自然问题来讨论,但目前也都未被证明不属于P。整数分解通常表述为函数问题,因此,在将其与判定语言进行比较时需要谨慎。
计数提出了一种不同的任务。判断布尔公式是否存在满足赋值是判定问题;而确定它有多少个满足赋值,在标准计数归约下则是计数复杂度类#P的完全问题。因此,#P完全性理论涉及的信息比简单的是非答案更多。虽然精确的计数结果可以立即确定解是否存在,但通常的NP完全性定义并未给出反方向的推导。
与密码学的联系同样需要谨慎看待。公钥密码学依赖于一些具体假设:能够高效生成对攻击者而言仍然难以求解的实例,而不只是存在最坏情况下的NP完全问题。目前尚不知道仅凭 这一假设能否推出单向函数的存在。反过来, 会使许多解可被高效验证的搜索任务能够在多项式时间内求解,从而动摇标准计算密码学的基础。
目前尚不知道量子计算机能否在多项式时间内求解NP完全问题。肖尔针对整数分解和离散对数提出的多项式时间算法并不能确立这一结论,因为这些问题尚未被证明是NP完全的。通用量子搜索相较于无结构的经典搜索可以实现平方级加速,但当搜索空间呈指数增长时,其运行时间仍然是指数级的。
试图解决这些问题的研究还受到一些重大障碍的制约。相对化结果表明,某些证明方法无法解决P与NP是否相等的问题,因为在适当构造的不同预言机世界中,可以分别得到相反的答案。亚历山大·拉兹博罗夫和史蒂文·鲁迪奇提出的自然证明框架指出,在密码学假设成立的条件下,一大类电路下界论证会面临障碍。这些结果限制的是特定的研究方法,并不意味着相关问题本身无法解决。