引言

在针对组合优化问题设计算法时，了解问题的复杂度是很有意义的。本篇推文主要介绍什么是大家耳熟能详的P类问题，NP类问题，NP完备问题以及NP难问题。

我们将介绍与组合优化问题的复杂度相关的定义以及证明一个组合优化问题的复杂度的步骤。最后，给出背包问题(Knapsack Problem，KP)和旅行商问题(Traveling Salesman Problem，TSP)的复杂度的证明过程。

在学习P类问题和NP类问题的定义之前，我们需要了解一些相关的基本概念，其中最重要的是判定问题，确定性算法以及不确定性算法的概念。而在证明一个组合优化问题的复杂度之前，我们则需要了解什么是多项式归约(polynomial transformation)。若想证明一个组合优化问题是强NP难，则需要进一步了解什么是伪多项式归约(pseudo-polynomial transformation)。

基本概念及定义

组合优化问题的定义

组合优化问题的可行解的个数是有限的，有一个目标函数用来衡量解的质量并且有一个明确的优化方向(最大化/最小化)。

令S为一个组合优化问题的可行解集合，f为一个组合优化问题的目标函数，则对于一个组合优化问题有

例：背包问题，旅行商问题，板材切割问题等等都是组合优化问题

问题的参数(parameter)和算例(instance)

参数是描述问题所需的常量的集合，而算例就是给问题参数明确的赋值。

在这里，我们给出两个组合优化问题的描述及其数学表达：

背包问题

问题描述

给定:
待装包物品集合
待装包物品的效用值v_i
待装包物品的重量w_i
背包容量B

约束:

装包物品的重量之和不超过背包容量

目标:

寻找一个装包方案，使得所装物品的效用值之和最大

数学模型

变量：

数学表达：

旅行商问题

问题描述

给定:

无向图G=(V,E,d) 。其中，V是顶点集合，V=|m|，E则是边集合, d是顶点之间的距离矩阵。

注意：旅行商问题的无向图G是一个完全图。

约束:

每个顶点必须被访问一次

目标:

寻找一条路径，使得总路程长度最短

数学模型

变量：

数学表达 (single commodity formulation)：

解集规模和输入规模的关系

在组合优化问题的参数确定之后，问题的输入规模与解的个数之间的关系是可以确定的。例如，

背包问题

令待装包物品的个数为m，每个物品都可以选择装包与否，那么所有可能(包含可行与不可行)的装包方案就有2^m个。

也就是说，背包问题的解集的规模与问题的输入规模是指数级的关系。

旅行商问题

令需要访问的城市个数为m，旅行商问题的任意一个可行解可以用一个包含m个元素的序列来表示。序列的第一个元素在m个城市中选择，序列的第二个元素在m-1个城市中选择，依此类推，那么一共有m!个不同的序列(可行路径)。

也就是说，旅行商问题的可行解集的规模与问题的输入规模是阶乘级的关系。

从解集规模的增长率也能感觉到，旅行商问题的复杂度是高于背包问题的复杂度的，在下文中也会证明，背包问题是NP难问题(NP-hard)，而旅行商问题是强 NP难问题(NP-hard in strong sense，或称 strongly NP-hard)。

判定问题

在判定问题中，在确定输入参数之后，问题的答案以“是”或“否”的形式返回。简单来说，判定问题就是是非题。

例如：给定一个有m个元素的数组，问：数组中是否存在素数？

确定性算法和不确定性算法

确定性算法(deterministic algorithm)拥有一个明确的算法流程。若输入的算例相同，则算法返回的结果永远相同。

例如：冒泡排序(bubble sort)就是一个确定性的排序算法

不确定性算法(non-deterministic algorithm)的算法流程不明确。在算法的某些节点有多种后续可能(即有随机性，例如元启发式算法中常用的 roulette wheel selection)。即使输入算例相同，算法返回的结果可能会不同。

例如：盲猜一个问题的解也4是一个不确定性算法，俗称“瞎蒙”。

P类问题和NP类问题

在P类问题中，都是可以通过确定性算法在多项式时间内求解的判定问题

(P代表的是 polynomial 的首字母)。

例如：给定一个有m个元素的数组，问：数组中是否有比100大的数？

在NP类问题中，都是可以通过不确定性算法在多项式时间内得到一个解并在多项式时间内验证这个解是否可行的判定问题

