scheduling - NP困難だがNPCではない

Question

問題がNP困難であるというスケジューリング問題をいくつか見ました。私の質問は、1）問題がNP困難であると言うとき、それはNPにないことを意味しますか？それがNPである場合、問題はNP完全であると言うからです。a）NPにある場合b）NP困難である場合、問題はNPCにあることを私は知っています。

Answer 1

問題が NP Hard の場合、それは NP にある可能性があります (その場合は NP 完全です) が、NP にない可能性もあります。以下は、これらのクラスのベン図です。