「P（polynomial）問題」代表我們目前使用的電腦等運算機器可不使用暴力法、而改用更高效率演算法處理的問題；而「NP（non-deterministic polynomial）問題」則是目前只能用暴力法處理的問題。究竟「NP 問題」是否等於「P 問題」，目前仍沒有確切的答案。

圖靈機（turning machine）

要更深入理解「P 問題」與「NP 問題」真正的意義，需先對「圖靈機（turning machine）」概念有基礎認識。

圖靈機概念圖（取自維基百科）
「圖靈機」是抽象化的數學邏輯機，可以幫助我們進行運算。若以「圖靈機」為母集合，我們使用的電腦等各類運算機器，都屬於當中的「確定型圖靈機（deterministic turning machine, DTM）」這個子集，而差集就是可以在同一時間平行完成多個運算的「非確定型圖靈機（nondeterministic turning machine, NTM）」。
現在我們分別來看這兩種圖靈機各自的意義：

1. 確定型圖靈機（DTM）：在運算過程中的每個步驟，都只能做一個判斷與決定，我們目前所能生產的所有運算設備皆屬之。
2. 非確定型圖靈機（NTM）：在運算過程中的每個步驟，可以同時做出多個判斷與決定，理論上要有無限個處理器，因此這類圖靈機在現實生活中並不存在。

NTM 因為可以同步處理多個運算，功能比 DTM 更為強大，當 DTM 只能用「超越多項式函數」處理 NP 問題，NTM 卻能以「多項式時間」求解，效能明顯較優。

至於什麼是「多項式時間」與「超越多項式時間」？基本上，可以把前者想成任何合理、不會過長的時間，只要不會呈指數以上爆炸性成長的時間都算，例如 O(n²)、O(n·log n)、O(n)、O(1) 等，而若是 O(2ⁿ)、O(nⁿ) 這類指數以上成長的時間複雜度，就屬於「超越多項式時間」。

在 DTM 中，每一步都只會是一個狀態，最終會有「接受」或「拒絕」任一種結果；在 NTM 中，每一步可以同時有多個狀態，或許會產生很多「拒絕」結果，但只要有一個結果為「接受」，就可以視為最後的結果被圖靈機接受。

這樣講或許有些抽象，可以改用更生活化的情境理解：假設今天有 SQ-879、EK-367、CI-12 這三個航班，我們想知道搭哪個班次可以飛往紐約。

DTM 就像是一般人，要三個航班依序搭過後，才能得到 SQ-879 為「拒絕」、EK-367 為「拒絕」、CI-12 為「接受」這些結果；NTM 就像是有特異功能，只要搭一次，就能得到 SQ-879 為「拒絕」、EK-367 為「拒絕」、CI-12 為「接受」結果。

至於 NTM 要如何搭一次就知道怎麼走到「接受」這個結果？共有兩種想法：

1. 行影分身之術，同時搭上三個航班，就知道哪種結果會被接受。
2. 超級會猜，猜一次就知道什麼結果會被接受。

但就像在現實生活中，並沒有人可以行「影分身之術」，也沒有人永遠都會猜到正確答案，NTM 實務上是做不出來的。

如果某個 NP 問題有解，NTM 可以用多項式時間找到答案（這個過程稱為「猜測（guessing）」），再用多項式時間驗證（verify）答案；即便某個 NP 問題無解，NTM 還是可以用多項式時間給出所有不被接受的結果，再用多項式時間驗證這些答案；另一方面，當 DTM 面對 NP 問題時，只能用超越多項式時間以暴力法求解，但驗證時一樣可以在多項式時間內完成。

精確來說，DTM 是 NTM 的特例，兩者可以解的問題都是一樣的，差別僅在於複雜度。

P 問題 & NP 問題（P Problem & NP Problem）

在演算法課程中，我們能夠學到的演算法包含兩類：

1. 時間複雜度為 O(nᵏ)，k 為常數，代表可用 DTM 在多項式時間內解決，屬於簡單的「P 問題」，例如各類排序法、字串搜尋法等。
2. 時間複雜度為 O(kⁿ)，k 為常數，代表若用目前有的 DTM，會使用超越多項式時間來解，屬於困難的「NP 問題」，例如目前僅能用回溯法求解的 N 皇后問題。

用比較容易懂的方式理解就是：

1. P 問題（P Problem） = 簡單問題 = DTM 可以不用暴力法求解。
2. NP 問題（NP Problem） = 困難問題 = DTM 目前只能用暴力法求解。

數學家與電腦科學家們不禁好奇：這些 NP 問題真的只能用暴力法慢慢解嗎？還是其實有更高效率的演算法，只是我們還沒找到？

這就是 2000 年千禧年大獎難題之一的「P/NP 問題」：

是否存在更高效率的演算法，可使確定型圖靈機以多項式時間求 NP 問題的解？

其答案共有兩種可能：

1. 用 DTM 解 NP 問題只能用暴力法，更有效率的演算法並不存在，即 P≠NP。
2. 用 DTM 處理 NP 問題的更高效率演算法其實存在，只是目前還沒被找到，即 P=NP。

