《算法详解》为何用Turing归约而非Karp归约证明NP难问题？

一、为何选择图灵归约而非卡普归约？ #

• 更贴合入门直觉：图灵归约的表述更贴近普通人对“问题难度关联”的朴素理解——如果能通过多次调用问题B的解法，再辅以少量额外计算就解决问题A，那显然A的难度不会超过B。这种定义不需要引入“多项式时间输入映射”这类相对抽象的概念，对刚接触复杂度理论的学习者更友好，能快速建立“归约”的核心认知。
• 证明场景更灵活：部分问题的NP难证明，用图灵归约实现起来更简洁。有些问题的求解逻辑天然适合通过多次调用子程序完成，而非一次性将输入转化为另一个问题的实例。教材选择这种定义，大概率是为了降低初学者的证明门槛，让他们更快掌握NP难证明的核心思路。

二、采用图灵归约是否会改变NP难问题的集合？ #

结论是：在P≠NP的前提下，两种归约定义的NP难问题集合完全一致。

你的直觉是正确的——两种归约都满足核心性质：若A可归约到B，且B存在多项式时间算法，则A也存在多项式时间算法。针对NP类问题，卡普归约和图灵归约的能力是等价的：任何能通过图灵归约证明NP难的问题，也能通过卡普归约完成证明；反之亦然。这是因为NP类问题具备自我归约性，图灵归约的多次子程序调用可以转化为单次的卡普归约输入映射。

当然如果跳出NP类讨论更广泛的复杂度类，两种归约的能力确实存在差异，但在NP难的范畴内，二者定义的集合完全重合。

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