I have seen couple of scheduling problem which says that the problem is NP hard. My question is that 1)when we say a problem is NP hard does it mean that it is not in NP?because if it is NP we say the problem is NP complete. I know that a problem is in NPC if a)it is in NP b)it is NP hard.

有帮助吗?

解决方案

If a problem is NP Hard, it may be in NP(then it's a NP complete), but it could also be not in NP. The following is a Venn diagram of these classes:

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top