time-complexity - 关于旅行商问题中 NP-hard 和 NP-Complete 的混淆

Question

旅行商优化(TSP-OPT)是一个 NP-hard 问题，而旅行商搜索(TSP)是一个 NP-完全问题。然而，TSP-OPT 可以简化为 TSP，因为如果 TSP 可以在多项式时间内求解，那么 TSP-OPT(1) 也可以。我认为将 A 简化为 B，B 必须和 A 一样硬。正如我在下面的引用资料中所见，TSP-OPT 可以简化为 TSP。 TSP-OPT 应该比 TSP 更难。我很迷惑...

引用文献:(1)算法，Dasgupta，Papadimitriou，Vazirani 练习 8.1 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf https://cseweb.ucsd.edu/classes/sp08/cse101/hw/hw6soln.pdf

http://cs170.org/assets/disc/dis10-sol.pdf

Answer 1

我快速浏览了您提供的引用资料，我必须承认，您的教科书(第 1 版 pdf)中有一点我非常不喜欢:它们解决了 NP 完整性问题，而几乎没有提到决策问题。提供的 NP 完全问题的定义也与我对教科书的期望有所不同。我认为这是一个有意识的决定，使介绍更具吸引力......

我将提供一个简短的答案，然后是有关相关概念的更详细的解释。

精简版

直观地(和非正式地)，问题在于 NP 如果容易验证 它的解决方案。

另一方面，问题是 NP-hard 如果难以解决，或者查找 一个办法。

现在，如果一个问题既是 NP 又是 NP-hard，那么它就是 NP 完全的。因此，您有两个关键的、直观的 NP 完整性属性。易易验证 ，但很难查找 解决方案。

尽管它们看起来很相似，但验证和寻找解决方案是两件不同的事情。当您使用缩减参数时，您正在查看是否可以找到解决方案。在这方面，TSP 和 TSP-OPT 都是 NP-hard，很难找到它们的解决方案。实际上，第三个pdf提供了您教科书8.1练习的解决方案，这直接表明TSP和TSP-OPT同样难以解决。

现在，TSP 和 TSP-OPT 之间的一个主要区别是前者是(你教科书所说的)搜索问题，而后者是优化问题。验证搜索问题的解决方案的概念是有道理的，在 TSP 的情况下，这很容易做到，因此它是 NP 完全的。对于优化问题，验证解的概念变得很奇怪，因为如果不首先计算最优解的大小，我想不出任何方法，这大致相当于解决问题本身。由于我们不知道验证 TSP-OPT 解的有效方法，我们不能说它是 NP，因此我们不能说它是 NP 完全的。 (在详细解释中有更多关于这个主题的信息。)

tl;dr 是 TSP-OPT 既难验证又难求解，而对于 TSP 来说验证容易又难求解。
归约参数仅在寻找解决方案时有用，因此在验证解决方案时您需要其他参数来区分它们。

更多细节

你的教科书非常简短的一件事是决策问题是什么。
形式上，NP 完备性、NP 硬度、NP、P 等的概念是在决策问题的背景下发展起来的，而不是优化或搜索问题。

以下是这些不同类型问题之间差异的快速示例。

决策问题是一个答案为 的问题。是 或 否 .

TSP decision problem

Input: a graph G, a budget b

Output: Does G admit a tour of weight at most b ? (YES/NO)

这是搜索版本

TSP search problem

Input: a graph G, a budget b

Output: Find a tour of G of weight at most b, if it exists.

现在是优化版本

TSP optimization problem

Input: a graph G

Output: Find a tour of G with minimum weight.

脱离上下文，TSP 问题可以指任何这些。我个人所说的 TSP 是决策版本。这里你的教科书使用 TSP 作为搜索版本，使用 TSP-OPT 作为优化版本。

这里的问题是这些不同的问题是严格不同的。决策版本只要求存在，而搜索版本要求更多，它需要一个这样的解决方案的例子。在实践中，我们往往希望有实际的解决方案，因此更实际的方法可能会省略提及决策问题。

现在呢？ NP 完全问题的定义适用于决策问题，因此从技术上讲，它并不直接适用于搜索或优化问题。但是因为它背后的理论定义明确且有用，所以仍然将术语 NP-complete/NP-hard 应用于搜索/优化问题很方便，以便您了解这些问题的解决难度。因此，当有人说旅行商问题是 NP 完全问题时，形式上它应该是问题的决策问题版本。

显然，许多概念可以扩展，以便它们也涵盖搜索问题，这就是您的教科书中所呈现的方式。决策、搜索和优化之间的差异正是练习 8.1 和 8.2 试图在教科书中涵盖的内容。这些练习可能旨在让您对这些不同类型问题之间的关系以及它们之间的关系感兴趣。