How to prove that a problem is NP complete?

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

151629 次浏览
小开

首先，你证明了它完全位于 NP 中。

Then you find another problem that you already know is NP complete and show how you polynomially reduce NP Hard problem to your problem.

小开

你需要把一个 NP 完全问题简化为你所有的问题。如果还原可以在多项式时间内完成，那么你已经证明了你的问题是 NP 完全的，如果问题已经在 NP 中，因为:

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

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

小开
最佳答案

To show a problem is NP complete, you need to:

在 NP 中显示它

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

例子

证明了 顶点覆盖问题(对于某些图 G，它是否有一个大小为 ABC1的顶点覆盖集，使得 G中的每个边在覆盖集中至少有一个顶点?)在 NP 中:

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

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

  • Then we can write an algorithm V that, given G, k and C, will return whether that set of vertices is a vertex cover for G or not, in 多项式时间.

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

Note that we do not need to find C in polynomial time. If we could, the problem would be in `P.

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

证明它是 NP 困难

这涉及到一个已知的 NP 完全问题，比如 高考，它是一组布尔表达式的形式:

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

其中表达式是 令人满意，也就是存在一些布尔值设置，这使得表达式 没错。

Then 在多项式时间内将 NP 完全问题归结为你的问题.

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

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

对于 完全证明，你必须同时证明以下两点:

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

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

Marcog 的 答案与其他几个 NP 完全问题有联系，你可以把它们归结为你的问题。

Footnote: In step 2 (证明它是 NP 难的), reducing another NP-hard (not necessarily NP-complete) problem to the current problem will do, since NP-complete problems are a subset of NP-hard problems (that are also in NP).

小开
  1. 熟悉 NP 完全问题的一个子集
  2. 证明 NP 难度: 将一个 NP 完全问题的任意实例简化为你的问题的实例。这是最大的一块蛋糕，熟悉 NP 完全问题是值得的。根据你选择的 NP 完全问题，这个减少或多或少是困难的。
  3. 证明你的问题是在 NP 中: 设计一个算法，可以在多项式时间验证一个实例是否是一个解。
小开

In order to prove that a problem L is NP-complete, we need to do the following steps:

  1. 证明你的问题 L 属于 NP (即给出一个解，你可以在多项式时间内验证它)
  2. 选择一个已知的 NP 完全问题 L’
  3. 描述一种将 L’转换为 L 的算法 f
  4. 证明了算法的正确性(形式上: x ∈ L’当且仅当 f (x)∈ L)
  5. Prove that algo f runs in polynomial time

提交答案