NP很難但不是NPC

Question

我已經看到幾個調度問題，說問題是NP難。我的問題是， 1）當我們說一個問題是NP很難，這是否意味着它不在NP？因爲如果它是NP，我們說這個問題是NP完全的。 我知道一個問題是在NPC中，如果 a）它在NP b）NP難。

Answer 1

如果問題是NP難度，它可能在NP（那麼它是NP完整的），但它也可能不在NP中。以下是這些類別的維恩圖：