在數學中，類別（class）是一群具有某種相似屬性的物件。

例如所有能在 O(n²) 時間內解決的計算問題構成一個類別，複雜度理論家簡記為 TIME(n²)；TIME(n³) 是能在 O(n³) 內解決的問題類別，依此類推。

由於超級電腦能算的東西筆電也能算，任何能在 O(n²) 內解決的問題也能在 O(n³) 內解決。因此 TIME(n²) 中的任何問題也屬於 TIME(n³)，兩者也都屬於 TIME(n⁴)……

所有 TIME(n^k) 類別（k 為常數）的聯集稱為 P，代表 polynomial time（多項式時間）。

空間複雜度#

如果你寫過程式，就知道看似很快的演算法仍可能吃光系統記憶體而讓它崩潰。選擇演算法時，你不只該考慮時間複雜度，也該考慮它用掉多少記憶體，也就是空間複雜度。

這特別重要，因為在 CPU 中，一次記憶體存取通常比一次基本算術運算慢上數個數量級。

形式上，你可以像定義時間複雜度那樣，把演算法的記憶體消耗定義成輸入長度 n 的函式：

• SPACE(f(n))：能用 f(n) 位元記憶體解決的問題類別。
• PSPACE：所有 SPACE(n^k) 問題的聯集。

顯然記憶體越少越好，但多項式量的記憶體並不必然意味著演算法實用。

以暴力金鑰搜尋為例：它只需要微不足道的記憶體，卻慢得要命。更一般地說，即使只用幾個位元組的記憶體，一個演算法仍可能跑到天荒地老。

兩者的關係#

任何能在 f(n) 時間內解決的問題，最多需要 f(n) 記憶體，所以 TIME(f(n)) 包含於 SPACE(f(n))。

原因是：在 f(n) 時間內你最多只能寫入 f(n) 個位元（假設寫入或讀取 1 位元花 1 個時間單位）。

結果是：P 是 PSPACE 的子集。

非確定性多項式時間（NP）#

NP 是繼 P 之後第二重要的複雜度類別。

NP 不是 non-polynomial time（非多項式時間）的縮寫，而是 nondeterministic polynomial time（非確定性多項式時間）。

這裡的「驗證」是指：給定一個候選解，你可以跑某個多項式時間演算法來確認它是否真的是解。

例子與反例#

在 NP 中：已知明文下還原秘密金鑰的問題。給定 P、C = E(K, P) 與某個候選金鑰 K₀，你可以驗證 E(K₀, P) 是否等於 C 來檢查 K₀ 是否正確。找到候選金鑰的過程無法在多項式時間內完成，但檢查金鑰是否正確可以。

不在 NP 中（反例一）：已知密文攻擊。這次你只拿到一些對隨機未知明文 P 的 E(K, P) 值。若你不知道那些 P 是什麼，就沒有辦法驗證候選金鑰 K₀ 是否正確。因此已知密文攻擊下的金鑰還原問題不在 NP 中（更不用說 P 了）。

不在 NP 中（反例二）：驗證某問題不存在解。驗證一個解正確，歸結為把候選解當輸入跑某個演算法並檢查回傳值。然而要驗證沒有解存在，你可能得走遍所有可能的輸入——若輸入有指數多個，你就無法有效率地證明無解。

對 NP 中最難的問題——所謂的 NP-complete 問題——而言，「不存在解」特別難以證明。

NP-complete 問題#

NP 類別中最難的問題稱為 NP-complete；我們不知道如何在多項式時間內解決它們。

1970 年代複雜度理論家發展 NP-completeness 理論時發現：NP 中最難的問題全都一樣難。

這是藉由「證明任何 NP-complete 問題的有效率解法，都能被轉換成任何其他 NP-complete 問題的有效率解法」來證明的。

換句話說：若你能有效率地解決任何一個 NP-complete 問題，你就能解決所有 NP-complete 問題，以及 NP 中的所有問題。

NP-complete 問題以不同的偽裝出現，但從數學角度看它們本質上相似——事實上，你可以把任何 NP-complete 問題歸約到任何其他 NP-complete 問題。

