3

我正在寻找 NP 和 NP 完全问题之间的区别。我在 Jason 的 StackOverflow 中找到了这个很棒的答案。关于 NP 完全问题，他说

一个 NP 问题 X，它可以在多项式时间内将任何其他 NP 问题 Y 简化为 X。直观地说，这意味着如果我们知道如何快速求解 X，我们就可以快速求解 Y。准确地说，如果存在多项式时间算法 f 将 X 的实例 x 在多项式时间内转换为 Y 的实例 y = f(x)，则 Y 可简化为 X，并且当且仅当答案f(x) 是肯定的。

我的问题是：哪一个是 NP 完全问题，X 还是 Y？

4

2 回答 2

7

NP 完全语言是 X。想法是您可以从任意 NP 语言 Y 开始，然后在多项式时间内将其简化为 X。

形式上，NP-completeness 的定义如下： 语言 X 被称为 NP-complete iff

  1. X ∈ NP。也就是说，X 不能比“最难的 NP 问题”“更难”，因为 X 本身就是 NP 的成员。
  2. 对于任何 Y ∈ NP，存在从 Y 到 X 的多项式时间映射缩减。也就是说，X“至少与 NP 中的任何问题一样难”，因为 X 的多项式时间算法给出了多项式时间算法对于 Y。顺便说一下，Y 是多项式时间可简化为 X 的事实有时表示为 Y ≤ p X。

也就是说，可以将任何 NP 完全语言简化为任何其他 NP 完全语言，因此如果 Y 多项式时间减少到 X 并且 X 是 NP 完全的，则 Y 可能（但不是必须）是 NP -完全的。然而，众所周知，如果 Y 在多项式时间内减少到 X，则 Y 必须是 NP 的一个元素。

希望这可以帮助！

于 2012-12-11T21:19:44.833 回答
2

两者都或都不是。这个过程称为 Karp 约简，关键是任何 NP 完全问题都可以在多项式时间内转化为任何其他 NP 完全问题。

然而，NP 完全问题只是 NP 问题的一个子集。（根据我们目前的理解，如果 P=NP，它们是相同的。）

于 2012-12-11T21:16:23.937 回答