旅行商问题中 NP-hard 和 NP-Complete 的混淆
Confusion about NP-hard and NP-Complete in Traveling Salesman problems
旅行商优化 (TSP-OPT) 是一个 NP 难问题，旅行商搜索 (TSP) 是 NP 完全问题。然而，TSP-OPT 可以简化为 TSP，因为如果 TSP 可以在多项式时间内求解，那么 TSP-OPT(1) 也可以。我想把 A 简化为 B，B 必须和 A 一样硬，如果不比 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
精简版
决策问题是 NP 完全问题，因为您可以为解决方案提供多项式时间验证器，以及汉密尔顿循环问题在多项式时间内可简化为 TSP_DECIDE 的事实。
但是，优化问题严格来说是 NP 难的，因为即使 TSP_OPTIMIZE 可以在多项式时间内从哈密尔顿 (HAM) 循环问题中归约，您也没有一个多时间验证器来声明一个哈密尔顿循环C，无论是否最短，因为你只需枚举所有可能性（这会消耗阶乘阶数space & 时间）。
给定的参考定义是，瓶颈 TSP
瓶颈旅行商问题（瓶颈TSP）是离散或组合优化中的一个问题。问题是在加权图中找到哈密顿循环，该循环最小化循环中最有权重的边的权重。
已知该问题是 NP-hard 问题。这个决策问题版本 "for a given length x is there a Hamiltonian cycle in a graph G with no edge longer than x?" 是 NP 完全的。 NP 完备性紧随找到哈密顿循环问题的归约。
这个问题可以通过对最小的x进行二分查找或者顺序查找使得权重最大为x的边的子图有一个哈密顿环来解决。 此方法得到的解的 运行 时间仅比找到哈密顿循环的时间大一个对数因子 。
长版
错误的是说TSP是NP完全的。事实是 TSP 是 NP 难的。让我解释一下：
The TSP is a problem defined by a set of cities and the distances
between each city pair. The problem is to find a circuit that goes
through each city once and that ends where it starts. This in itself
isn't difficult. What makes the problem interesting is to find the
shortest circuit among all those that are possible.
解决这个问题很简单。只需要计算所有可能电路的长度，然后保留最短的一个。问题是此类电路的数量随着城市数量的增加而迅速增长。如果有 n 个城市，那么这个数字是 n-1 = (n-1)(n-2)...3.2.
的阶乘
如果一个问题可以很容易地（在多项式时间内）检查所提出的解决方案确实是一个解决方案。
这是诀窍。
为了检查提议的游览是否是 TSP 的解决方案，我们需要检查两件事，即
- 每个城市只被访问一次
- 没有比我们正在检查的旅行更短的旅行了
我们没有检查第二个条件！第二个条件是问题难以解决的原因。到今天为止，还没有人找到在多项式时间内检查条件 2 的方法。据我们所知，这意味着 TSP 不在 NP 中。
因此，据我们所知，TSP 不是 NP 完全的。只能说TSP是NP hard。
当他们写 TSP 是 NP 完全时，他们的意思是以下决策问题（yes/no 问题）是 NP 完全：
TSP_DECISION ：给定一个数字 L，一组城市，以及所有城市对之间的距离，是否有一个游览每个城市恰好一次的长度小于比 L?
这个问题确实是 NP 完全问题，因为很容易（多项式时间）检查给定的游览是否导致对 TSPDECISION 的肯定回答。
我快速浏览了您提供的参考资料，我必须承认在您的教科书（第 1 pdf）中有一点我非常不喜欢：它们解决了 NP 完整性问题，但几乎没有提到 决策问题。提供的 NP 完全问题的定义也有些偏离我对教科书的期望。我认为这是使介绍更具吸引力的有意识的决定...
我将提供一个简短的答案，然后对相关概念进行更详细的解释。
简短版
直觉上（和非正式地），问题是在 NP 如果很容易 verify 其解决方案。
另一方面，一个问题是NP-hard如果很难解决，或者find 一个解决方案。
现在，如果一个问题既是 NP 又是 NP-hard，那么它就是 NP-complete。因此，NP 完整性有两个关键的、直观的属性。容易验证，但很难找到解决方案。
虽然看起来很相似，但验证和寻找解决方案是两回事。当您使用缩减参数时，您正在查看是否可以找到解决方案。在这方面，TSP 和 TSP-OPT 都是 NP-hard，很难找到它们的解决方案。其实第三个pdf提供了你课本习题8.1的解法，直接说明TSP和TSP-OPT等价难解
现在，TSP 和 TSP-OPT 之间的一个主要区别是前者是（您的教科书所说的）搜索问题，而后者是优化问题。验证搜索问题的解决方案的概念是有道理的，在 TSP 的情况下，这很容易做到，因此它是 NP 完全的。对于优化问题，验证解决方案的想法变得很奇怪，因为如果不首先计算最优解的大小，我想不出任何方法来做到这一点，这大致相当于解决问题本身。由于我们不知道验证 TSP-OPT 解决方案的有效方法，我们不能说它在 NP 中，因此我们不能说它是 NP-complete。 （更多关于这个主题的详细解释。）
tl;dr就是TSP-OPT既难验证又难求解，而TSP易验证难求解。
归约参数仅在寻找解决方案时有帮助，因此在验证解决方案时，您需要其他参数来区分它们。
更多详情
您的教科书非常简短的一件事是 决策问题 是什么。
形式上，NP 完整性、NP 硬度、NP、P 等概念是在决策问题的背景下发展起来的，而不是优化或搜索问题。
下面是这些不同类型问题之间差异的简单示例。
决策问题的答案是 YES 或 NO.
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 应用于 search/optimization 问题很方便，这样您就可以了解这些问题的解决难度。所以当有人说旅行商问题是NP-complete时，形式上应该是决策问题版本的问题。
显然，许多概念都可以扩展，以便它们也涵盖搜索问题，这就是它在教科书中的呈现方式。决策、搜索和优化之间的区别正是练习 8.1 和 8.2 试图在教科书中涵盖的内容。这些练习可能是为了让您对这些不同类型的问题之间的关系以及它们之间的关系感兴趣。
旅行商优化 (TSP-OPT) 是一个 NP 难问题，旅行商搜索 (TSP) 是 NP 完全问题。然而，TSP-OPT 可以简化为 TSP，因为如果 TSP 可以在多项式时间内求解，那么 TSP-OPT(1) 也可以。我想把 A 简化为 B，B 必须和 A 一样硬，如果不比 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
精简版
决策问题是 NP 完全问题，因为您可以为解决方案提供多项式时间验证器，以及汉密尔顿循环问题在多项式时间内可简化为 TSP_DECIDE 的事实。
但是，优化问题严格来说是 NP 难的，因为即使 TSP_OPTIMIZE 可以在多项式时间内从哈密尔顿 (HAM) 循环问题中归约，您也没有一个多时间验证器来声明一个哈密尔顿循环C，无论是否最短，因为你只需枚举所有可能性（这会消耗阶乘阶数space & 时间）。
给定的参考定义是，瓶颈 TSP
瓶颈旅行商问题（瓶颈TSP）是离散或组合优化中的一个问题。问题是在加权图中找到哈密顿循环，该循环最小化循环中最有权重的边的权重。
已知该问题是 NP-hard 问题。这个决策问题版本 "for a given length x is there a Hamiltonian cycle in a graph G with no edge longer than x?" 是 NP 完全的。 NP 完备性紧随找到哈密顿循环问题的归约。
这个问题可以通过对最小的x进行二分查找或者顺序查找使得权重最大为x的边的子图有一个哈密顿环来解决。 此方法得到的解的 运行 时间仅比找到哈密顿循环的时间大一个对数因子 。
长版
错误的是说TSP是NP完全的。事实是 TSP 是 NP 难的。让我解释一下：
The TSP is a problem defined by a set of cities and the distances between each city pair. The problem is to find a circuit that goes through each city once and that ends where it starts. This in itself isn't difficult. What makes the problem interesting is to find the shortest circuit among all those that are possible.
解决这个问题很简单。只需要计算所有可能电路的长度，然后保留最短的一个。问题是此类电路的数量随着城市数量的增加而迅速增长。如果有 n 个城市，那么这个数字是 n-1 = (n-1)(n-2)...3.2.
的阶乘如果一个问题可以很容易地（在多项式时间内）检查所提出的解决方案确实是一个解决方案。
这是诀窍。
为了检查提议的游览是否是 TSP 的解决方案，我们需要检查两件事，即
- 每个城市只被访问一次
- 没有比我们正在检查的旅行更短的旅行了
我们没有检查第二个条件！第二个条件是问题难以解决的原因。到今天为止，还没有人找到在多项式时间内检查条件 2 的方法。据我们所知，这意味着 TSP 不在 NP 中。
因此，据我们所知，TSP 不是 NP 完全的。只能说TSP是NP hard。
当他们写 TSP 是 NP 完全时，他们的意思是以下决策问题（yes/no 问题）是 NP 完全：
TSP_DECISION ：给定一个数字 L，一组城市，以及所有城市对之间的距离，是否有一个游览每个城市恰好一次的长度小于比 L?
这个问题确实是 NP 完全问题，因为很容易（多项式时间）检查给定的游览是否导致对 TSPDECISION 的肯定回答。
我快速浏览了您提供的参考资料，我必须承认在您的教科书（第 1 pdf）中有一点我非常不喜欢：它们解决了 NP 完整性问题，但几乎没有提到 决策问题。提供的 NP 完全问题的定义也有些偏离我对教科书的期望。我认为这是使介绍更具吸引力的有意识的决定...
我将提供一个简短的答案，然后对相关概念进行更详细的解释。
简短版
直觉上（和非正式地），问题是在 NP 如果很容易 verify 其解决方案。
另一方面，一个问题是NP-hard如果很难解决，或者find 一个解决方案。
现在，如果一个问题既是 NP 又是 NP-hard，那么它就是 NP-complete。因此，NP 完整性有两个关键的、直观的属性。容易验证，但很难找到解决方案。
虽然看起来很相似，但验证和寻找解决方案是两回事。当您使用缩减参数时，您正在查看是否可以找到解决方案。在这方面，TSP 和 TSP-OPT 都是 NP-hard，很难找到它们的解决方案。其实第三个pdf提供了你课本习题8.1的解法，直接说明TSP和TSP-OPT等价难解
现在，TSP 和 TSP-OPT 之间的一个主要区别是前者是（您的教科书所说的）搜索问题，而后者是优化问题。验证搜索问题的解决方案的概念是有道理的，在 TSP 的情况下，这很容易做到，因此它是 NP 完全的。对于优化问题，验证解决方案的想法变得很奇怪，因为如果不首先计算最优解的大小，我想不出任何方法来做到这一点，这大致相当于解决问题本身。由于我们不知道验证 TSP-OPT 解决方案的有效方法，我们不能说它在 NP 中，因此我们不能说它是 NP-complete。 （更多关于这个主题的详细解释。）
tl;dr就是TSP-OPT既难验证又难求解，而TSP易验证难求解。 归约参数仅在寻找解决方案时有帮助，因此在验证解决方案时，您需要其他参数来区分它们。
更多详情
您的教科书非常简短的一件事是 决策问题 是什么。 形式上，NP 完整性、NP 硬度、NP、P 等概念是在决策问题的背景下发展起来的，而不是优化或搜索问题。
下面是这些不同类型问题之间差异的简单示例。
决策问题的答案是 YES 或 NO.
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 应用于 search/optimization 问题很方便，这样您就可以了解这些问题的解决难度。所以当有人说旅行商问题是NP-complete时，形式上应该是决策问题版本的问题。
显然，许多概念都可以扩展，以便它们也涵盖搜索问题，这就是它在教科书中的呈现方式。决策、搜索和优化之间的区别正是练习 8.1 和 8.2 试图在教科书中涵盖的内容。这些练习可能是为了让您对这些不同类型的问题之间的关系以及它们之间的关系感兴趣。