TSP为什么是NP难问题？

Question

TSP为什么是NP难问题？

3

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

旅行商问题通常被描述为寻找连接所有城市的最便宜路线。这不是一个决策问题，我们无法直接验证任何提出的解决方案。我们可以将其重新表述为决策问题：给定成本C，是否存在一条比C更便宜的路线？这个问题是NP完全问题，通过一些工作，我们可以像解决修改后的NP完全形式一样容易地解决原始的TSP。因此，TSP是NP难问题，因为它至少和NP完全问题一样难。

我理解TSP是NP完全问题，但是它为什么是NP难问题？我读到过在NP中但不在P中的问题是NP难问题。我无法将这件事与TSP联系起来。请解释一下。

- Suhail Gupta

2个回答

3

TSP问题的优化版本已被证明为NP难问题，但因为没有已知的验证算法，所以不确定其是否属于NP。

TSP问题的决策版本已被证明为NP完全问题（既是NP困难问题又在NP中）。

- CrepuscularV

优化版本和决策版本有什么区别？ - MTA

1

@RegUser 优化版本寻找答案：最小成本是多少？为了验证这一点，我们需要检查每条路线，但这不是多项式时间。决策版本是：是否存在任何低于成本K的路径？我们可以在多项式时间内验证最后一个问题。 - PeerNet

@MTA - 结果。决策=布尔值或优化=数值型。 - pds

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Trixter · Accepted Answer

NP-Hard问题是指每个NP问题都可以通过多项式时间（Cook或Karp，多种定义）约简得到的问题。这些问题可能包含不在NP中的问题，实际上甚至不需要包含可决定问题（如停机问题）。

NP完全问题是指NP中也属于NP-Hard的问题。

如果P不等于NP，则NP中有无限多个问题既不属于P，也不属于NP-Complete（Ladner定理）。