# 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]