Fagin 定理（Fagin's theorem）
/ FAY-gin /
想像你得知整個 NP 類別——每個「解容易檢查」的問題——竟能純粹用邏輯描述，視野裡沒有時鐘、沒有圖靈機、也沒有任何執行時間的概念。Fagin 定理正是那座驚人的橋。它說 NP 恰好等於存在性二階邏輯所能表達的性質之集合，這是第一個賦予某個複雜度類別一個乾淨、無機器之邏輯身分的結果，也是描述複雜度的奠基定理。
把邏輯拆開來看：一般的（一階）邏輯讓你對個別元素量化——「存在一個頂點 x 使得……」。二階邏輯加上對整個關係或集合量化的能力——「存在一個頂點集合 S……」或「存在一種著色……」。「存在性」這一部分意味著你只能在最外層說「存在這樣一個關係」，然後描述它必須滿足的一個一階條件。Fagin 定理陳述：有限結構的某個性質屬於 NP，若且唯若它能寫成這種形式。這直覺與 NP 的驗證者圖像完美吻合——那個被存在量化的關係，正是證書、是被猜出的解，而那個一階條件，正是「證書有效」的多項式時間檢查。
這是一個里程碑，因為它揭示了「可高效檢查」與「靠猜一個結構加一個簡單條件就能表達」是同一個概念，從兩個方向看到。它開啟了「以邏輯捕捉複雜度類別」的整個計畫，並把 P 對 NP 重新框定為一個關於邏輯表達力的問題（在一階邏輯上加一個不動點遞迴運算子，是否就足以表達存在性二階邏輯所能表達的一切？）。誠實的附帶條件：這些優雅的對應是針對有限結構陳述的，且對較低的類別通常假設元素上有一個排序；它們是一個貨真價實的深刻等價，而非鬆散的類比。
圖的 3-著色性屬於 NP，而 Fagin 的形式讓這一點一目了然：該性質說「存在三個頂點集合 R、G、B（一個存在性二階量詞），使得每個頂點恰好落在一個集合中、且沒有任何邊連接兩個同集合的頂點（一個一階條件）」。被猜出的集合就是證書；那個一階部分就是容易的驗證。
Fagin：NP = 存在性二階邏輯——被猜的關係是證書，其餘是檢查。
Fagin 定理刻畫 NP 時完全不提時間或機器——那份機器無關性正是重點所在。「存在性」這個限制很關鍵：完整的二階邏輯捕捉的是大得多的多項式階層，而非僅僅 NP。