我在SO :的一个答案中读到以下内容:
旅行商问题通常被描述为寻找连接所有城市的最便宜路线。这不是一个决策问题,我们无法直接验证任何提出的解决方案。我们可以将其重新表述为决策问题:给定成本C,是否存在一条比C更便宜的路线?这个问题是NP完全问题,通过一些工作,我们可以像解决修改后的NP完全形式一样容易地解决原始的TSP。因此,TSP是NP难问题,因为它至少和NP完全问题一样难。
我理解TSP是NP完全问题,但是它为什么是NP难问题?我读到过在NP中但不在P中的问题是NP难问题。我无法将这件事与TSP联系起来。请解释一下。