turing-machines - 如何证明语言 $E_{tm}$ 是 $NP-Hard$

Question

考虑语言 $E_{tm}={ \langle M \rangle: M\text{是一个不接受任何东西的图灵机}$

我什至不知道如何开始。我的想法是从一些 NP - Complete 问题中减少多时间。E_tm

我不明白的是，知道 E_tm 是不可判定的，但 NP-Hard 类是可判定的。

Answer 1

解决方案：

DF：如果 NP 中的所有问题都是多项式时间可归约到它的，那么问题就是 NP 难的，即使它可能不在 NP 本身中（p326 Sipser）（我们书中的唯一定义）。对于任何在 NP 中的语言 L'，如果我们证明我们可以多时间归约到 Etm。这将证明 Etm 是 NP - 难的。由于 L' 根据定义在 NP 中，因此存在一个 TM（NTM，但由于它们在功率上是等效的，所以我写 TM）M' 这样就决定了 L'。

TM M'' that takes as an input <M,w> constructs
TM M' such that
 on arbitrary x
if w = x
  run M on w if accept => reject
                     if reject => accept
else reject.

因此，如果 M'' 拒绝所有输入，则 M 接受 w。让我们确认一下。首先假设 M 接受 w，然后 M'' 拒绝任何输入，因此 L(M'') = 空。现在假设 M 拒绝 w，然后 M'' 接受，因此 L(M'') 不为空。请注意，构建 M'' 需要多项式时间。这样就完成了证明。