如果已知问题 X（决策问题）是 NP-Complete，并且证明可以在多项式时间内简化为问题 Y，那么您能说问题 Y 是 NP-Complete 吗？
我的第一个想法是，不，问题 Y 需要证明它在 NP 中。但是经过进一步思考，如果将 X 简化为 Y，则 Y 已经被认为是 NP-Complete。现在我很困惑......任何帮助将不胜感激。
问问题
923 次
5 回答
1
每个相反的论点：
如果 X ∈ NP 且 X ⇔ Y 且 Y ∉ NP 则 X ∉ NP。
于 2010-11-02T02:51:45.967 回答
1
问题 X - 不确定
问题 Y - 在 NP
为了证明 X 在 NP 中，您表明您可以按照步骤将 X 中的每个问题简化为 Y 中的问题。然后您知道 X 问题至少与等效的 Y 问题一样难。
所以不，你需要从 Y 开始，然后减少到 X。
于 2010-11-02T02:55:20.143 回答
0
SAT 可以通过对 ALL 的一次调用来解决，但这并不意味着 ALL 在 NP 中。
于 2010-11-02T06:13:26.093 回答
0
对，那是正确的。您可以在多项式时间内将您的问题简化为任何已知的 NP 完全问题，但这被认为是一项非常困难的任务。因此，您选择一个已经 NP 完全的问题并将其简化为您的问题，并表明它在 NP 中，那么您的问题将是 NP 完全的。
于 2013-12-01T00:00:25.250 回答
0
还没有，你还需要几个步骤
为了证明问题 L 是 NP 完全的，我们需要执行以下步骤：
- 证明您的问题 L 属于 NP（即给定一个解决方案，您可以在多项式时间内验证它）
- 选择一个已知的 NP 完全问题 L'
- 描述一个将 L' 转换为 L 的算法 f
- 证明你的算法是正确的（形式上：x ∈ L' 当且仅当 f(x) ∈ L ）
- 证明算法 f 在多项式时间内运行
到目前为止，您已经完成了第 2、3、4 步
，您仍然需要证明归约是多项式的（第 5 步）
并且问题属于 NP（第 1 步），即可以在多项式时间内验证解决方案。
于 2016-09-01T00:53:02.550 回答