5

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

它们看起来相同。

4

2 回答 2

7

对于一个问题 X 是NP-complete，它必须满足：

  1. X 在 NP 中，给定 X 的解，可以在多项式时间内验证解。
  2. X 在 NP-hard中，也就是说，每个 NP 问题都可以在多项式时间内归约到它（您可以通过从已知的 NP 难问题（例如哈密顿路径）中归约来做到这一点）。

旅行商问题 (TSP)有两个版本：

  1. 优化版本（可能是您正在查看的那个），即找到 TSP 的最佳解决方案。这不是一个决策问题，因此不能在 NP 中，但是在 NP-hard 中，可以通过Hamiltonian Path reduction来证明。因此，这不是一个 NP 完全问题。
  2. 决策版本 - 给定一个整数 K，是否有一条路径通过长度 < K 的图中的每个顶点？这是一个决策（是/否）问题，并且可以在多项式时间内验证解决方案（只需遍历路径并查看它是否触及每个顶点），因此它在 NP 中，但它也在 NP-hard 中（通过与上述相同的证明）。由于它满足 NP 完全性的两个要求，因此它是一个 NP 完全问题。
于 2016-07-28T21:00:43.813 回答
5

NP-hardness 和 NP-completeness 的定义相关但不同。具体来说，如果 NP 中的每个问题在多项式时间内都归结为该问题，则该问题是 NP-hard；如果问题在 NP 中既是 NP-hard 又是其自身，则该问题是 NP-complete。

NP 类包括决策问题，即有是/否答案的问题。结果，TSP 不能在 NP 中，因为预期的答案是一个数字，而不是是或否。因此，TSP 可以是 NP 难的，但不能是 NP 完全的。

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

现在，您可以通过将问题从“最便宜的路径是什么？”更改为 TSP 并将其转换为决策问题。到“是否有一条成本为 X 或更少的路径？”，后一种表述是 NP 的，也恰好是 NP 完全的。

于 2016-07-28T20:55:21.743 回答