一个无法决定的问题等同于说它是NP-hard吗？

Question

我知道如何证明停顿问题是不可决定的。然而，我搞不懂为什么它是NP难的。一个无法决定的问题等同于说它是NP-hard吗？

Answer 1

如果存在从每个NP问题到它的多时间简化，则称一个问题是"NP-hard“的。

停机问题确实是NP难的，原因如下：

假设L是NP问题，因为L在NP中，所以它是可决定的-因此有一个确定性的图灵机来决定L，记为M。现在我们可以创建M'，它模拟M并停止i.f.f M接受x(其中x是输入)。并且输入x的减少的结果是(M'，x)。

表示还原为R，实际上x在LI.F.F中，R(x)在H中。

(M(x) =1 => M'(x)使=> (M'，x)在H中停止。

M(x) =0 => M'(x)不会停止=> (M'，x)不在H中)

为什么是约化多项式？描述M的大小可能非常大，但它是固定的。因此，创建M‘需要恒定的时间(可以将其视为M’在R中被“硬编码”)，因此缩减是线性的，因此是多项式的。

由于归约的传递性(即，如果存在从L1到L2和从L2到L3的(多项式/计算性)归约(必须是相同的归约类型！)从L1到L3)这足以证明从一个已知的NP-hard问题到一个新的问题的简化，以证明新的问题是NP-hard的，这是通常的方法。在这个例子中，直接从定义中证明是很方便的。

至于你的另一个问题，答案是否定的。存在一个不是NP-hard的不可判定问题。你可以在这里看到一个证明：https://math.stackexchange.com/questions/642726/are-all-undecidable-problems-np-hard

请注意，如果为P=NP，则所有问题(除了平凡集)都是NP难的。所以证明假设P != NP。