5

如果一个已知为 NP-Complete 的问题 A 可以在多项式时间内简化为另一个问题 B，则 B 是 (A) NP-Complete (B) NP-hard

无论问题 B 是否在 NP 中，都没有给出任何内容。我很困惑，因为在 Hopcraft 和 Ullman 书中给出了一个定理，如果一个 NP 完全问题 P1 可以在多项式时间内简化为问题 P2，那么 P2 是 NP 完全的。但它也要求一个问题是 NP 完全的，它应该属于 NP 类。伙计们帮助理解这个概念。

4

3 回答 3

9

如果可以在多项式时间内将 A 简化为 B，那么您所知道的就是 B 比 A 更难。在您的情况下，如果 A 是 NP 完全的，则 B 是 NP 难的。

如果 B 也恰好在 NP 中，则 B 将是 NP 完全的（因为 NP 完全意味着同时处于 NP 和 NP-hard 中）。

然而，没有什么能阻止你将 A 简化为一个不在 NP 中的问题。例如，将 NP 中的任何问题简化为停止问题是微不足道的——除了 NP 难之外，这个问题是不可判定的：

Construct the following program:
    Test all possible solutions for A.
    If one of them is successful halt and otherwise enter an infinite loop.
A has a solution if-and-only if that program halts
于 2011-11-25T17:06:02.933 回答
2

由于问题 A 可以在多项式时间内简化为问题 B，因此问题 B 的任何解决方案都可以用来找到 A 的解决方案。或者更简单地说，解决 A 不会比解决 B 更难。因为我们知道 A 是 NP 完全的，哪一类问题至少和 NP 完全问题一样难？

作为参考，您可能还想查看关于NP-Hard（特别是第二句）、NP-Complete的维基百科文章。和减少。

于 2011-11-25T17:00:37.710 回答
-1

如果 A 是 NP-完全的，那么它也必然是 NP。这反过来意味着 A 的每个潜在解决方案都可以在多项式时间内得到验证，这意味着 B 也是如此（因为 A 在多项式时间内可简化为 B）。因此 B 是 NP；不必将其声明为单独的条件。

于 2011-11-25T16:42:42.503 回答