( NP代表的是 non-deterministic polynomial 的首字母组合)。

P类问题和NP类问题的关系

目前认为，, 也就是说，任意一个可以在多项式时间内用确定性算法求解的判定问题，也可以在多项式时间内用不确定性算法得到一个解并在多项式时间内验证这个解是否可行。

目前仍然存在许多属于NP类的问题，我们不确定这些问题是否也属于P类问题，因为目前还没有找到确定性算法可以在多项式时间内求解这些判定问题。

在目前假设P≠NP的前提下，这两类问题的关系图如下：

多项式归约(polynomial transformation)

假设有和 两个判定问题，如果存在一个确定性的关于输入规模的多项式时间算法f，可以将任意一个的算例I构造成一个的算例I'=f(I)，并且使得， 在输入算例I后判定为“是”，当且仅当在输入算例I'后判定也为“是”，则称可以在多项式时间内归约到。

如果可以在多项式时间内转化(归约)到，记作 。并且可以说，** 至少和一样难**。

另外，多项式归约存在传递性，也就是说，如果且则有 。

NP完备问题(NP-complete,NPC )

定义

如果一个判定问题属于NP类问题且对任意一个判定问题满足:，则称判定问题是NP完备问题。

Note：NP完备问题俗称是NP类问题中最难的问题。

证明方法

若要证明一个判定问题是NP完备的，在实践中通常使用下列步骤：

1.证明

2.选择一个适合的NP完备问题

3.证明存在多项式归约，使得

因为多项式归约具有传递性，所以这三步用来证明已经足够了。

下面介绍一个经典的NP完备问题，这个问题在之后的证明过程中也会用到：

二分区问题(Partition Problem，PP)

问题描述

给定一个物品集合

给每个物品分配一个整数值a_j

判定：

是否存在一个集合，使得

伪多项式归约 (pseudo-polynomial transformation)

假设有和两个判定问题，那么我们说f是将转化成的伪多项式归约，如果：

1. 可以将任意一个的算例I构造成一个的算例I'=f(I)，并且使得在输入算例I后判定为“是”，当且仅当在输入算例I'后判定也为“是”。
2. f可以在关于max[I]和length[I]的多项式时间内完成 (f can be computed in time polynomial in the two variables max[I] and length[I] )，其中max[I]是的算例I中最大的数值，length[I]是的算例I的长度(输入的长度，体现的是算例的规模)。
3. 存在一个多项式q₁，使得对任意一个的算例I都满足：

     4. 存在一个多项式 ，使得对任意一个 的算例 都满足：

强NP完备问题(NP-complete in strong sense/strongly NP-complete)

强 NP完备问题是NP完备问题的 special case。

定义

设有一个判定问题， I是问题的算例，另外有一个判定问题， I'是问题的算例，还有一个多项式p，使得max[I']≤p(length[I])。若问题是NP完备问题，那么就说是强NP完备问题。

(A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input.)

证明方法

若要证明一个判定问题是强NP完备的，通常使用下列步骤：

1.证明

2.选择一个适合的强NP完备问题

3.证明存在伪多项式归约，将转化成

下面介绍两个经典的强NP完备问题：

汉密尔顿圈问题(Hamilton Circuit Problem，HCP)

问题描述

给定一个无向图G'=(V',E') ，其中， V'是顶点集合，|V'|=n， E'则是边集合

注意：该无向图G'往往不是一个完全图。

判定:

是否存在一个汉密尔顿圈，即一条经过所有顶点恰好一次的闭路径。

三分区问题(3 Partition Problem，3-PP)

问题描述

给定一个物品集合U={1,2,......,3k}

给定一个整数B

给每个物品分配一个整数值a_j，使得且

判定:

是否可以将集合u划分成k个互无交集的集合，使得 .

NP难问题和强NP难问题

之前介绍的NP完备问题的概念是针对判定问题来说的，而NP难问题则是针对组合优化问题来说的。

通俗来说，如果一个组合优化问题所对应的判定问题是NP完备问题，那么这个组合优化问题就是NP难问题；如果一个组合优化问题所对应的判定问题是强NP完备问题，那么这个组合优化问题就是强NP难问题。

在下一节中，我们来详细看一下，如何证明组合优化问题的复杂度，选取背包问题和旅行商问题作为我们的case。

