如何证明一个问题是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

，布尔表达式的集合，其形式为：

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

其中表达式是

可满足

，即这些布尔值存在一些设置，这使得表达式true。 然后

将 NP 完全问题简化为多项式时间内的问题

。 也就是说，给定 SAT 的一些输入

X

（或者您正在使用的任何 NP 完全问题），为您的问题创建一些输入

Y

，这样

X

就在 SAT 中当且仅当

Y

是在你的问题中。函数

f : X -> Y

必须在

多项式时间内运行

。 在上面的示例中，输入

Y

将是图形

G

和顶点覆盖的大小

k

。要获得

完整的证明

，您必须同时证明：

• X

  位于

  SAT

  =>

  Y

  在你的问题中 您问题中的

和
• Y

  =>

  X

  中的

  SAT

  。

marcog 的

答案与其他几个 NP 完全问题有联系，您可以将其简化为您的问题。 脚注：在步骤 2 中（

证明它是 NP-hard

），将另一个 NP-hard（不一定是 NP-complete）问题简化为当前问题即可，因为 NP-complete 问题是 NP-hard 问题的子集（也在 NP 中）。

Answer 2

它并不比 NP 完全问题容易，因为它可以在多项式时间内简化为 NP 完全问题，这使得问题成为 NP 困难问题。

请参阅

http://www.ics.uci.edu/~eppstein/161/960312.html

的末尾了解更多信息。

Answer 3

证明你的问题L属于NP（即给定一个解决方案，你可以在多项式时间内验证它）

1. 选择一个已知的 NP 完全问题 L'
2. 描述将 L' 转换为 L 的算法 f
3. 证明你的算法是正确的（形式上：x ∈ L'当且仅当 f(x) ∈ L ）
4. 证明算法 f 在多项式时间内运行

Answer 4

然后你会发现另一个你已经知道是 NP 完全问题的问题，并展示如何通过多项式将 NP 困难问题简化为你的问题。

Answer 5

熟悉 NP 完全问题的子集

1. 证明 NP 难度：将 NP 完全问题的任意实例减少为您的问题的实例。这是最大的一块，熟悉 NP 完全问题是值得的。减少的难度或多或少取决于您选择的 NP Complete 问题。
2. 证明你的问题是 NP 问题：设计一个算法，可以在多项式时间内验证一个实例是否是一个解。