为什么旅行商问题是NP难的，而哈密顿路径问题是NP完全的？

Question

为什么这两个问题，即TSP和哈密顿路径问题，都不是NP完全问题？

它们看起来是相同的。

- User

Answer 1

要成为NP-complete问题，问题X必须满足以下条件：

1. X在NP中，给定X的解决方案，可以在多项式时间内验证该解决方案。
2. X是NP-hard，也就是说，每个NP问题都可以在多项式时间内归约为它（可以通过从已知的NP-hard问题（例如哈密顿回路）进行约化来实现）。

旅行商问题（TSP）有两个版本:

1. 优化版本(可能是您正在查看的版本)，即找到TSP的最佳解决方案。这不是一个决策问题, 因此不能在NP中，但是它是NP-hard的，可以通过哈密顿回路约化证明。因此，这不是一个NP完全问题。
2. 决策版本 - 给定整数K，是否存在一条经过图中每个顶点的路径长度小于K？这是一个决策（是/否）问题，其解决方案可以在多项式时间内验证（只需遍历路径并查看是否触及每个顶点）。因此，它属于NP，并且也是NP-hard（与上述证明相同）。由于它满足NP完全性的所有要求，因此它是一个NP完全问题。

- ifma

---

那么这个优化问题是NP难问题？ - User

我认为你的定义中有几个错误。决策问题可能没有可以在多项式时间内验证的解（它只是任何具有是/否答案的问题）。NP-hard并非以其他NP-hard问题为基础来定义（尽管你的定义足够，但不是必要的）——定义是每个NP问题都可以在多项式时间内归约到它。 - Paul Hankin

@PaulHankin 当然，你是正确的，非常感谢你的评论。对于NP-hard的定义，我只想给出一个直观的定义，并说明证明问题X属于NP-hard所需的步骤。我更新了我的答案。 - ifma

问题：对于一个TSP决策问题，假设答案是否定的。你如何在多项式时间内检查它？ - wjmccann

通过遍历给定的解决方案并验证它确实是“否”，来证明@wjmccann。你不能简单地说“不”——你需要提供一个为什么答案是“不”的证明——从那里你可以简单地检查它，因为你只需要从解决方案遍历n个节点，所以它是在多项式时间内完成的。 - ifma

Answer 2

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。

- templatetypedef