如何證明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「需要多項式時間。 這就完成了證明。