我在SO的答案之一中阅读了以下内容：
旅行商问题，正如通常所提出的，是找到连接所有城市的最便宜的路线。这不是决策问题，我们无法直接验证任何提议的解决方案。我们可以将其重述为一个决策问题：给定成本 C，有没有比 C 更便宜的路线？这个问题是 NP 完全的，只需一点点工作，我们就可以像修改后的 NP 完全形式一样简单地求解原始 TSP。因此，TSP 是 NP 难的，因为它至少与 NP 完全问题一样难。
我知道 TSP 是 NP-Complete 但问题是如何 NP-Hard ？我读到NP中但不在P中的问题是NP-Hard。我无法将这件事与 TSP 联系起来。请解释一下。
NP-Hard 问题是 NP 中的每个问题都有多项式时间（Cook 或 Karp，多个定义）归约到的那些问题。这些可能包含不属于 NP 的问题，实际上甚至不需要包含可决定的问题（如停止问题）。
NP-Complete 问题是 NP 中也是 NP-Hard 的那些问题。
如果 P 不等于 NP，则 NP 中存在无限多的问题，它们既不在 P 中，也不是 NP-Complete（Ladner 定理）。
TSP 问题的优化版本已被证明是 NP 难的，但由于尚有已知的验证算法，因此尚不知道它是否在 NP 中。
TSP 问题的决策版本已显示为 NP-complete（in-NP 和 NP-hard）。