這當中要特別留意的是，「沒找到」並不等於「不存在」，如果能夠證明 P=NP，人類或許有一天就能找到更高效率的演算法，處理目前只能用暴力法慢慢解的 N 皇后問題、旅行推銷員問題等各類 NP 問題。

截至目前為止，P 是否等於 NP 仍是未解之謎。

NP 完全（NP-Complete, NPC）

NP 完全／NP 完備／NPC（NP-complete）問題是 NP 問題的子集合，代表難度最高的 NP 問題。所有的 NP 問題都能夠在多項式時間內化約（reduce）為任何 NPC 問題、任一個 NPC 問題也能夠在多項式時間內化約為另一個 NPC 問題，但 NPC 問題無法化約成 NP 問題。

NPC 問題無法在多項式時間內化約（reduce）成 NP 問題
以上圖來說，A 問題為 NP 問題、B 問題為 NPC 問題，A 問題可以化約為 B 問題，代表若要解 B 問題，難度至少會跟 A 問題一樣高。

化約（reduction ）

所謂「化約」指的是將問題轉換，若有一 X 問題可以「化約」為 Y 問題，代表 Y 問題難度至少會跟 X 問題一樣，只要能用多項式時間解決 Y 問題，就必能用多項式時間解決 X 問題。

NPC 問題屬於難度高的 NP 問題，因此，只要 NP 問題可用 DTM 在多項式時間內化約為 NPC 問題，且能夠找到 DTM 用多項式時間就能解決 NPC 問題的高效率演算法，則 DTM 在處理 NP 問題時，僅需耗費多項式時間。

若 NP 可用多項式時間化約為 NPC、且 NPC 可用多項式時間求解，則 NP 可用多項式時間求解

第一個NPC問題：布林可滿足性問題（Boolean satisfiability problem, SAT ）

根據「古克-李文理論（Cook–Levin theorem）」，布林可滿足性問題（Boolean satisfiability problem, SAT ）問題是第一個 NPC 問題，也就是說，所有的 NP 問題都能夠用 DTM 在多項式時間內化約為 SAT 問題，SAT 問題也能夠在多項式時間內化約為其他的 NPC 問題。

所有 NP 問題都能化約為 SAT 問題，再化約為其他 NPC 問題
SAT 問題問的是：給定一布林代數的「合取範式（CNF）」，是否能給定一組變數賦值，使其結果為真？

要理解這個問題，得先對布林代數運算規則有基本認識。可以簡單將邏輯運算的「且」想成「·」、邏輯運算的「或」想成「+」，因此具有下列規則：

若設 A 為真、B 為假、C 為真，代表 A' 為假、B' 為真、C' 為假，則布林代數運算如下：

(A+B')+C = T

(A+B)·C' = F

上述是已知 A、B、C 分別為真或假的狀況下求布林代數結果，SAT 問題則相反，探討的是在已知布林代數式（即 CNF）的情況下，要如何為 A、B、C 賦值，使最終結果為真。舉例來說，若有下列 CNF：

(A+B')·C

那麼 A、B、C 分別要是真還是假，才可以使最終輸出結果為真呢？

由上表可知，共有下列三種可能：

1. A 為真、B 為真、C 為真
2. A 為真、B 為假、C 為真
3. A 為假、B 為假、C 為真

上述就是用「暴力法」將所有可能性一一列舉，再從最後的八種計算結果中找出為「真」者，而類似這樣的暴力法也是目前用來解決上述 SAT 問題唯一的解法，因此說 SAT 問題是一個 NPC 問題。

其他 NPC 問題範例

1. 背包問題（knapsack problem）
2. 哈密論路徑問題（Hamiltonian path problem）
3. 旅行推銷員問題（travelling salesperson problem, TSP）
4. 子集和問題（subset sum problem）
5. 圖著色問題（graph coloring problem, GCP）

更多範例可參考維基百科。

NP 困難（NP-Hard, NPH）

要驗證上述的 P 問題與 NP 問題是否正確，都能以 DTM 在多項式時間內完成，但如果有些問題困難到連驗證都無法在多項式時間內完成，或者這些問題根本解不出來（如著名的「停機問題（halting problem）」），則稱這些問題為「NP 困難（NP-Hard, NPH）」問題。

所有的 NPC 都屬於「NPH」問題，但除了 NPC 問題外，還有一些問題的難度比 NPC 問題更高，超越 NP 問題的範圍，甚至可能電腦根本就沒辦法解。

P、NP、NPC、NPH 問題關係圖

上圖顯示 P、NP、NPC 與 NPH 四種問題關係圖，越上面代表複雜度越高；左為 P≠NP 時之假設、右為 P=NP 時之假設。

用 DTM 與 NTM 處理 P 問題、NP 問題、NPC 問題與 NPH 問題的比較如下：

參考資料

1. 輕鬆談演算法的複雜度分界：什麼是P, NP, NP-Complete, NP-Hard問題
2. P, NP, NPC問題