Polynomial Complexity Classes
在〈Decision Problems〉中，將計算問題表述成只有 yes 或 no 兩種答案的 decision problem。這樣的表述方式提供了一個統一的框架，使不同問題之間的計算難度得以比較。
在此基礎上，接下來便要進一步討論：這些 decision problems 究竟有多難。複雜度理論正是研究這個問題的工具。它依照「能否有效率地求解」以及「能否有效率地驗證」來分類不同的問題。本節將介紹 $P$、$co\text{-}P$、$NP$、$co\text{-}NP$ 與 $NP$-complete 等基本類別，並說明這些概念雖然構成理解計算困難度的基礎，卻仍不足以直接作為密碼學安全性的完整依據。
The Class $P$
一個 decision problem 若屬於 $P$，意思是存在一個演算法，對於所有答案為 yes 的 instance，都能在 polynomial time 內輸出 yes。這裡的時間是以 bit operations 來衡量，而 polynomial time 的意思是：所需位元操作數量被某個輸入大小的多項式函數所界定。在這樣的表述下，若答案是 no，演算法甚至不一定要保證在多項式時間內停機；但如果它真的停下來，就必須回答正確。
直觀上，$P$ 代表的是那些「容易計算」的問題，也就是存在有效率演算法的問題。例如，給定整數 $x,y,z$，判斷 $z=x\cdot y$ 是否成立；或者給定密文 $c$、金鑰 $k$ 與明文 $m$，判斷 $c$ 是否是 $m$ 在某個加密系統下用 $k$ 加密後的結果。這些都屬於容易驗算的問題，因此可以理解為位於 $P$ 中。
The Class $co\text{-}P$
若把前面 $P$ 的定義中 yes 與 no 的角色對調，就得到 $co\text{-}P$。也就是說，對於所有答案為 no 的 instance，都能在 polynomial time 內輸出 no。換句話說，$P$ 著重的是能快速確認 yes，而 $co\text{-}P$ 著重的是能快速確認 no。
事實上，
\[P = co\text{-}P\]證明方式很直接。假設有一個演算法 $A$，只要 instance 的答案是 yes，就能在 $n^c$ 的時間內輸出 yes。那麼只要把 $A$ 跑起來：若它在 $n^c$ 步內輸出 yes，就接受 yes；若超過 $n^c$ 還沒有輸出 yes，就直接終止它並輸出 no。這樣一來，就能把原本「快速確認 yes」的能力轉換成「快速確認 no」的能力，因此 $P$ 與 $co\text{-}P$ 相等。
The Class $NP$
一個 decision problem 若屬於 $NP$，意思是：對每一個答案為 yes 的 instance，都存在一個 witness，而且這個 witness 可以在 polynomial time 內被檢查。這裡的 witness 可以理解成一份「證明」，用來證明這個 instance 的確屬於 yes 的那一側。
這裡最重要的點不是「能不能快速找到 witness」，而是「若有人把 witness 給你，你能不能快速驗證它是對的」。這正是 $NP$ 與 $P$ 的關鍵差別所在。
- Composite problem：問一個整數 $N$ 是否為合成數。這個問題在 $NP$ 中，因為 witness 可以是一個非平凡因數，而驗證方式只要檢查它是否真的整除 $N$ 即可。
- $k$-colourability：問圖 $G$ 是否可用 $k$ 種顏色著色。這時 witness 就是一組具體的著色方式，而驗證時只需確認每條邊的兩端頂點顏色不同即可。
- Knapsack：問某個 knapsack instance 是否有解。這時 witness 就是那組 $b_i$ 的值，而驗證只需計算 $$ S=b_1w_1+\cdots+b_nw_n $$ 是否成立。
在這些例子裡，並沒有假設 witness 本身能在 polynomial time 內被找出來；$NP$ 的重點只在於：一旦有人給出 witness，就能在 polynomial time 內驗證它是否正確。由此立刻可以看出
\[P \subset NP\]因為若一個問題本來就能在 polynomial time 內求解，那麼它的答案自然也能在 polynomial time 內被驗證。
不過，這裡也帶出了理論計算機科學中最重要的公開問題之一，也就是 $P = NP$？
\[P \stackrel{?}{=} NP\]目前普遍相信答案是否定的，也就是相信
\[P \ne NP\]這代表可能存在某些問題：雖然它們的 yes instance 擁有簡短而且可快速驗證的證明，但整體而言，仍然不存在已知的 polynomial-time 演算法可以有效率地把答案求出來。
The Class $co\text{-}NP$
與 $co\text{-}P$ 的定義方式相同，$co\text{-}NP$ 是把 $NP$ 中 yes 與 no 的角色對調後得到的類別。也就是說，對於每一個答案為 no 的 instance，都存在一個可在 polynomial time 驗證的 witness。換句話說，$NP$ 是「yes 有短證明」，而 $co\text{-}NP$ 是「no 有短證明」。
不過，這裡就不像 $P$ 與 $co\text{-}P$ 那樣自然相等。若
\[P \ne NP\]則可推出
\[NP \ne co\text{-}NP\]因此一般會認為
\[NP \ne co\text{-}NP\]這表示「yes 有可驗證證明」與「no 有可驗證證明」通常應被視為不同層次的性質。
Size of Witnesses
除了問某個問題是否在 $NP$ 裡之外，另一個值得注意的問題是：一個 witness 可以多小？ 也就是說，不只要看某個問題是否有可驗證證明，還可以進一步問這份證明本身需要多長。
以 COMPOSITES 為例，對於一個合成數 $N$，可以用兩種方式作為證明它是 composite 的 witness：
-
直接給一個因數。此時 witness 的大小是 \(O(\log n).\) 因為一個因數本身所需的位元長度與輸入大小呈對數關係。
-
給一個 Miller–Rabin witness $a$。在假設廣義黎曼猜想（GRH）成立下，這個 witness 的大小甚至可以做到 \(O(\log\log n),\) 因為此時可以取 \(a \le O((\log n)^2).\)
這說明即使同樣是一個 $NP$ 問題，其證明的長度也可能有很大差異。
$NP$-Complete Problems
一個 decision problem $DP$ 若是 $NP$-complete，表示每一個屬於 $NP$ 的問題都可以在 polynomial time 內 reduce 到 $DP$。換句話說，若能有效率地解掉這個 $DP$，那麼所有 $NP$ 問題也都能有效率地解掉。形式上可寫成：
\[DP \in P \implies P = NP\]因此，$NP$-complete 問題通常可以被看成是 $NP$ 中最困難的一群問題。更多經典例子可參見〈List of NPC Problems〉。
- 3-colouring problem
- knapsack problem
這些例子也說明，理論上的高困難度與實務上是否適合作為密碼學基礎，未必是同一件事。對密碼學而言，問題並不只是在理論上是否夠難，而是這種困難性是否真的符合密碼學所需要的形式。
- 先將圖 $G$ 的頂點任意排序為 $v_1,\dots,v_t$。
- 顏色集合為 $\{1,2,3\}$。
- 依照排序逐一造訪頂點。
- 每次都嘗試使用當前可用的最小顏色。
- 若卡住，就回溯到最近一個已著色頂點，改試下一個顏色。
- 若第一個頂點都無法再換色，就輸出「不可 3-著色」。
- 若最後一個頂點成功上色，則輸出「可 3-著色」。
整體而言，複雜度類別提供了一套理解計算困難度的基本語言，也為後續討論密碼學中的 hardness assumptions 奠定了背景。不過，從複雜度理論走向密碼學時，還必須進一步區分 worst-case 與 average-case 的差別。
References
- Nigel P. Smart, Cryptography: An Introduction (3rd ed.), Chapter 19. PDF