NP 完全问题：一个解开，全部解开

在所有 NP 问题里，存在一类特殊的问题——NP 完全问题（旅行商问题是其代表）——它们彼此之间存在一种奇特的等价关系：只要能为其中任何一个 NP 完全问题找到多项式时间的确定性解法，这个解法就能被推广、用来在多项式时间内解决所有其他的 NP 问题。换句话说，NP 完全问题是整个 NP 类里”最难”的那批问题，它们的难度彼此互相牵连，一荣俱荣、一损俱损。这也意味着，只要有人证明了任何一个 NP 完全问题存在高效解法，就等于一举证明了 P 类和 NP 类其实是同一个集合（P=NP）。发散：NP 完全问题的存在把”P 是否等于 NP”这个抽象的理论问题，变成了一个可以通过研究具体某一个问题（比如旅行商问题）来推进的具体目标——这也是为什么几十年来无数计算机科学家反复扑向旅行商问题、背包问题这类具体的 NP 完全问题：破解其中任何一个，都等于同时破解了整个 NP 类问题的效率天花板，这个巨大的”连带效应”正是它们格外吸引研究者的原因。