證明暫停問題是NP-hard？

Question

（對於這個問題，如果這是錯誤的網站，我很抱歉，但考慮到有很多「CS不夠理想」CS理論問題在這裏浮動，我認爲這可能是一個很好的選擇請隨意移動這個，如果它是不恰當的。）

在this answer到約NP，NP難的定義問題，NP完全，傑森使得聲稱

停機問題是經典的NP難題。這是給定程序P和輸入I的問題，它會停止嗎？這是一個決策問題，但它不在NP中。很明顯，任何NP完全問題都可以歸結爲這個問題。

儘管我認爲暫停問題在直覺上是一個比NP更難的「更難」的問題，但我實在不能拿出一個正式的，數學證明暫停問題是NP難的問題。特別是，我似乎無法從NP中的每個問題的實例（或者至少是任何已知的NP完全問題）中找到一個多項式時間多對一映射到停止問題上。

有沒有直接的證據表明暫停問題是NP-hard？

Answer 1

我們首先注意到所有NP完全問題都可以簡化爲3SAT。現在我們有了一個圖靈機，它遍歷所有可能的任務，如果沒有找到滿意的任務，那麼它將永遠運行。當且僅當3SAT實例可滿足時，此機器纔會停止。

完成證明 - 我們可以在多項式時間內將NP完全問題的任何實例都減少爲3SAT。從那裏，我們可以通過將輸入與上述圖靈機器的描述（具有恆定大小）配對來將此問題減少爲停機問題的一個實例。這種配對可以在多項式時間內完成，因爲圖靈機只有恆定的尺寸。然後，如果圖靈機停止在給定的輸入上，如果3SAT實例可滿足，則原始的NP完全問題回答「是」。