algorithm - 将 A 简化为 B：对或错

Question

有两个陈述：如果决策问题 A 是多项式时间可简化为决策问题 B（即A≤ pB），并且 B 是 NP 完全的，则 A 必须是 NP 完全的。

和：

如果决策问题 B 是多项式时间可简化为决策问题 A（即B≤ pA），并且 B 是 NP 完全的，则 A 必须是 NP 完全的。

以上哪些说法是正确的？

也能解释一下吗？

Answer 1

第一个陈述是错误的，因为这意味着通过求解 B 然后应用一些多项式时间算法，您可以求解 A 但也许还有另一种求解 A 的方法不需要求解 B，而且它可能只是多项式。

第二个陈述是正确的，因为这意味着您可以通过首先解决 A 来解决 B，然后应用一些多项式时间算法来解决 B 但 B 是 NP 完全的，因此 A 必须是 NP 完全的