幾個例子#

• 旅行推銷員問題：給定地圖上一組點（城市、地址或其他地理位置）與各點之間的距離，找出一條走訪每個點、且總距離小於給定距離 x 的路徑。
• 團問題（clique problem）：給定一個數 x 與一個圖（由邊連接的節點集合），判定是否存在一組 x 個或更少的點，使所有點兩兩相連。
• 背包問題：給定兩個數 x 與 y，以及一組各有已知價值與重量的物品，能否挑出一組物品使總價值至少為 x、總重量至多為 y？

NP-complete 問題無所不在——從排程問題（給定有優先權與時長的工作與一個或多個處理器，在尊重優先權的同時最小化總執行時間）到約束滿足問題（找出滿足一組數學約束的值）。

連某些電玩的通關任務都能被證明是 NP-complete（包括俄羅斯方塊、超級瑪利歐兄弟、寶可夢與 Candy Crush Saga）。例如論文〈Classic Nintendo Games Are (Computationally) Hard〉（https://arxiv.org/abs/1203.1895 ^↗）就探討「可達性的決定問題」——判定能否從某個特定起點抵達目標點。

NP-hard#

某些電玩問題其實比 NP-complete 更難，稱為 NP-hard。

一個問題是 NP-hard，若它至少與 NP-complete 問題一樣難。更形式地說：若解決它所需的東西可以被證明也能解決 NP-complete 問題。

一個重要但書#

某些特定實例因為規模小、或因為具有特定結構，可能可以有效率地解決。

例如看一個小的團問題圖，你盯個幾秒就能找出那個團——儘管團問題是 NP-hard 的，這裡並沒有什麼困難之處。

所以 NP-complete 不代表某問題的所有實例都困難，而是隨著問題規模增長，許多實例會變得困難。

P vs. NP 問題#

若你能在多項式時間內解決最難的 NP 問題，你就能在多項式時間內解決所有 NP 問題，因此 NP 就會等於 P。

這聽起來很荒謬——難道不是顯然存在「解答容易驗證卻難以找到」的問題嗎？例如，指數時間的暴力破解不是顯然就是還原對稱密碼金鑰最快的方法，因此該問題不可能在 P 中嗎？

結果是：儘管聽起來瘋狂，至今沒有人證明 P 不同於 NP——即使有整整一百萬美元的懸賞。

克雷數學研究所會把這筆獎金頒給任何證明 P ≠ NP 或 P = NP 的人。這個被稱為 P vs. NP 的問題，被知名複雜度理論家 Scott Aaronson 稱為「人類曾提出過最深刻的問題之一」。

想想看：若 P 等於 NP，那麼任何容易驗證的解也都容易找到。

實務上使用的所有密碼學都會變得不安全——因為你可以有效率地還原對稱金鑰、反轉雜湊函式。

但別驚慌#

多數複雜度理論家相信 P 不等於 NP，因此 P 是 NP 的真子集，而 NP-complete 問題是 NP 中另一個與 P 不重疊的子集。

換句話說：看起來困難的問題確實困難，只是這件事很難用數學證明。

證明 P = NP 只需要為某個 NP-complete 問題找出一個多項式時間演算法，而證明這種演算法不存在則從根本上困難得多。

這並未阻止一些古怪的數學家提出簡單的證明——那些證明通常明顯是錯的，但常常讀來有趣。例子見〈The P-versus-NP page〉：https://www.win.tue.nl/~gwoegi/P-versus-NP.htm ^↗。

為什麼密碼學不用 NP-complete 問題#

既然我們幾乎確信困難問題確實存在，何不利用它們建構強大、可證明安全的密碼學？想像一個證明說「破解某密碼是 NP-complete」，因此只要 P ≠ NP，該密碼就牢不可破。

但現實令人失望：NP-complete 問題已被證明難以用於密碼學目的——因為那個讓它們一般而言困難的結構，在特定情況下反而會讓它們變得容易，而那些特定情況有時正好會在密碼學中出現。

因此密碼學往往依賴的是大概不是 NP-hard 的問題。