如果一个问题X（决策问题）已知为NP完全问题，并被证明可以归约到问题Y，那么你能说问题Y也是NP完全问题吗？

Question

如果一个问题X（决策问题）已知是NP-完全的，并且被证明可以在多项式时间内归约到问题Y，那么你能说问题Y也是NP-完全的吗？

我的第一反应是不行，问题Y需要被证明它属于NP。但经过进一步思考，如果X被归约到了Y，那么Y已经被认为是NP-完全的了。现在我只是有些困惑...任何帮助都将不胜感激。

- Mr. X

---

我认为你第一次已经说得很清楚了。如果我们能将任何已知问题归约到另一个NP完全问题上，那么该问题也是NP问题。 - Jim

从维基百科上可以看到：“通过从先前已被证明为NP完全的其他问题进行约简，已经显示出成千上万的其他问题也是NP完全的。”所以我会说答案是“是”吗？ - White Dragon

根据定义，Y是“NP-hard”。 NP-hard问题是可以用来解决NP中的任何问题，包括NP-complete问题。然而，NP-hard问题不一定在NP中。 - gnasher729

Answer 1

反证法：

如果 X ∈ NP 且 X ⇔ Y，而 Y ∉ NP，则 X ∉ NP。

- msw

Answer 2

问题X - 不确定
问题Y - 在NP中

为了证明X在NP中，你需要展示你可以按照步骤将X中的每个问题都归约到Y中的一个问题。这样你就知道X问题至少和等价的Y问题一样难。

所以，不，你需要从Y开始，然后归约到X。

- Kevin Burke

Answer 3

还没有，你需要更多的步骤。

为了证明一个问题L是NP完全问题，我们需要完成以下步骤：

1. 证明你的问题L属于NP（也就是说，给定一个解决方案，你可以在多项式时间内验证它）
2. 选择一个已知的NP完全问题L'
3. 描述一个算法f，将L'转化为L
4. 证明你的算法是正确的（形式上：x ∈ L'当且仅当f(x) ∈ L）
5. 证明算法f在多项式时间内运行

到目前为止，你已经完成了第2、3、4步。
你仍然需要展示缩减是多项式的（第5步），并且该问题属于NP（第1步），也就是说，可以在多项式时间内验证解决方案。

- Albert s

Answer 4

SAT问题可以在一次ALL调用中解决，但这并不意味着ALL属于NP。

- Charles

Answer 5

是的，那是正确的。 你可以将你的问题在多项式时间内归约到任何已知的 NP 完全问题，不过这被认为是一项非常困难的任务。 所以，你可以选择一个已经是 NP 完全问题的问题，并将其归约到你的问题，同时还要证明它在 NP 中，然后你的问题就会成为 NP 完全。

- happs