NP完备性问题
NP-Complete问题（NPC问题）是信息学中一个重要和知名的命题，我们现在在尝试一下自然地理解这个问题。 首先从涉及到的名词开始，这里会涉及到的名词包括P问题，NP问题，NPC问题和NP-Hard问题。我们从最简单的P问题开始。P问题是存在能够在多项式时间复杂度内解决问题的算法的问题。这对于实现来说是一个“好”的性质。因为更高的时间复杂度，如阶乘或指数时间复杂度算法的耗时会随着数据规模的增长极其迅速地增长，带来的开销是无法接受的。因此我们当然希望所有的问题都可以是P问题。但是我们可以发现，对于有些问题没能找出多项式时间复杂度的算法，对于这一类问题我们可以退而求其次，寻找在在多项式时间复杂度内验证一个解的方法，这就引出了NP问题。 NP问题指的是可以在多项式时间内验证一个解的问题。我们容易知道，一个NP问题必定是一个P问题，因为既然已经求出了解，那么验证只需要进行一个不增加时间复杂度的比对就行。即有逻辑表达式$P \in NP$。那么自然的，我们也会想知道是否有$NP \in P$，如果我们能够证明$NP \in P$，那也就证明了$P = NP$，因为这就意味着凡是能在多项式复杂度内验证的问题都可以在多项式复杂度内解决，这有着重大意义。这是信息学中一个重要、知名和至今仍未被解决的问题。为了尝试证明或证伪这个命题，我们需要引入另一个概念————规约，或称约化(Reducibility)。 规约的定义是这样的，如果可以通过将问题A转化为问题B的一个实例，从而运用解决B的方案来解决A，那么我们就说“问题A可以规约到问题B”。一个经典的例子是，问题A是求解一元一次方程，问题2是求解一元二次方程，此时A可以作为B的一个实例，即令二元一次方程的平方项系数为0，它就退化成了一个一元一次方程。因此我们说求解一元一次方程问题可以归约到求解一元二次方程问题。而在NP问题的场景下，一个经典的例子就是Halmition回路问题与TSP问题。在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。那么引入规约的意义在哪里呢？意义在于我们可以注意到，如果A可以被归约到B，那么必然有A的时间复杂度小于等于B，因此我们可以说A不比B简单。注意这里的简单不只是一个直观的感受，而是有明确定义的，即如果A可以被归约到B，那么A不比B简单。（当然这个定义也是符合直觉的）通过规约，我们可以尝试将一个NP问题包含到另一个NP问题中，并且尝试找到一个能够包含一切NP问题的问题，即NP-Complete问题，简称NPC问题。当然，在这一语境下，这个变换的方法的时间复杂度也必须是多项式复杂度的，否则就失去了意义。这样的规约被称为“多项式地”规约，以下简称为规约。 首先我们来解答一个问题：是否真的存在NPC问题？答案是肯定的，历史上发现的第一个NPC问题是电路可满足性问题(CIRCUIT-SAT)。简单地说，就是组织一系列的逻辑电路。要求求解各组能够使电路输出为true的输入。那么如何证明这是一个NPC问题？首先容易发现这个问题可以在多项式时间内验证，因为只需要按照电路逐步计算即可。然后我们可以发现，所有的计算机问题都可以视为一系列的0和1信号在电路中的流动，因此所有计算机问题都可以被归约到电路可满足性问题。 在发现了第一个NPC问题后，寻找新的NPC问题就变的容易了。因为证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它即可。 那么NPC问题对于证明或证伪$P = NP$有什么意义？意义在于它使得$P = NP$显得难以置信。因为所有的NPC问题在难度上都是等价的，这就意味着计算机科学领域和生产生活中的巨量问题，包括SAT、TSP、图着色问题、背包问题、蛋白质折叠问题、整数规划问题等全部都存在一个共同的、高校的解法。这就像是说，你只需要找到一把能打开“旅行商问题”这个锁的钥匙，然后你惊讶地发现，这把钥匙竟然也能打开“蛋白质折叠”、“芯片设计”、“航班调度”等成千上万把看起来完全不同的锁。这种“万能钥匙”的存在，虽然在逻辑上不能被排除，但在直觉和经验上是极其反常和令人难以置信的。 最后来讲一下NP-Hard问题，NP-Hard问题是不被包含在上面的主线（从P到NP再到NPC）中的，因为一个NP-Hard问题可能不是一个NP问题。一个问题成为NP-Hard问题只需要满足一个条件：任何一个 NP 问题都可以在多项式时间内归约到它。它和NPC问题的区别在于NPC-Hard问题并不要求问题能在多项式时间内被验证。简单说：NP-Hard 是一个更宽泛的标签，它只关心问题的“难度下限”，而不关心问题本身是否容易验证。它包含了以下问题：
- 所有的 NP-Complete 问题。
- 比 NP-Complete 更难，但仍然可解的问题（如优化版 TSP）。
- 比 NP-Complete 难得多，甚至不可解的问题（如停机问题）。