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

圖靈機（turning machine）

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

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

確定型圖靈機（DTM）：在運算過程中的每個步驟，都只能做一個判斷與決定，我們目前所能生產的所有運算設備皆屬之。
非確定型圖靈機（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 要如何搭一次就知道怎麼走到「接受」這個結果？共有兩種想法：

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

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

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

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

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

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

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

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

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

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

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

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

其答案共有兩種可能：

用 DTM 解 NP 問題只能用暴力法，更有效率的演算法並不存在，即 P≠NP。
用 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）」，是否能給定一組變數賦值，使其結果為真？