我正在寻找 NP 问题和 NP 完全问题之间的区别。我在 Jason 的 StackOverflow 中找到了这个很好的答案。关于 NP 完全问题，他说
An NP problem X for which it is possible to reduce any other NP problem Y to X in polynomial time. Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X if there is a polynomial time algorithm f to transform instances x of X to instances y = f(x) of Y in polynomial time with the property that the answer to x is yes if and only if the answer to f(x) is yes.
我的问题是:哪个是 NP 完全问题，X 还是 Y？
最佳答案
NP 完全语言是 X。这个想法是您可以从任意 NP 语言 Y 开始，然后在多项式时间内将其简化为 X。
形式上，NP-completeness 的定义如下:语言 X 称为 NP-complete iff
- X ∈ NP。也就是说，X 不可能比“最难的 NP 问题”“更难”，因为 X 本身就是 NP 的一个成员。
- 对于任何 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 的元素。
希望这对您有所帮助!
关于algorithm - 以下哪种语言是 NP 完全的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13828615/