TSP NP如何？
我在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-hard，但由于尚未知道验证算法，所以尚未知晓它是否在NP中。
TSP问题的决策版本已被证明是NP-complete（NP-NP和NP-hard）。
链接地址: http://www.djcxy.com/p/39995.html上一篇: How is TSP NP