NP完全なpr0blemもNPハードですか？

Question

NP完結問題とは、NPとNP困難な問題ですが、問題がNP完全であるという理由だけでNP困難であると主張できます。

例：NP完全問題aを問題bに縮小します。したがって、問題bはNP完全であることが証明されています。実際にそれがNP困難であると言うことはできますか？

Answer 1

のNP完全性の定義は次のとおりです。

QがあればNP完全であり、QはNPであり、QはNP困難である場合にのみ問題。

したがって、はい、NP完全な問題はNPハードであると定義すると、定義上はとなります。あなたがあなたの質問にわずかな虚偽表示を持って

注：

例：私は問題bにNP完全問題aを減らします。したがって、問題bはNP完全であることが証明されています。

上記の結論は、bがNPに表示されている場合のみ有効です。 bがNPよりも「難しい」場合は、でなく、 NP完了です。ただし、この減少はbがNP困難であることを証明するのに十分です。