NP类问题间的归约疑问：任意两个NP问题是否必可归约？

好问题！这触及了NP复杂度类内部层级结构的核心，答案是否定的——任意两个NP问题X和Y之间，并不必然存在X到Y的多项式时间归约，具体分情况来看：

首先得明确，复杂度理论界几乎所有人都相信P≠NP（虽然还没被严格证明），我们基于这个被广泛认可的假设展开讨论：

1. 当X是NP完全问题，Y是P类问题时 #

• Y（P类）可以轻松归约到X（NP完全）：比如你要把“判断一个数是否是偶数”这个P问题，转化为SAT（NP完全）问题，只需要构造一个简单的布尔公式——输入数是偶数时公式可满足，否则不可满足，这个转化过程是多项式时间的。
• 但反过来，X（NP完全）不能归约到Y（P类）：如果能的话，意味着所有NP问题都能先归约到X，再转成Y解决，那所有NP问题都成了P类问题，直接推出P=NP，和我们的假设矛盾。

2. NP中间问题的存在（Ladner定理） #

根据Ladner定理，如果P≠NP，那么NP里还存在一类「中间派」问题——它们既不属于P类（不能快速解决），也不是NP完全问题（不能接受所有NP问题的归约）。假设Z是这类问题：

• NP完全问题X无法归约到Z：要是能的话，所有NP问题都能通过X归约到Z，那Z就成了NP完全问题，和它的“中间派”身份矛盾。
• Z无法归约到P类问题Y：要是能的话，Z就能在多项式时间内解决，直接属于P类，同样矛盾。

3. 只有P=NP时，任意NP问题才能互相归约 #

如果哪天有人证明了P=NP，那所有NP问题都属于P类——而P类里的问题之间可以互相多项式归约：毕竟任何P类问题都能快速解决，你只需要先解决X，再根据结果构造Y的对应实例就行。

在P≠NP的假设下，NP类内部是有严格层级的：P类 ⊂ NP中间类 ⊂ NP完全类，上层问题没法归约到下层问题；只有同层级的NP完全问题之间可以互相归约，而跨层级的不行。

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