我理解如何证明停顿问题是不可判定的。然而，我很困惑为什么它是NP难。一个问题是不可判定的等同于说它是NP难的吗？
如果从每一个NP问题到它都有一个多时间约简，那么一个问题被称为"NP难"。
停顿问题确实是NP难题，原因如下：
设L是一个NP问题，因为L在NP中，它是可判定的-因此有一个确定的图灵机来决定L，将其表示为M。现在我们可以创建M'，它模拟M并停止i.f.f M接受x(其中x是输入(。并且对输入x进行缩减的结果是(M'，x(。
将还原表示为R，实际上x在L中。f R(x(在H中。
(M(x(=1=>M'(x(暂停=>(M'，x(在H中。
M(x
为什么是归约多项式？M的描述大小可能很大，但它是固定的。因此，创建M'需要恒定的时间(可以将其视为M'在R中被"硬编码"(，因此归约是线性的，因此是多项式的。
由于归约的传递性(即，如果存在从L1到L2和从L2到L3的(多项式/计算(归约(必须是相同的归约类型！(，则有从L1到L3的归约(，足以证明从已知NP难问题到新问题的归约，以证明新问题是NP难问题，这是常见的方法。在本例中，直接从定义上证明是很方便的。
至于你的另一个问题，答案是否定的。存在一个不可判定的问题，它不是NP难的。你可以在这里看到一个证明：https://math.stackexchange.com/questions/642726/are-all-undecidable-problems-np-hard
注意，如果p=NP，则每个问题(除了平凡集(都是NP难的。因此证明假定P！=NP.