要成为NP-complete问题,问题X必须满足以下条件: X在NP中,给定X的解决方案,可以在多项式时间内验证该解决方案。 X是NP-hard,也就是说,每个NP问题都可以在多项式时间内归约为它(可以通过从已知的NP-hard问题(例如哈密顿回路)进行约化来实现)。 旅行商问题(TSP)有两个版本: 优化版本(可能是您正在查看的版本),即找到TSP的最佳解决方案。这不是一个决策问题, 因此不能在NP中,但是它是NP-hard的,可以通过哈密顿回路约化证明。因此,这不是一个NP完全问题。 决策版本 - 给定整数K,是否存在一条经过图中每个顶点的路径长度小于K?这是一个决策(是/否)问题,其解决方案可以在多项式时间内验证(只需遍历路径并查看是否触及每个顶点)。因此,它属于NP,并且也是NP-hard(与上述证明相同)。由于它满足NP完全性的所有要求,因此它是一个NP完全问题。
NP-hard和NP-complete的定义相关但不同。具体来说,如果NP中的每个问题可以在多项式时间内归约到某个问题,则该问题是NP-hard;如果一个问题既是NP-hard又在NP中,则该问题是NP-complete。类NP包括决策问题,即有是/否答案的问题。因此,TSP不能在NP中,因为期望答案是一个数字而不是是/否答案。因此,TSP可能是NP-hard,但不能是NP-complete。另一方面,Hamiltonian路径问题要求是/否答案,恰好在NP中。因此,由于它也是NP-hard,所以它是NP-complete。现在,你可以通过将TSP转换为决策问题,将问题从“最便宜的路径是什么?”改为“是否存在一条成本小于等于X的路径?”这样后者的表述在NP中,同时也是NP-complete。