如果问题X（决策问题）已知是NP完全的，并且证明可以简化为问题Y，那么你能说问题Y是NP完全的吗？

Question

如果已知问题 X（决策问题）是 NP 完全的，并且证明在多项式时间内可简化为问题 Y，那么您能说问题 Y 是 NP 完全的吗？

我的第一个想法是，不，问题 Y 需要证明它是 NP 问题。但进一步思考，如果X约简为Y，Y就已经被认为是NP-Complete了。现在我只是很困惑...任何帮助将不胜感激。

Answer 1

反对意见：

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

Answer 2

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

为了证明 X 在 NP 中，您证明可以按照步骤将 X 中的每个问题简化为 Y 中的问题。然后您就知道 X 问题至少与等效的 Y 问题一样难。

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

Answer 3

SAT 可以通过对 ALL 的一次调用来解决，但这并不意味着 ALL 属于 NP。

Answer 4

是的，这是正确的。
您可以在多项式时间内将问题简化为任何已知的 NP 完全问题，但这被认为是一项非常困难的任务。
因此，你选择一个已经 NP 完全的问题并将其简化为你的问题，并表明它是 NP 的，那么你的问题将是 NP 完全的。

Answer 5

还没有，你还需要几个步骤

为了证明问题 L 是 NP 完全的，我们需要执行以下步骤：

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

到目前为止，您已经完成了步骤 2,3,4
您仍然需要证明减少是多项式的（步骤 5）
并且该问题属于NP问题（步骤1），即可以在多项式时间内验证解。