NP完全问题的两种定义是否等价？

结论：在计算复杂性理论的标准研究框架下，两个定义完全等价，仅存在表述视角的差异，无实质判定区别。 #

定义原文重述 #

定义1（通用标准定义） #

问题B属于NP完全问题当且仅当同时满足两个条件：

• B属于NP类
• 对任意NP类问题C，C可在多项式时间内归约到B

定义2（部分文献采用定义，出自Berlekamp、McEliece与Tilborg《On the Inherent Intractability of Certain Coding Problems》等相关研究） #

问题B属于NP完全问题当且仅当同时满足两个条件：

• B属于NP类
• 若B存在多项式时间求解算法，则所有NP类问题均存在多项式时间求解算法

等价性推导 #

两个定义的约束条件可以双向互推：

1. 定义1 → 定义2：如果所有NP问题都能在多项式时间内归约到B，那么只要B有多项式时间解法，对任意NP问题，只需要先做多项式时间归约，再调用B的解法，整体计算复杂度依然是多项式级，自然所有NP问题都存在多项式时间解法，完全满足定义2的要求。
2. 定义2 → 定义1：“B有多项式时间解法则所有NP问题都有多项式时间解法”的本质，就是B是NP类中难度最高的问题，所有NP问题的求解难度都不高于B，对应的形式化表达就是所有NP问题可在多项式时间内归约到B，完全满足定义1的要求。

边界说明 #

两个定义的等价性建立在*多项式时间多对一归约（Karp归约）*的标准约定上，如果替换归约模型（比如采用多项式时间图灵归约即Cook归约），二者的判定边界会出现细微差异，但这属于归约模型选择的问题，不影响绝大多数算法设计、复杂性分析、密码学/编码理论难解性证明场景下的等价性。定义2本质是跳过了归约的形式化描述，直接从NP完全问题“NP类最难问题”的核心性质出发做的直白表述，不存在和标准定义的冲突。

注：P与NP是否相等的猜想结果，不会影响两个定义的等价性。即使未来证明P=NP，两个定义对NP完全问题的判定结果依然保持一致。

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