Question

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.

Was it helpful?

Solution

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:

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top