如何certificate一个问题是NP完成的？

我有调度问题。 我需要certificate这个问题是NP完整的。 什么可以是certificateNP完整的方法？

Answer 1

要显示一个问题是NP完整的，你需要：

显示在NP中

换句话说，给定一些信息C ，你可以创build一个多项式时间algorithmV ，它将为每个可能的inputXvalidationX是否在你的域中。

例

certificate顶点覆盖问题 （也就是说，对于某个图G ， 它是否有一个顶点覆盖集合，其大小为k ，使得G中的每个边在覆盖集合中至less有一个顶点 ？）在NP中：

• 我们的inputX是一些图G和一些数k （这是来自问题的定义）

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

• 那么我们可以写出一个algorithmV ，给定G ， k和C ，在多项式时间内返回这个顶点集是否是G一个顶点覆盖。

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

请注意 ，我们不需要在多项式时间中findC 如果可以的话，问题将出现在P.

请注意 ，对于某些C ，algorithmV应该适用于每个 G 对于每个input应该存在的信息可以帮助我们validationinput是否在问题域中。 也就是说，不存在信息不存在的input。

certificate这是NP难

这涉及到一个已知的NP完全问题，如SAT ，布尔expression式的集合forms如下：

（A或B或C）和（D或E或F）和…

expression式是可以满足的 ，也就是说这些布尔值存在一些设置，这就使得expression式成立 。

然后在多项式时间内减lessNP-complete问题到你的问题 。

也就是说，给SAT一些inputX （或者你正在使用的任何NP完全问题），为你的问题创build一些inputY ，这样当且仅当Y在你的问题中时， X在SAT中。 函数f : X -> Y必须以多项式时间运行。

在上面的例子中，inputY将是图G和顶点覆盖k的大小。

为了充分certificate ，你必须certificate两个：

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

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

marcog的答案与几个其他NP完全问题可以减less到你的问题的链接。

注释：在步骤2（ certificate它是NP难 ），减less另一个NP难（不一定是NP完全）的问题，目前的问题将做，因为NP完全问题是NP难题的一个子集也在NP）。

Answer 2

你需要减lessNP-Complete问题到你有的问题。 如果减less可以在多项式时间内完成，那么你已经certificate你的问题是NP完全的，如果问题已经在NP中，因为：

这并不比NP完全问题容易，因为它可以在多项式时间中减less到NP-Hard问题。

详情请参阅http://www.ics.uci.edu/~eppstein/161/960312.html的结尾。;

Answer 3

首先，你显示它完全位于NP中。

然后，你会发现另一个你已经知道的问题是NP完整，并显示你如何多项式地减lessNP难题到你的问题。

Answer 4

1. 熟悉NP Complete问题的一个子集
2. certificateNP硬度：将NP完全问题的任意实例减less到问题的实例。 这是一个馅饼的最大的一块，熟悉NP完成问题的地方。 根据您select的NP完整性问题，减less将会或多或less。
3. certificate你的问题在NP中：devise一个可以在多项式时间validation一个实例是否是一个解的algorithm。

Answer 5

为了certificate问题L是NP完全的，我们需要执行以下步骤：

1. certificate你的问题L属于NP（即给出一个解决scheme，你可以在多项式时间validation）
2. select一个已知的NP完全问题L'
3. 描述将L'转换为L的algorithmf
4. certificate你的algorithm是正确的（forms上：x∈L'当且仅当f（x）∈L）
5. certificatealgorithm在多项式时间运行