Вопрос

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