Summary
| Problem Type | Verifiable in P time | Solvable in P time |
|---|---|---|
| P | Yes | Yes |
| NP | Yes | Yes or No * |
| NP-Complete | Yes | Unknown |
| NP-Hard | Yes or No** | Unknown *** |
- Increasing Difficulty
- * An NP problem that is also P is solvable in P time.
- ** An NP-Hard problem that is also NP-Complete is verifiable in P time.
- *** NP-Complete problems (all of which form a subset of NP-hard) might be. The rest of NP hard is not.
computer science - What are the differences between NP, NP-Complete and NP-Hard? - Stack Overflow
P
- 能在多项式时间内解决
NP
- 无法确定是否能在多项式时间内解决
- 能够在多项式时间内验证
NP-Complete
- 它是一个NP问题
- 无法确定是否能在多项式时间内解决
- 能够在多项式时间内验证
- 其他所有属于NP的问题都可以规约成它
NP-Hard
- 不一定是一个NP问题
- 所有的NP问题都能约化到它