NP - Cyan's Notebook

Cyan

2023-12-06

Summary

1
2
3
4
5
6
7
8


____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

* 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问题都能约化到它

浅谈P、NP、NP-Complate和NP-Hard问题 - 知乎 (zhihu.com)