复杂性理论
为什么NP-hard不等于NP-complete？
我对使用的定义的非正式理解：
NP - 可以在多项式时间内验证的所有问题
NP-complete - NP和NP都是难题
NP-hard - 至少和NP中最难的问题一样困难
决策问题 - 一个问题，关于输入问题，并输出一个布尔值
混乱：
P与NP未知解的问题是由于我们不能证明或否定NP中的所有问题都可以在多项式时间内解决的事实。 感觉类似的问题来自NP-complete vs NP-hard。 我们如何知道NP-hard中的所有问题都不能在多项式时间内验证，从而导致NP-hard = NP-complete？
这是我的推理线
从在线研究的角度来看，这似乎与决策问题有关（这是一个我完全陌生的概念，但似乎很简单）。 我认为这意味着NP中的问题具有互补性的决策问题，即问问题的输入是否是解决问题的方法。 假设问题是找到最佳解决方案。 我相信补充决策问题是“给定的输入是最优解？”，我相信如果这个决策问题在多项式时间内是可验证的，那么问题就是NP完全问题（或在NP中）。 所以这意味着非NP完全问题的NP难问题是那些没有决策问题的问题（我认为从来都不是这样，因为任何强力解决方案都可以回答这个问题），或者问题是NP难题而不是NP - 完整的，如果它有一个在多项式时间内无法验证的决策问题。 如果是后者，那么感觉就像我们有P和NP相同的问题。 也就是说，我们如何确认NP中的所有决策问题 - 很难没有多项式时间解决方案？
对不起，如果上述措辞很奇怪。 我会尝试澄清我的问题中的任何混淆。
笔记
我对直观的解释和正式的解释都感兴趣（证明它是一个复杂的答案）。 正式的解释当然可以链接到一篇学术论文。 我不希望任何人投入大量的时间来进行过度复杂的证明，这可能超出我的理解范围（我发现复杂性理论变得非常迅速......复杂）。
如果为了解释起见，我已经完成了关于旅行推销员问题的工作，并且我正在为护士调度问题撰写论文（我相信这些是NP难题）。
NP-Hard包括所有问题，其解决方案可用于推导NP中存在多项式开销问题的解决方案。
这包括许多不在NP中的问题。 例如，暂停问题 - 一个不可判定的问题 - 是NP-Hard，因为NP中的任何问题都可以在多项式时间内减少到它：
上一篇: complexity theory