从NP完全问题到其他问题的多项式时间缩减

Question

有人能消除我的疑虑吗？

假设我有一个已知为NP完全的问题A。我还有另一个问题B，我们不知道它的复杂度。

如果我在多项式时间内将A减少到B。我们可以说B也是NP-完全的。

但是..。如果我在多项式时间内将B化为A。为什么我不能在NP-Complete中也说B？

Answer 1

如果我在多项式时间内将A还原为B，则为

。我们可以说B也是NP-完全的。

不，我们可以说B是NP-难的。完备性也需要NP中的成员身份，这并不是从假设中得出的。

例如，我们可以将3SAT简化为停止问题。停顿问题不在NP中(它甚至不是可判定的)。

如果我在多项式时间内将B化为A，则为

。为什么我不能在NP-Complete中也说B？

我们可以说B在NP中。B的一种算法是使用约简，然后求解A。B可能是一个简单的问题，比如“输入的长度是奇数”。

Answer 2

如果A是NP完全的，则可以将NP中的任何问题归结为A。NP完全问题是NP中最困难的问题。

如果你可以在多项式时间内将A简化为B，这意味着B“至少和”A一样难，因为如果你能解决B，那么就很容易解决A。所以，如果A是NP -完全的，并且那些(根据定义)是NP中最难的问题，B也是NP-完全的(假设B在NP中，否则它就是NP- hard )。

另一方面，能够将B简化为A就像能够用火箭筒杀死一只蚂蚁一样。你显然可以做到，但这并不意味着杀死一只蚂蚁是“火箭筒完成”。