---
# System prepended metadata

title: NP problems 解釋

---

# NP problems 解釋

![](https://i.imgur.com/p1vjY8C.png)


**P**:Polynomial problems
**NP**:Non-deterministic Polynomial problems
P=NP 與否是八大難題之一
如果P=NP,then P=NP=NP-complete,
但是如果不相等，則P is subset of NP,and NP-Complete is the intersections of NP and NP-Hard problem,且不包含P
![](https://i.imgur.com/ki6b2zs.png)


NP-Complete問題
布林滿足問題
N-puzzle問題（華容道問題）
背包問題
漢彌爾頓迴圈問題
旅行推銷員問題
子圖同構問題：（Subgraph isomorphism problem）
子集合加總問題
分團問題
頂點覆蓋問題：（Vertex cover）
獨立頂點集問題：（Independent set problem）
圖著色問題
踩地雷[2]

