big-o - NP完全な問題はNP困難でもありますか?

Question

NP 完全問題は、NP および NP 困難な問題であると言えますが、NP 完全であるという事実だけで、問題が NP 困難であると排他的に主張することはできます。

例: NP 完全問題aをproblem に還元しますb。したがって、問題bは NP 完全であることが証明されました。実際、それも NP 困難であると言えますか?

Answer 1

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

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

したがって、はい、定義上、NP完全問題はNP困難であると最も断言できます。

質問にわずかな誤りがあることに注意してください。

例: NP 完全問題aをproblem に還元しますb。したがって、問題bは NP 完全であることが証明されました。

b上記の結論は、NP であることが示された場合にのみ有効です。が NP よりも「難しい」場合b、それはNP 完全ではありません。ただし、削減はbが NP 困難であることを証明するのに十分であることに注意してください。