为什么TSP NP很难,而哈密顿路径NP是完全的?

对于问题X NP完成 ,它必须满足:

1. X在NP中 ,给定X的解,该解可以在多项式时间内验证。
2. X为NP硬 也就是说,每个NP问题都可以在多项式时间内还原为它(您可以通过从已知NP难问题(例如哈密顿路径)进行还原来实现)。

有两个版本的 旅行推销员问题(TSP) :

1. Hamiltonian Path reduction
2. 决策版本-给定一个整数K,长度图中的每个顶点都有一条路径<K这是一个决策(是/否)问题,一个解决方案可以在多项式时间内验证(只需遍历路径,看看它是否触及每个顶点),因此它是NP问题,但它也是NP难问题(通过上述相同的证明)。由于它满足NP完全性的两个要求,因此它是一个NP完全问题。

NP硬度和NP完备性的定义是相关的,但又是不同的。具体来说,如果NP中的每个问题都在多项式时间内归结为NP难问题,那么问题就是NP难的;如果一个问题既NP难又NP难,那么问题是NP完全的。

另一方面,哈密顿路径问题需要一个是/否的答案,它恰好在NP中。因此,由于它也是NP难的,所以它是NP完全的。

现在,您可以将TSP转换为决策问题,方法是将问题从“什么是最便宜的路径?”“有一条花费X或更少的路径吗?”,后一个公式是NP形式的,并且碰巧也是NP完全的。