NP-完全vs. NP-hard

Question

如果一个已知为NP-完全的问题A可以在多项式时间内归结为另一个问题B，则B是(A) NP-完全(B) NP-困难的

无论问题B是否在NP中，都没有给出任何关于它的内容。我很困惑，因为在霍普克拉夫特和乌尔曼的书中有一个定理，如果一个NP-完全问题P1可以在多项式时间内归结为问题P2，那么P2是NP-完全的。但它也要求一个问题是NP完全的，即它应该属于NP类。男人有助于理解这个概念。

Answer 1

如果A可以在多项式时间内化为B，你所知道的就是B比A更难。在你的例子中，如果A是NP完全的，那么B是NP难的。

如果B恰好也在NP中，那么B将是NP -完全的(因为NP-完全意味着既在NP中又是NP难的)。

然而，没有什么能阻止你将A归结为一个不在NP中的问题。例如，将NP中的任何问题归结为停顿问题是微不足道的-除了NP-hard之外，该问题还是一个无法确定的问题：

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

Answer 2

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

作为参考，你可能还想看看维基百科上关于NP-Hard的文章(特别是第二句话)，NP-Complete。和Reduction。

Answer 3

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