如何证明问题是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应该适用于每个人 .对于每个输入,应该存在可以帮助我们验证输入是否在问题域中的信息.也就是说,不应存在信息不存在的输入.GC

证明它是NP Hard

这涉及到获得一个已知的NP完全问题,如SAT,即表格中的布尔表达式集合:

(A或B或C)和(D或E或F)和......

表达式是可满足的,即存在一些这些布尔值的设置,这使得表达式成立.

然后在多项式时间内将NP完全问题减少到您的问题.

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

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

要获得完整的证明,您必须证明两者:

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

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

marcog的答案与您可以减少问题的其他几个NP完全问题有关.

脚注:在第2步(证明它是NP难的),将当前问题的另一个NP难(不一定是NP完全)问题减少将会发生,因为NP完全问题是NP难问题的一个子集(即也在NP).

Answer 2

您需要将NP-Complete问题减少到您遇到的问题.如果减少可以在多项式时间内完成,那么你已经证明你的问题是NP完全的,如果问题已经在NP中,因为:

它不比NP完全问题容易,因为它可以在多项式时间内减少到它,这使得问题NP-Hard.

有关更多信息,请参见http://www.ics.uci.edu/~eppstein/161/960312.html的结尾.

Answer 3

首先,你表明它完全位于NP中.

然后你会发现另一个你已经知道NP完成的问题,并展示你如何多方式地减少NP Hard问题.

Answer 4

为了证明问题L是NP完全的,我们需要执行以下步骤:

1. 证明你的问题L属于NP(即给定一个解决方案,你可以在多项式时间验证它)
2. 选择一个已知的NP完全问题L'
3. 描述将L'变换为L的算法f
4. 证明你的算法是正确的(形式上:x∈L'当且仅当f(x)∈L时)
5. 证明算法f在多项式时间内运行

Answer 5

1. 熟悉NP完整问题的一部分
2. 证明NP硬度：将NP完全问题的任意实例简化为您的问题的实例。这是最大的一块蛋糕，而对NP Complete问题的熟悉也值得付出。根据您选择的NP完全问题，减少难度将或多或少。
3. 证明您的问题出在NP上：设计一种算法，该算法可以在多项式时间内验证实例是否为解。