为什么NP-hard不等于NP-complete？
My informal understanding of definitions being used:
NP - 可以在多项式时间内验证的所有问题
NP完全 - 所有NP和NP难的问题
NP-hard - 至少和NP中最难的问题一样难
决策问题 - 询问有关输入的问题并输出bool值的问题
Confusion:
P与NP未知解的问题源于这样一个事实，即我们无法证明或反驳NP中的所有问题都可以在多项式时间内求解 . 感觉类似的问题来自NP-complete与NP-hard . 我们如何知道NP-hard中的所有问题都无法在多项式时间内得到验证，从而导致NP-hard = NP-complete？
Here is my line of reasoning
从在线研究来看，区别似乎与决策问题有关（这个概念我完全是新手，但看起来很简单） . 我认为这意味着NP中的问题具有互补的决策问题，询问输入是否是问题的解决方案 . 假设问题是找到最佳解决方案 . 我认为补充决策问题是“给定输入是最优解？”并且我相信如果这个决策问题在多项式时间内是可验证的那么问题是NP完全（或在NP中） . 所以这意味着那些不是NP完全问题的NP难问题就是那些没有决策问题的问题（我认为这是不可能的，因为任何暴力解决方案都可以解决这个问题）或者问题是NP难，而不是NP - 如果它有一个在多项式时间内无法验证的决策问题，则表示已完成 . 如果是后者那么感觉就像P和NP一样有问题 . 也就是说，我们如何确认NP-hard中的所有决策问题都没有多项式时间解？
对不起，如果上面的措辞很奇怪 . 我会尽力澄清我的问题中的任何混淆 .
notes
我对直观的解释和正式的解释感兴趣（证明这是一个复杂的答案） . 正式的解释当然可以成为学术论文的链接 . 我不希望任何人投入大量时间进入过于复杂的证据，这可能超出了我的理解范围（我发现复杂性理论变得非常快......复杂） .
如果它有助于解释我已经完成了旅行商问题的工作，我目前正在编写一份关于护士安排问题的论文（我相信这些是NP难问题） .
1 回答
NP-Hard包括所有问题，其解决方案可用于导出NP中具有多项式开销的问题的解决方案 .
这包括很多NP不存在的问题 . 例如，暂停问题 - 一个不可判定的问题 - 是NP-Hard，因为NP中的任何问题都可以在多项式时间内减少到它：
将NP中的任何问题减少为NP-Complete问题3-SAT的实例
在多项式时间内构造一个TM，它检查所有赋值，如果找到满意的赋值则停止 .
使用暂停问题的解决方案来判断TM是否停止 .
如果它停止，接受;否则，拒绝 .