npc

NP完全問題

npc,指NP完全問題(Non-deterministic Polynomial complete problem)。簡單的說,如果任何一個NP問題都能通過一個多項式時間演演算法轉換為某個NP問題,那麼這個NP問題就稱為NPC問題。

目錄

正文


第一個被證明是NPC的問題是3SAT問題。
目前為止我們還不能證明NPC問題有多項式演演算法(即NP等於P),也不能證明NPC問題沒有多項式演演算法(即NP不等於P)。
關於更詳細地介紹請參看NP問題。