描述複雜度（descriptive complexity）

複雜度類別通常靠計算資源來定義：一台機器用了多少時間、多少記憶體。描述複雜度提供了一個出奇不同的視角，一個完全不提機器的視角。它的問題是：你究竟需要多麼豐富的邏輯語言，才能把一個問題表達出來？事實證明，計算一個問題的困難程度，與描述它所需邏輯的表達能力，是同一枚硬幣的兩面。

其想法是把一個輸入（一張圖、一個字串、一個結構）看成一個邏輯公式可以談論的數學物件，並追問：要陳述某個給定性質，你必須允許哪些邏輯運算子？純粹的一階邏輯（對個別元素量化：「存在一個頂點使得……」）只能捕捉相當簡單、局部的性質。加上對關係或集合量化的能力——二階邏輯——或加上一個表達遞迴的最小不動點運算子，便把你一躍提升到整個複雜度類別。一個了不起的經驗事實是：自然的複雜度類別恰好對應自然的邏輯——P、NP、PSPACE 等各有一個乾淨的邏輯刻畫，而關鍵是這些對應與機器無關——它們根本不提時間、紙帶或步驟。

這為何重要？它把那些重大未解問題重新框定為關於邏輯能力的問題。例如，既然 NP 等於存在性二階邏輯（Fagin 定理，有自己的條目），P 是否等於 NP 的問題，便化為「某個較弱的邏輯能否表達較強邏輯所能表達的一切」的問題。這給了邏輯學家一個切入複雜度的立足點，也驅動著實用工具：像 SQL 這樣的資料庫語言裡的查詢，本質上就是一個一階（或不動點）公式，所以描述複雜度精確地告訴我們這類查詢能有多難。這套理論在「什麼能被高效計算」與「什麼能被言說」之間架起一座橋。