1

我见过几个调度问题，说这个问题是 NP 困难的。我的问题是 1）当我们说一个问题是 NP 困难时，这是否意味着它不在 NP 中？因为如果它是 NP，我们说这个问题是 NP 完全的。我知道问题出在 NPC 中，如果 a）在 NP 中 b）在 NP 中很难。

4

1 回答 1

1

如果一个问题是 NP Hard，它可能在 NP 中（那么它是一个 NP 完全问题），但它也可能不在 NP 中。以下是这些类的维恩图：

于 2012-12-24T22:59:34.640 回答