NP-complete vs NP-hard（为什么它们不相等？）
NP-complete vs NP-hard (why are they unequal?)
为什么 NP-hard 不等于 NP-complete？
我对所用定义的非正式理解：
NP——所有可以在多项式时间内验证的问题
NP-complete - 所有问题都是 NP 和 NP-hard
NP-hard - 至少和 NP
中最难的问题一样难
决策问题 - 针对输入提出问题并输出布尔值的问题
困惑：
P vs NP未知解的问题是因为我们无法证明或反驳NP中的所有问题都可以在多项式时间内解决。感觉类似的问题来自 NP-complete vs NP-hard。我们如何知道 NP-hard 中的所有问题都无法在多项式时间内得到验证，从而导致 NP-hard=NP-complete？
这是我的推理
从在线研究来看，区别似乎与决策问题有关（我对这个概念很陌生，但看起来很简单）。我认为这意味着 NP 中的问题具有补充决策问题，这些问题询问输入是否是问题的解决方案。假设问题是找到最佳解决方案。我相信互补决策问题是 "is the given input the optimal solution?" 并且我相信如果这个决策问题在多项式时间内是可验证的，那么这个问题就是 NP-complete（或 NP）。所以这意味着不是 NP 完全问题的 NP 难问题是那些没有决策问题的问题（我相信这永远不会是真的，因为任何蛮力解决方案都可以回答这个问题）或者问题是 NP 难而不是 NP -如果它有一个在多项式时间内无法验证的决策问题，则完成。如果是后者，那么感觉就像我们在 P vs NP 中遇到了同样的问题。也就是说，我们如何确认NP-hard中的所有决策问题都没有多项式时间解？
抱歉，如果上面的措辞很奇怪。我会尝试澄清我的问题中的任何混淆。
笔记
我对直观的解释和正式的解释都感兴趣（如果答案很复杂，则提供证据）。正式的解释当然可以是对学术论文的link。我不希望任何人将大量时间投入到可能超出我理解范围的过于复杂的证明中（我发现复杂性理论变得非常快......复杂）。
如果对解释有帮助的话，我已经完成了关于旅行商问题的工作，并且我目前正在写一篇关于护士调度问题的论文（我相信这些是 NP-hard 问题）。
NP-Hard 包括所有问题，其解决方案可用于导出具有多项式开销的 NP 问题的解决方案。
这包括许多不在 NP 中的问题。例如，停机问题 - 一个不可判定的问题 - 是 NP-Hard，因为 NP 中的任何问题都可以在多项式时间内简化为它：
- 将 NP 中的任何问题简化为 NP 完全问题 3-SAT 的实例
- 在多项式时间内构造一个 TM，它检查所有分配并在找到满意的分配时停止。
- 使用停机问题的解决方案判断 TM 是否停机。
- 如果停止，接受；否则，拒绝。
为什么 NP-hard 不等于 NP-complete？
我对所用定义的非正式理解：
NP——所有可以在多项式时间内验证的问题
NP-complete - 所有问题都是 NP 和 NP-hard
NP-hard - 至少和 NP
中最难的问题一样难决策问题 - 针对输入提出问题并输出布尔值的问题
困惑：
P vs NP未知解的问题是因为我们无法证明或反驳NP中的所有问题都可以在多项式时间内解决。感觉类似的问题来自 NP-complete vs NP-hard。我们如何知道 NP-hard 中的所有问题都无法在多项式时间内得到验证，从而导致 NP-hard=NP-complete？
这是我的推理
从在线研究来看，区别似乎与决策问题有关（我对这个概念很陌生，但看起来很简单）。我认为这意味着 NP 中的问题具有补充决策问题，这些问题询问输入是否是问题的解决方案。假设问题是找到最佳解决方案。我相信互补决策问题是 "is the given input the optimal solution?" 并且我相信如果这个决策问题在多项式时间内是可验证的，那么这个问题就是 NP-complete（或 NP）。所以这意味着不是 NP 完全问题的 NP 难问题是那些没有决策问题的问题（我相信这永远不会是真的，因为任何蛮力解决方案都可以回答这个问题）或者问题是 NP 难而不是 NP -如果它有一个在多项式时间内无法验证的决策问题，则完成。如果是后者，那么感觉就像我们在 P vs NP 中遇到了同样的问题。也就是说，我们如何确认NP-hard中的所有决策问题都没有多项式时间解？
抱歉，如果上面的措辞很奇怪。我会尝试澄清我的问题中的任何混淆。
笔记
我对直观的解释和正式的解释都感兴趣（如果答案很复杂，则提供证据）。正式的解释当然可以是对学术论文的link。我不希望任何人将大量时间投入到可能超出我理解范围的过于复杂的证明中（我发现复杂性理论变得非常快......复杂）。
如果对解释有帮助的话，我已经完成了关于旅行商问题的工作，并且我目前正在写一篇关于护士调度问题的论文（我相信这些是 NP-hard 问题）。
NP-Hard 包括所有问题，其解决方案可用于导出具有多项式开销的 NP 问题的解决方案。
这包括许多不在 NP 中的问题。例如，停机问题 - 一个不可判定的问题 - 是 NP-Hard，因为 NP 中的任何问题都可以在多项式时间内简化为它：
- 将 NP 中的任何问题简化为 NP 完全问题 3-SAT 的实例
- 在多项式时间内构造一个 TM，它检查所有分配并在找到满意的分配时停止。
- 使用停机问题的解决方案判断 TM 是否停机。
- 如果停止，接受；否则，拒绝。