若A为NP完全问题、B为NP难问题，B能否多项式时间归约到A？

你这个判断完全正确——一般来说，NP难问题B无法保证在多项式时间内归约到NP完全问题A，核心原因确实和「NP完全是NP难的子集」这个关系直接相关。

咱们先把关键定义掰扯明白，避免混淆：

• NP完全问题（NP-complete）：必须同时满足两个条件：
  1. 它属于NP类（也就是问题的解可以在多项式时间内验证）；
  2. 所有NP类问题都能在多项式时间内归约到它。
• NP难问题（NP-hard）：只需要满足一个条件：所有NP类问题都能在多项式时间内归约到它，但它不一定属于NP类。

从定义就能看出来：NP完全是NP难的真子集——所有NP完全问题都是NP难，但NP难问题的范围更大，包含了那些甚至不属于NP的问题（有些NP难问题甚至是不可判定的，比如停机问题）。

举个具体的例子：停机问题是经典的NP难问题，但它是不可判定的（没有任何算法能解决它），而A作为NP完全问题，属于NP类，是可判定的（至少可以通过非确定性算法在多项式时间内验证解）。你不可能把一个不可判定的问题多项式归约到一个可判定的问题——这逻辑上就不成立，因为归约意味着用A的解来解决B的问题，但B本身根本没有能被算法解决的解，更别说多项式时间内了。

只有当B本身同时属于NP类时（也就是B是NP完全问题时），它才能和A互相多项式归约，但题目里只说B是NP难，没说它属于NP，所以我们不能保证这个归约存在。

内容的提问来源于stack exchange，提问作者centrinok