完成与NP
如果一个已知为NP-Complete的问题可以在多项式时间内归结为另一个问题B，那么B是（A）NP-完全的（B）NP-硬的
关于问题B是否在NP中没有提供。 我很困惑，因为在Hopcraft和Ullman的书中，如果一个NP完全问题P1在多项式时间内可以归结为问题P2，那么P2就是NP-完全的。 但它也需要一个问题是NP-Complete，它应该属于NP类。 伙计们帮助理解这个概念。
如果A可以在多项式时间内减少到B，所有你知道的是B比A更难。在你的情况下，如果A是NP-完全的，那么B就是NP-hard。
如果B也碰巧在NP中，那么B将是NP完全的（因为NP-完全意味着既在NP中又在NP-中同时）。
然而，没有什么能阻止你将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
由于问题A可以在多项式时间内简化为问题B，因此问题B的任何解都可以用来找到A的解。或者更简单地说，求解A并不比求解B困难。既然我们知道A是NP完全的，哪类问题至少和NP完全问题一样困难？
作为参考，你可能还想看看NP-Hard上的维基百科文章（特别是第二句），NP-Complete。 和减少。
如果A是NP完全的，那么它也一定是NP。 这又意味着可以在多项式时间内验证A的每个可能的解，这意味着对于B也是如此（因为A可以在多项式时间内缩减到B）。 因此B是NP; 它不必被说成是单独的条件。
链接地址: http://www.djcxy.com/p/39931.html上一篇: Complete vs. NP