“3 色问题的 NP-Complete 证明”

3 色问题 (3-Color) 的描述如下：给定一个图 ，为 中每一个顶点涂色，要求每两个相邻的顶点颜色不一致。问是否可以用 3 种颜色完成上面的要求。

首先我们证明这个问题是 NP 问题。显然，若给定一个解，我们只需要遍历每一个节点，检查其与其相临节点的颜色是否一致，即可判断解是否正确。这个操作显然是可以在多项式时间内完成的，所以 3 色问题是 NP 问题。

接下来我们通过将 SAT 转换到 3 色问题来证明 3 色问题是 NP 难问题。即任意给定一个 SAT ，我可以在多项式时间内将其转化为 3 色问题。实际上，通过下面的证明我们可以最终知道，3 色问题和 SAT 问题实际上是完全等价的。

首先我们知道 SAT 实际上与电路问题是等价的。即任意一个 SAT，它的布尔表达式都可以转换为一个等价的电路。我们利用电路作为中介，证明 3 色问题可以来构成电路来说明 3 色问题与电路问题的等价性，进而说明其与 SAT 问题的等价性。

首先我们规定我们要用的 3 种颜色分别叫做 , , 。其中 代表真， 代表假， 代表其他某种颜色（例如中性）。假设我们的输入变量是 ，我们先试着连接 和 来使 的取值只能为 和 ，即构造了一个布尔变量。

接着，我们引入一个新的节点 并尝试构造一个否门（NOT Gate）。我们构造的方法为先将 与 连接，使其成为一个布尔变量，再将其与 连接，使其不能和 取值相同。这时，当 为真时， 为假；当 为假时， 为真。

这样我们就成功构造出了一个否门。现在我们尝试构造一个 或门（OR Gate）。我们引入三个节点 , , 分别表示两个输入和或门的输出。我们首先将 , , 分别连接 使它们变成布尔变量，然后按下图连接各个节点。

当 为真， 为假时，我们由图可得 只能为真，同理当 为假， 也为假时，我们由图可得 只能为假。

与是我们成功使用 3 色问题构造出了非门和或门。结合他们我们得到了 或非门。根据逻辑电路，使用或非门我们可以构造出其他所有门。于是乎我们从 3 色问题出发，构造出了电子逻辑。于是对于任何一个电路问题，我都可以通过替换的方式将其转换为一个 3 色问题；对于任意一个 3 色问题，我也可以通过替换的方式将其转换为一个电路问题。替换的过程显然是可以在多项式时间内完成的。所以我们证明了 3 色问题与 SAT 问题的等价性，即 3 色问题是 NP 完全的。