有两种说法：
如果决策问题a是多项式时间可约为决策问题b（即A≤ pB），且b是np完全的，则a必须是np完全的。
以及：
如果决策问题B是多项式时间可约为决策问题a（即B≤ pA），且B是NP完全的，则a必须是NP完全的。
以上哪个说法是正确的？
你也能解释一下吗？
最佳答案
第一个陈述是错误的，因为它意味着通过解b，然后应用一些多项式时间算法，你可以解a，但是也许有另一种方法来解a，不需要解b，也许它只是多项式。
第二种说法是对的，因为这意味着你可以通过先解a来解b，然后用多项式时间算法来解b，但是b是np完全的，所以a必须是np完全的
关于algorithm - 将A还原为B:对还是错，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34079628/