NPC問題

NP-Complete是計算複雜度理論中，決定性問題的等級之一。NPC問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。 著名NPC問題：

變換流程圖。 布林滿足問題 N-puzzle問題 背包問題 漢彌爾頓迴圈問題 旅行推銷員問題 子圖同構問題：（Subgraph isomorphism problem） 子集合加總問題 分團問題 頂點涵蓋問題 獨立頂點集問題：（Independent set problem） 圖著色問題 踩地雷

TSP旅行推銷員問題(Travelling salesman problem)

旅行推銷員問題（英語：Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。