TSP NP-Hard怎么样？

Question

我在SO的答案中读到以下内容:

通常提出的旅行推销员问题是找到连接所有城市的最便宜的路线.这不是决策问题,我们无法直接验证任何建议的解决方案.我们可以将其重申为一个决策问题:给定成本C,是否有比C便宜的路线？这个问题是NP完全的,通过一些工作,我们可以像修改的NP完全形式一样轻松地解决原始TSP.因此,TSP是NP难的,因为它至少与NP完全问题一样难.

我知道TSP是NP-Complete但问题是NP-Hard？我读到NP中但不是P中的问题是NP-Hard.我无法将此事与TSP联系起来.请解释一下.

Answer 1

NP-Hard问题是NP中的每个问题都有多项式时间(Cook或Karp,多个定义)减少的问题.这些可能包含不在NP中的问题,实际上甚至不需要包含可确定的问题(如停止问题).

NP完全问题是NP中的那些也是NP-Hard的问题.

如果P不等于NP,则NP中存在无限多的问题,既不是P,也不是NP完全(Ladner定理).