若属于P或NP的问题X可归约至NP完全问题，X是否为NP难问题？

先明确几个核心定义，这是理解问题的基础：

• NP难问题：如果所有NP类中的问题都能在多项式时间内归约到问题X，那么X是NP难的。注意NP难问题不一定属于NP。
• NP完全问题：同时满足两个条件：(1) 属于NP类；(2) 是NP难的。这类问题是NP类里“最难”的一批。
• 多项式时间归约（记作 (A \leq_p B)）：如果能在多项式时间内把问题A的任意实例转化为问题B的实例，说明B的解法可以直接用来解决A，换句话说，B至少和A一样难。

问题1：将P或NP问题（注：归约是问题层面的操作，不是单个实例）归约到NP完全问题后，该问题是否属于NP难问题？ #

答案是不一定，甚至绝大多数情况下都不是。

举个直观的例子：排序问题是典型的P类问题，我们可以很容易地把排序问题的实例转化为SAT（经典NP完全问题）的实例——但排序问题显然不是NP难的（除非P=NP这个未被证明的猜想成立）。原因很简单：NP难要求所有NP问题都能归约到它，而排序问题只能处理P类的任务，没法让更复杂的NP问题（比如旅行商问题）归约到它。

你这里的逻辑搞反了：归约的方向决定了难度的传递。如果NP完全问题归约到X，那X才是NP难的；而X归约到NP完全问题只能说明NP完全问题比X难（或者难度相当），不能反过来证明X的难度。

问题2：若属于P或NP的问题X可归约至NP完全问题，该问题X是否自动成为NP难问题？ #

答案还是不一定，核心逻辑和上面一致。

只有当X满足“所有NP问题都能归约到它”时，X才是NP难的。而X能归约到NP完全问题，只说明X的难度不超过NP完全问题——比如所有P类问题都能归约到NP完全问题，但它们都不是NP难的（默认P≠NP的前提下）。

如果要让X成为NP难问题，你需要证明的是反向归约：把某个NP完全问题归约到X，这样就能推导所有NP问题都能通过先归约到这个NP完全问题，再归约到X，从而满足NP难的定义。

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