爲了證明某些事情是NP難的，爲什麼你需要從NP-complete中減少它？

Question

維基百科：

的問題H是NP-hard的當且僅當有一個NP完全問題L，該多項式時間圖靈還原爲H（即，L≤TH）。

爲什麼問題（稱爲W）從需要減少到NP-complete？爲什麼它不能成爲NP-hard？看起來好像你在乎W是「硬」而不是NP。

想法？

Answer 1

它可以。事實上，你的第二段意味着第一段。

假設NP難問題H可以多項式還原爲問題X.根據定義，存在一個NP-完全問題C，它可以多項式化爲H.因爲兩個約簡都是多項式的，所以可以在多項式時間中將C簡化爲X 。因此，在多項式時間內NP完全問題C可簡化爲X.因此，問題X是NP難的。

Answer 2

如果你可以多項式地減少一個NP難題到你的問題，這足以證明你的問題的NP硬度。然而，一個特定的NP難問題可能不是多項式可降解的，即使它本身就是NP難題。此外，您不必通過減少證明NP硬度，也可以直接證明它。