证明组合优化问题的复杂度

在这一节中，我们看一下背包问题以及旅行商问题的复杂度证明过程。

证明过程中所用的数学符号在上文中都定义过，具体的符号含义请参照上文介绍过的模型，这里就不再赘述了。

在证明过程中，需要用到(伪)多项式归约。因此，需要先将背包问题以及旅行商问题转换成各自对应的判定问题(也就是把组合优化问题转化成判定问题)。

背包问题

背包问题的目标是最大化所装物品的效用值，在转化成判定问题时，则改为 “是否存在一个装包方案，使得所装物品的效用值之和不小于常数C?”。也就是说，在将背包问题转化成其对应的判定问题时，多了一个参数C，背包问题的判定问题我们称之为。

证明过程

证明使用多项式规约的方式

1.背包问题的判定问题是NP类问题，因为我们可以在(算例规模，这里为m的)多项式时间内给出一个解，并在多项式时间内验证这个解。

2.选择一个合适的NP完备问题。此处选择二分区问题(平分问题，Partition Problem，PP)。

3.使用PP算例中的参数完成对算例的归约

背包问题的判定问题( )的算例参数:

 

详解：

可以看到，归约之后的参数全都是由二分区问题中的参数构成的。

在此算例下，

且

等价于

也就是说，在此算例设计下，若的判定为“是”，那么PP的判定也为“是”，反之亦然。

上表的算例转化(归约)可以在多项式时间内完成，因此，也就是说，背包问题的判定问题() 至少和二分区问题一样难。

得证，背包问题的判定问题 (即 ) 是NP-完备问题，所以背包问题是NP-难问题。

旅行商问题

旅行商问题的目标是最小化路程总长度，在转化成判定问题时，则可以改为 “是否存在一条经过所有顶点恰好一次的路径，其路程总长度不大于常数C?”。也就是说，在将旅行商问题转化成其对应的判定问题时，多了一个参数C，旅行商问题的判定问题我们称之为。

证明过程

证明首先使用多项式规约的方式

1.旅行商问题的判定问题是NP类问题，因为我们可以在(算例规模，这里为m的)多项式时间内给出一个解，并在多项式时间内验证这个解

2.选择一个合适的NP-完备问题，此处选择汉密尔顿圈问题(Hamilton Circuit Problem，HCP)

3.使用HCP算例中的参数完成对算例的归约

旅行商问题的判定问题( )的算例参数:

m=n

C=n

设m=n，意味着无向图G与G'的点集是相同的 (V=V')。

在HCP中，是不考虑顶点间的距离的。在相应的中，根据HCP的算例，对距离矩阵d做如下赋值操作：

详解

因为中的无向图G是一个完全图，而HCP中的无向图G'未必是一个完全图，所以有。当边[i,j]存在于无向图G'中时，将d_ij(从顶点到顶点的距离)设为1。若边[i,j]是在无向图G中通过补全得到的，则将d_ij设为2。

下图为一个HCP中的无向图G'：

下图则为对应的中的无向图G：

