概述

迄今为止，几乎大部分算法都是多项式时间算法，也就是对于规模为n的输入，在最坏情况下的运行时间为O（n^k），其中k为某个常数，然而并不是所有的问题都能在多项式时间内解决，如著名的“停机问题”。

“NP完全”（NP-complete）问题的状态是未知的，既没有人找到这类问题的多项式时间算法，也没有人证明这类问题的多项式时间算法不存在。

一个NPC不一定是无法解决的，但是他的算法可能复杂度是O（2^n）等等，总之是无法在多项式时间内解决。

在本文档中介绍三类问题

• P：在多项式时间内可以解决的问题

• NP：在多项式时间内可以验证的问题，在问题输入的规模的多项式时间内，可以验证某一个结果是否是正确的（不难看出，P⊆NP）

• NPC：如果一个问题属于NP，并且与NP中的任何一个问题是一样难的，那么这个问题属于NPC，也就是说他是NP完全的

如果任何NPC问题可以在多项式时间内解决，那么每一个NPC问题都有一个多项式时间算法

在证明一个问题是NPC问题的时候，我们需要的证明方式往往是去陈述它是一个多么困难的问题，而不是去证明存在某个算法与否。

关键概念

判定问题与最优化问题

NPC并不适用于最优化问题，但适用于判定问题，尽管证明一个问题是NPC问题会将我们的目光局限于判定问题，但是在最优化问题和判定问题之间有很方便的联系。

当我们在证明某一个最优化问题是一个困难的问题的时候，我们可以利用这个问题所对应的判定问题，因为从某种意义上来讲，判定问题会容易一些，或者至少不会更难。

因此，加入我们能够提供证据表明某个判定问题是个困难问题的话，我们也提供了证据表明其相关的最优化问题也是困难的。

归约

对于一个判定问题A，我们希望在多项式时间内解决该问题，称这个问题的输入为该问题的一个实例，假设我们有另一个不同的判定问题B，我们知道如何在多项式时间内解决它，并且假设有一个过程，可以将A的任何实例转化成B的实例，并且这个转化的过程具有如下的性质：

• 转换操作需要多项式时间

• 两个实例的答案是相同的

那么我们称这个转化的过程为多项式时间的归约算法。因此可以将问题A的求解归约为B的求解（因为如果B的算法是多项式时间，转换过程为多项式时间，那么A也可以在多项式时间内解决）。

第一个NPC问题，电路可满足性问题，已知一个布尔组合电路，由AND，OR和NOT组成，我们希望知道这个电路是否存在一组布尔输入，使得电路的输出为1，检查这个电路是否是可满足的，除了尝试去测试每一组输入输出之外，没有别的好办法，而这样的办法的复杂度为O（2^n）

多项式时间

我们形式化的定义一下多项式时间可解问题，这些问题通常都被看作是容易处理的。

抽象问题

问了理解多项式时间可解问题，我们形式化定义“问题”这个概念：

• 定义抽象问题Q为在问题实例集合I和问题解法集合S上的一个二元关系

而为了简单起见，因为我们只讨论NPC问题中的判定问题，我们可以把抽象的判定问题看作是实例集I映射到解集{0，1}上的一个函数。如在一个最短路径问题中，我们的输入是一个实例i=，那么如果从u到v最短路径长度为k，则PATH（i）=1，否则PATH（i）=0

编码

使用计算机解决问题，任何多边形，图，函数，有序对都可以编码成二进制串。

我们把实例集为二进制串的集合的问题成为具体问题，如果一个问题实例的长度为n=|i|，算法可以在O（T（n））内产生问题的解，那么我们说算法在这个时间内解决了该问题。

因此，如果给定一个抽象判定问题Q，其映射为实例集合I到{0,1}，通过某种编码e：I->{0,1}可以导出与问题相关的具体判定问题。

通常情况下，编码的方式并不会影响问题的计算难度，然而在实践中并不是这样，我们需要假设采用标准编码的二进制串。

形式语言体系

形式语言体系可以表述判定问题和求解算法之间的联系，如果给定输入x，算法输出A（x）=1，我们说算法A接受串x，如果A（x）=0，我们说算法A拒绝串x。被算法A接受的语言L={x belongs to {0,1}*: A(x)=1}

如果对于L中每个x，要么被A接受要么被拒绝（不存在拒绝该x但是永远循环下去的情况，这种情况说A接受L），我们说L由A判定。

多项式时间的验证

Hamilton Cycle

我们先使用形式语言来定义Hamilton Cycle问题

HAM-CYCLE={:G is a Hamilton Cycle}

如何使用算法来判定Hamilton Cycle问题，已知一个问题实例，一种办法就是列出G定点的全部排列，然后对于每一种排列进行检查，那么这个算法的运行时间为Omega（2^(n^1/2)）

不难看出，如果有一个人说对于一个问题实例,他说这个图是一个Hamilton Cycle并给出了一个回路排列来证明，我们很容易来验证这个答案是否是正确的。

NP问题

从上面的问题可以看出，HAM-CYCLE属于NP，因为他能在多项式时间内被验证。

NP完全性与可归约性

HAM-CYCLE就是一个NPC问题

可归约性

一个问题Q可以被归约为另一个问题Q‘，如果Q的任何实例都可以被容易的（在多项式时间内）表述为Q’的实例，并且Q‘实例的解也是Q的实例的解，因此，如果一个问题Q可以归约成Q’，则从某种意义上来说Q不比Q‘更难解决

回归到形式语言体系中，也可也表述为L1可以在多项式时间内归约为语言L2，记作L1<=pL2。

如果L1<=pL2，则L2属于P蕴含着L1属于P

NP完全性

通过以上对于可归约性的定义，我们可以定义NPC的集合

语言L属于NPC，如果：

1. L属于NP

2. 对于每个L‘属于NP，有L’<=pL

如果一种语言满足2，但不一定满足1，我们称这种语言是NP-Hard

如果任何NP问题是多项式时间可以求解的，那么P=NP，等价的，如果NP中的任何问题不是多项式时间可以求解的，那么任何NP完全问题都不是多项式时间可以求解的。

NPC完全性的证明

引理

如果L是一种对于某个L‘属于NPC，有L’<=pL的语言，则L是NP难度的，此外如果L属于NP，则L属于NPC。