非NP完全困難的NP難題更難？

Question

根據我的理解，所有NP完全問題都是NP難題，但是一些NP難題已知不是NP完全問題，而NP難問題至少和NP完全問題一樣困難。

這是不是NP NP完全困難的NP難題？而且它更難嗎？

Answer 1

從http://en.wikipedia.org/wiki/NP-hard#Examples

也有一些是NP-硬而不NP完全性，例如停機問題的決策問題。這是問題：「給定一個程序和它的輸入，它會永遠運行嗎？」這是一個是/否的問題，所以這是一個決策問題。很容易證明暫停問題是NP-hard，但不是NP-complete。

Answer 2

一套NP難問題是一套NP完全問題的超集。有複雜性類比NP更「困難」，例如PSPACE,EXPTIME或EXPSPACE，所有這些包含NP-硬但不是NP-完全問題。

Answer 3

要回答這個問題，首先需要了解哪些NP-難題也是NP-完整的。如果一個NP難題屬於NP集，那麼它是NP完全的。屬於設置NP，一個問題需要是

（ⅰ）一個決策問題，
（II）的解決方案的問題的辦法的數目應是有限的，並且每個解決方案應該是多項式的長度，並
（ iii）給出一個多項式長度的解，我們應該能夠說出問題的答案是否是

現在很容易發現可能存在許多不屬於集合的NP-難問題NP並且很難解決。作爲一個直觀的例子，我們需要找到實際時間表的旅行推銷員的優化版本比旅行推銷員的決策版本更難，我們只需要確定具有長度< = k的時間表是否存在。

Answer 4

圖靈機停機問題是圖靈機NP難，但不是NPC判定的。顯然，這是困難;）

Answer 5

圖靈停機問題是不可判定它屬於NP-硬集。對於turing halting問題，我們沒有任何決定因素，因爲它是一種RE語言。所以我們沒有任何算法來解決它。因此很明顯，無法解決的問題也在NP-Hard集中。因此，NP-Hard集還包含我們沒有任何算法要解決的語言或問題。

Answer 6

1. NP完全問題必須NP和NP難。
2. 和NP-hard不是NP-完全不是NP。
3. 現在NP的定義有人給出問題的答案實例。並有驗證者進行驗證。
4. 這意味着NP-Hard沒有任何一個。因此他們很難解決是真的。