在此算例设计下，尝试在中的无向图G中寻找一条经过所有顶点恰好一次且总路程长度不超过n的路径(若路径总长度为n，则说明路径中只包含无向图G'中存在的边)。

若上述问题的回答为”是“，即的判定为”是“，那么HCP的判定也为”是“，即在无向图G中存在一个汉密尔顿圈，反之亦然。

其实，汉密尔顿圈问题不仅是个NP完备问题，也是一个强NP完备问题 (注：不带数值的NP完备问题是强NP完备问题)。

事实上，上述的算例转化是伪多项式归约，因为：

1.上述的转化步骤可以在n的多项式时间内完成

2.length(G)≥length(G')是满足的，因为G是在G'的基础上补全的

3.我们有：,即完全图G中边的个数。

因此，必定满足

得证，旅行商问题的判定问题(即) 是强NP-完备问题， 所以旅行商问题是强NP-难问题。

参考文献

1.Garey, M. R.; Johnson, D. S. (July 1978). "'Strong' NP-Completeness Results: Motivation, Examples, and Implications". Journal of the Association for Computing Machinery. New York, NY: ACM. 25 (3): 499–508. doi:10.1145/322077.322090. ISSN 0004-5411. MR 0478747. S2CID 18371269

2.Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.

---

本文转载自微信公众号：运小筹

引言

在针对组合优化问题设计算法时，了解问题的复杂度是很有意义的。本篇推文主要介绍什么是大家耳熟能详的P类问题，NP类问题，NP完备问题以及NP难问题。

我们将介绍与组合优化问题的复杂度相关的定义以及证明一个组合优化问题的复杂度的步骤。最后，给出背包问题(Knapsack Problem，KP)和旅行商问题(Traveling Salesman Problem，TSP)的复杂度的证明过程。

在学习P类问题和NP类问题的定义之前，我们需要了解一些相关的基本概念，其中最重要的是判定问题，确定性算法以及不确定性算法的概念。而在证明一个组合优化问题的复杂度之前，我们则需要了解什么是多项式归约(polynomial transformation)。若想证明一个组合优化问题是强NP难，则需要进一步了解什么是伪多项式归约(pseudo-polynomial transformation)。

基本概念及定义

组合优化问题的定义

组合优化问题的可行解的个数是有限的，有一个目标函数用来衡量解的质量并且有一个明确的优化方向(最大化/最小化)。

令S为一个组合优化问题的可行解集合，f为一个组合优化问题的目标函数，则对于一个组合优化问题有

例：背包问题，旅行商问题，板材切割问题等等都是组合优化问题

问题的参数(parameter)和算例(instance)

参数是描述问题所需的常量的集合，而算例就是给问题参数明确的赋值。

在这里，我们给出两个组合优化问题的描述及其数学表达：

背包问题

问题描述

给定:
待装包物品集合
待装包物品的效用值v_i
待装包物品的重量w_i
背包容量B

约束:

装包物品的重量之和不超过背包容量

目标:

寻找一个装包方案，使得所装物品的效用值之和最大

数学模型

变量：

数学表达：

旅行商问题

问题描述

给定:

无向图G=(V,E,d) 。其中，V是顶点集合，V=|m|，E则是边集合, d是顶点之间的距离矩阵。

注意：旅行商问题的无向图G是一个完全图。

约束:

每个顶点必须被访问一次

目标:

寻找一条路径，使得总路程长度最短

数学模型

变量：

数学表达 (single commodity formulation)：

解集规模和输入规模的关系

在组合优化问题的参数确定之后，问题的输入规模与解的个数之间的关系是可以确定的。例如，

背包问题

令待装包物品的个数为m，每个物品都可以选择装包与否，那么所有可能(包含可行与不可行)的装包方案就有2^m个。

也就是说，背包问题的解集的规模与问题的输入规模是指数级的关系。

旅行商问题

令需要访问的城市个数为m，旅行商问题的任意一个可行解可以用一个包含m个元素的序列来表示。序列的第一个元素在m个城市中选择，序列的第二个元素在m-1个城市中选择，依此类推，那么一共有m!个不同的序列(可行路径)。

也就是说，旅行商问题的可行解集的规模与问题的输入规模是阶乘级的关系。

从解集规模的增长率也能感觉到，旅行商问题的复杂度是高于背包问题的复杂度的，在下文中也会证明，背包问题是NP难问题(NP-hard)，而旅行商问题是强 NP难问题(NP-hard in strong sense，或称 strongly NP-hard)。

判定问题

在判定问题中，在确定输入参数之后，问题的答案以“是”或“否”的形式返回。简单来说，判定问题就是是非题。

例如：给定一个有m个元素的数组，问：数组中是否存在素数？

确定性算法和不确定性算法

确定性算法(deterministic algorithm)拥有一个明确的算法流程。若输入的算例相同，则算法返回的结果永远相同。

例如：冒泡排序(bubble sort)就是一个确定性的排序算法

不确定性算法(non-deterministic algorithm)的算法流程不明确。在算法的某些节点有多种后续可能(即有随机性，例如元启发式算法中常用的 roulette wheel selection)。即使输入算例相同，算法返回的结果可能会不同。

例如：盲猜一个问题的解也4是一个不确定性算法，俗称“瞎蒙”。

P类问题和NP类问题

在P类问题中，都是可以通过确定性算法在多项式时间内求解的判定问题

(P代表的是 polynomial 的首字母)。

例如：给定一个有m个元素的数组，问：数组中是否有比100大的数？

在NP类问题中，都是可以通过不确定性算法在多项式时间内得到一个解并在多项式时间内验证这个解是否可行的判定问题

( NP代表的是 non-deterministic polynomial 的首字母组合)。

P类问题和NP类问题的关系

目前认为，, 也就是说，任意一个可以在多项式时间内用确定性算法求解的判定问题，也可以在多项式时间内用不确定性算法得到一个解并在多项式时间内验证这个解是否可行。

目前仍然存在许多属于NP类的问题，我们不确定这些问题是否也属于P类问题，因为目前还没有找到确定性算法可以在多项式时间内求解这些判定问题。

在目前假设P≠NP的前提下，这两类问题的关系图如下：

多项式归约(polynomial transformation)

假设有和 两个判定问题，如果存在一个确定性的关于输入规模的多项式时间算法f，可以将任意一个的算例I构造成一个的算例I'=f(I)，并且使得， 在输入算例I后判定为“是”，当且仅当在输入算例I'后判定也为“是”，则称可以在多项式时间内归约到。

如果可以在多项式时间内转化(归约)到，记作 。并且可以说，** 至少和一样难**。

另外，多项式归约存在传递性，也就是说，如果且则有 。

NP完备问题(NP-complete,NPC )

定义

如果一个判定问题属于NP类问题且对任意一个判定问题满足:，则称判定问题是NP完备问题。

Note：NP完备问题俗称是NP类问题中最难的问题。

证明方法

若要证明一个判定问题是NP完备的，在实践中通常使用下列步骤：

1.证明

2.选择一个适合的NP完备问题

3.证明存在多项式归约，使得

因为多项式归约具有传递性，所以这三步用来证明已经足够了。

下面介绍一个经典的NP完备问题，这个问题在之后的证明过程中也会用到：

二分区问题(Partition Problem，PP)

问题描述

给定一个物品集合

给每个物品分配一个整数值a_j

判定：

是否存在一个集合，使得

伪多项式归约 (pseudo-polynomial transformation)

假设有和两个判定问题，那么我们说f是将转化成的伪多项式归约，如果：

1. 可以将任意一个的算例I构造成一个的算例I'=f(I)，并且使得在输入算例I后判定为“是”，当且仅当在输入算例I'后判定也为“是”。
2. f可以在关于max[I]和length[I]的多项式时间内完成 (f can be computed in time polynomial in the two variables max[I] and length[I] )，其中max[I]是的算例I中最大的数值，length[I]是的算例I的长度(输入的长度，体现的是算例的规模)。
3. 存在一个多项式q₁，使得对任意一个的算例I都满足：

     4. 存在一个多项式 ，使得对任意一个 的算例 都满足：

强NP完备问题(NP-complete in strong sense/strongly NP-complete)

强 NP完备问题是NP完备问题的 special case。

定义

设有一个判定问题， I是问题的算例，另外有一个判定问题， I'是问题的算例，还有一个多项式p，使得max[I']≤p(length[I])。若问题是NP完备问题，那么就说是强NP完备问题。

(A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input.)

证明方法

若要证明一个判定问题是强NP完备的，通常使用下列步骤：

1.证明

2.选择一个适合的强NP完备问题

3.证明存在伪多项式归约，将转化成

下面介绍两个经典的强NP完备问题：

汉密尔顿圈问题(Hamilton Circuit Problem，HCP)

问题描述

给定一个无向图G'=(V',E') ，其中， V'是顶点集合，|V'|=n， E'则是边集合

注意：该无向图G'往往不是一个完全图。

判定:

是否存在一个汉密尔顿圈，即一条经过所有顶点恰好一次的闭路径。

三分区问题(3 Partition Problem，3-PP)

问题描述

给定一个物品集合U={1,2,......,3k}

给定一个整数B

给每个物品分配一个整数值a_j，使得且

判定:

是否可以将集合u划分成k个互无交集的集合，使得 .

NP难问题和强NP难问题

之前介绍的NP完备问题的概念是针对判定问题来说的，而NP难问题则是针对组合优化问题来说的。

通俗来说，如果一个组合优化问题所对应的判定问题是NP完备问题，那么这个组合优化问题就是NP难问题；如果一个组合优化问题所对应的判定问题是强NP完备问题，那么这个组合优化问题就是强NP难问题。

在下一节中，我们来详细看一下，如何证明组合优化问题的复杂度，选取背包问题和旅行商问题作为我们的case。

证明组合优化问题的复杂度

在这一节中，我们看一下背包问题以及旅行商问题的复杂度证明过程。

证明过程中所用的数学符号在上文中都定义过，具体的符号含义请参照上文介绍过的模型，这里就不再赘述了。

在证明过程中，需要用到(伪)多项式归约。因此，需要先将背包问题以及旅行商问题转换成各自对应的判定问题(也就是把组合优化问题转化成判定问题)。

背包问题

背包问题的目标是最大化所装物品的效用值，在转化成判定问题时，则改为 “是否存在一个装包方案，使得所装物品的效用值之和不小于常数C?”。也就是说，在将背包问题转化成其对应的判定问题时，多了一个参数C，背包问题的判定问题我们称之为。

证明过程

证明使用多项式规约的方式

1.背包问题的判定问题是NP类问题，因为我们可以在(算例规模，这里为m的)多项式时间内给出一个解，并在多项式时间内验证这个解。

2.选择一个合适的NP完备问题。此处选择二分区问题(平分问题，Partition Problem，PP)。

3.使用PP算例中的参数完成对算例的归约

背包问题的判定问题( )的算例参数:

 

详解：

可以看到，归约之后的参数全都是由二分区问题中的参数构成的。

在此算例下，

且

等价于

也就是说，在此算例设计下，若的判定为“是”，那么PP的判定也为“是”，反之亦然。

上表的算例转化(归约)可以在多项式时间内完成，因此，也就是说，背包问题的判定问题() 至少和二分区问题一样难。

得证，背包问题的判定问题 (即 ) 是NP-完备问题，所以背包问题是NP-难问题。

旅行商问题

旅行商问题的目标是最小化路程总长度，在转化成判定问题时，则可以改为 “是否存在一条经过所有顶点恰好一次的路径，其路程总长度不大于常数C?”。也就是说，在将旅行商问题转化成其对应的判定问题时，多了一个参数C，旅行商问题的判定问题我们称之为。

证明过程

证明首先使用多项式规约的方式

1.旅行商问题的判定问题是NP类问题，因为我们可以在(算例规模，这里为m的)多项式时间内给出一个解，并在多项式时间内验证这个解

2.选择一个合适的NP-完备问题，此处选择汉密尔顿圈问题(Hamilton Circuit Problem，HCP)

3.使用HCP算例中的参数完成对算例的归约

旅行商问题的判定问题( )的算例参数:

m=n

C=n

设m=n，意味着无向图G与G'的点集是相同的 (V=V')。

