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問題。