如何证明E_tm = {M | M是一个图灵机，它不接受}是NP-Hard？

Question

我不知道如何开始。 我的想法是从一些NP完全问题提供多时间减少。 E_tm

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

Answer 1

解决方案：

DF：一个问题是NP难的，如果在NP的所有问题都多项式时间还原到它，甚至thoughit可能不是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接受w如果M“拒绝所有输入。 让我们来确认一下。首先假定M接受w，那么M“拒绝任何输入，因此L（M”）=空。 现在假设M拒绝w，那么M“接受，因此L（M”）不是空的。 请注意，构造M“需要多项式时间。 这就完成了证明。