在HCP中，是不考虑顶点间的距离的。在相应的中，根据HCP的算例，对距离矩阵d做如下赋值操作：

详解

因为中的无向图G是一个完全图，而HCP中的无向图G'未必是一个完全图，所以有。当边[i,j]存在于无向图G'中时，将d_ij(从顶点到顶点的距离)设为1。若边[i,j]是在无向图G中通过补全得到的，则将d_ij设为2。

下图为一个HCP中的无向图G'：

下图则为对应的中的无向图G：

在此算例设计下，尝试在中的无向图G中寻找一条经过所有顶点恰好一次且总路程长度不超过n的路径(若路径总长度为n，则说明路径中只包含无向图G'中存在的边)。

若上述问题的回答为”是“，即的判定为”是“，那么HCP的判定也为”是“，即在无向图G中存在一个汉密尔顿圈，反之亦然。

其实，汉密尔顿圈问题不仅是个NP完备问题，也是一个强NP完备问题 (注：不带数值的NP完备问题是强NP完备问题)。

事实上，上述的算例转化是伪多项式归约，因为：

1.上述的转化步骤可以在n的多项式时间内完成

2.length(G)≥length(G')是满足的，因为G是在G'的基础上补全的

3.我们有：,即完全图G中边的个数。

因此，必定满足

得证，旅行商问题的判定问题(即) 是强NP-完备问题， 所以旅行商问题是强NP-难问题。

参考文献

1.Garey, M. R.; Johnson, D. S. (July 1978). "'Strong' NP-Completeness Results: Motivation, Examples, and Implications". Journal of the Association for Computing Machinery. New York, NY: ACM. 25 (3): 499–508. doi:10.1145/322077.322090. ISSN 0004-5411. MR 0478747. S2CID 18371269

2.Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.

---

本文转载自微信公众号：运小筹