algorithm - 如何证明一个问题是NP完备的？

Question

我的日程安排有问题。我需要证明这个问题是NP完全的。 NP完备的证明方法有哪些？

Answer 1

要证明问题是 NP 完备的，您需要:

显示为NP

换句话说，给定一些信息 C，您可以创建一个多项式时间算法 V 来验证每个可能的输入 X 是否X 是否在您的域中。

例子

证明顶点覆盖问题(也就是说，对于某个图G，它是否有一个顶点覆盖集k 这样 G 中的每条边在覆盖集中至少有一个顶点?) 在 NP 中:

• 我们的输入 X 是一些图 G 和一些数字 k(这来自问题定义)

• 将我们的信息 C 设为“图 G 中大小为 k 的任何可能的顶点子集”

• 然后我们可以编写一个算法 V，给定 G、k 和 C，将在多项式时间中返回该组顶点是否为G 的顶点覆盖。

然后对于每个图 G，如果存在一些“G 中大小为 k 的顶点的可能子集”，它是顶点覆盖, 那么 G 在 NP 中。

注意我们不需要需要在多项式时间内找到C。如果可以的话，问题就出在 `P.

注意算法V应该适用于每个 G，对于某些C。对于每个输入，应该存在信息可以帮助我们验证输入是否在问题域中。也就是说，不应该在信息不存在的地方输入。

证明它是NP Hard

这涉及得到一个已知的 NP 完全问题，如 SAT ，形式为 bool 表达式的集合:

(A or B or C) and (D or E or F) and ...

表达式可满足的地方，即这些 bool 值存在一些设置，这使得表达式为真。

然后在多项式时间内将 NP 完全问题简化为您的问题。

也就是说，给定 SAT(或您正在使用的任何 NP 完全问题)的一些输入 X，为 Y 创建一些输入你的问题，这样当且仅当 Y 在你的问题中时，X 在 SAT 中。函数 f : X -> Y 必须在多项式时间内运行。

在上面的示例中，输入 Y 将是图 G 和顶点覆盖的大小 k。

对于完整的证明，您必须同时证明:

• X 在 SAT 中 => Y 在你的问题中

• 和 Y 在您的问题中 => X 在 SAT 中。

ma​​rcog 的 答案与其他几个 NP 完全问题有链接，您可以将其归结为您的问题。

脚注:在步骤 2(证明它是 NP-hard)中，将另一个 NP-hard(不一定是 NP-complete)问题简化为当前问题就可以了，因为 NP-complete 问题是NP-hard 问题的一个子集(也在 NP 中)。