複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/npc/658479
複製
複製成功

npc

（NP完全問題）

鎖定
npc，指NP完全問題（Non-deterministic Polynomial complete problem）。簡單的説，如果任何一個NP問題都能通過一個多項式時間算法轉換為某個NP問題，那麼這個NP問題就稱為NPC問題。
中文名
npc
外文名
Non-deterministic Polynomial complete problem
所屬學科
理論信息學
作    用
計算複雜度理論
在理論信息學中的計算複雜度理論領域裏NPC指NP完全問題（Non-deterministic Polynomial complete problem）。
簡單的説，如果任何一個NP問題都能通過一個多項式時間算法轉換為某個NP問題，那麼這個NP問題就稱為NPC問題。
換言之，如果這個問題解決了，那麼所有NP問題也都能解決了。第一個被證明是NPC的問題是3SAT問題。
我們還不能證明NPC問題有多項式算法（即NP等於P），也不能證明NPC問題沒有多項式算法（即NP不等於P）。
關於更詳細的介紹請參看NP問題。