algorithm - 为什么 TSP NP-hard 而 Hamiltonian 路径 NP-complete？

Question

为什么不是这两个问题，即TSP和 Hamiltonian path problem , 都是 NP-complete?

它们看起来一模一样。

Answer 1

要使问题 X 成为NP-complete，它必须满足:

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

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

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