这些语言中哪个是NP完全的？

Question

我在搜索NP和NP-complete问题的区别。我在StackOverflow上找到了Jason的一个很好的答案。关于NP-complete问题，他说：

一个NP问题X，它可以在多项式时间内将其他任何NP问题Y减少为X。 直观地说，这意味着如果我们知道如何快速解决X问题，我们就可以快速解决Y问题。 精确地说，如果存在一个多项式时间算法f将X问题的实例x转换为Y问题的实例y = f（x），并且具有以下特性：当且仅当x的答案是yes时，f（x）的答案也是yes。

我的问题是：哪个是NP-complete问题，X还是Y？

- odbhut.shei.chhele

Answer 1

NP完全语言是X。其思想是，您可以从任意的NP语言Y开始，并在多项式时间内将其归约为X。

严格来说，NP完全性的定义如下：如果语言X满足以下条件，则称其为NP完全：

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的元素。

希望这可以帮助您！

- templatetypedef

---

这可能看起来很愚蠢，但最难的 NP 问题不属于 NP 吗？那么为什么 X 不能比最难的 NP 问题更难呢？ - odbhut.shei.chhele

@eddard.stark- 你说得对，最难的NP问题必须属于NP。NP完全问题也必须属于NP，这意味着它们不能比最难的NP问题更难，因为NP完全问题不超出NP范围。这样讲清楚了吗？ - templatetypedef

@eddard.stark 记住，任何 x 和 y 之间都有一个转换函数，因此 X 和 Y 的复杂度并不完全相同。 - wangkaibule

Answer 2

两者都可以。这个过程被称为Karp归约，重点是任何NP完全问题都可以在多项式时间内转化为任何其他NP完全问题。

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

- biziclop

---

我认为你声称“任何”NP问题都可以转化为“任何”其他NP问题是错误的。这意味着NP与NP-complete相同，但正如你自己提到的，NP-complete是NP的子集。（除非P=NP） - JoshOrndorff

谢谢，当然我本来就想写NP完全问题的。我会更新答案的。 - biziclop

那个部分是固定的，但你的主要答案“两者都不或都是”仍然是错误的。请参考@templatetypedef的答案，了解为什么X必须是NP-Complete。 - JoshOrndorff