2010s - 幾何複雜度理論與電路下界#

案件摘要#

2010 年代，證明電路下界（如 P ⊄ 常數深度多數閘電路）仍撞牆，Ketan Mulmuley 提出以「表示論 + 代數幾何」攻堅 P vs NP 的幾何複雜度理論（GCT）。GCT 將問題化約為 permanent vs determinant 的表示論分離，2019 年 Mulmuley 宣稱 GCT 取得關鍵進展——這是 21 世紀最大懸案最系統化的偵辦路線。

前因 -- 為什麼會有這個案子#

1985 年：Razborov 對單調電路證明 clique 下界，一度被視為攻破 P vs NP 的曙光。
1994 年：Razborov–Rudich 的「自然證明障礙」宣判：這類證明在密碼學假設下無法奏效，曙光破滅。
1987 年：Håstad 證明 \(\text{AC}^0\) 的指數下界——常數深度、AND/OR/NOT 電路無法計算 parity。
1992 年：Razborov–Smolensky 證明常數深度多數閘電路（ \(\text{ACC}^0\) ）無法計算 MOD \(_q\) （ \(q\) 為質數冪以外的模）——但 ACC 本身（MOD \(_6\) 電路）直到 2010 年 Williams 才有非平凡下界。
疑案本質：所有「組合式」下界技術皆撞上自然證明障礙。需要全新的數學語言——Mulmuley 選擇了表示論與代數幾何。

線索與推理 -- 數學式、程式、理論#

1. 電路複雜度下界#

定義（電路類階層）：

\[ \text{AC}^0 \subsetneq \text{ACC}^0 \subseteq \text{TC}^0 \subseteq \text{NC}^1 \subseteq \text{P/poly} \]

\(\text{AC}^0\) ：常數深度、多項式大小、AND/OR/NOT 閘（不限扇入）。
\(\text{ACC}^0\) ：再加上 MOD \(_m\) 閘。
\(\text{TC}^0\) ：再加上 MAJORITY（多數閘）閘。
\(\text{NC}^1\) ：對數深度、有界扇入。

Håstad 下界（1987）：parity 需要 \(\text{AC}^0\) 電路大小 \(2^{\Omega(n^{1/(d-1)})}\) ：

\[ \text{PARITY} \notin \text{AC}^0 \]

Razborov–Smolensky（1992）：MOD \(_q\) （ \(q\) 非質數冪）不在 \(\text{ACC}^0\) 的質數冪模版本中——但 MOD \(_6\) 電路下界長期懸而未決。

Williams 突破（2010/2011）：Ryan Williams 證明：

\[ \text{NEXP} \not\subseteq \text{ACC}^0 \]

「滿足絲毫下界即可反推上界演算法」的「演算法—下界對偶」新路線，這是 2010 年代電路下界的最大突破。

P 不含常數深度多數閘電路： \(\text{P} \not\subseteq \text{TC}^0\) 是未證明的目標——若證明，即證明 P ≠ NP 的中途站。

2. Mulmuley 的幾何複雜度理論（GCT）#

GCT 核心思想（Mulmuley–Sohoni 1998/2001 提出）：把複雜度問題轉化為代數幾何上的軌道閉包問題，再用表示論（量子群、李群表示）分離。

將布爾函數「提昇（lifting）」為多項式，進入代數複雜度世界。
複雜度類對應到齊次多項式在 \(\text{GL}_n\) 作用下的軌道閉包。
「 \(f\) 的複雜度 \(\leq g\) 的複雜度」⟺ 「 \(f\) 落在 \(g\) 的軌道閉包」。
分離複雜度類 ⟺ 找到表示論不變量（如權格、矩陣係數）在軌道閉包上「不消失」的障礙。

數學口號：

\[ \text{P vs NP} \ \leadsto \ \text{表示論分離} \ \leadsto \ \text{飽和定理與軌道閉包} \]

GCT 的哲學：「自然證明障礙阻擋組合技術，但表示論不變量是『非自然』的——它對隨機函數不敏感，繞過 Razborov–Rudich 障礙。」

3. GCT 對 permanent vs determinant 的攻擊路線#

代數複雜度核心問題：permanent（積和式）與 determinant（行列式）：

\[ \text{perm}_n(X) = \sum_{\sigma \in S_n} \prod_{i=1}^{n} x_{i,\sigma(i)}, \qquad \det_n(X) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^{n} x_{i,\sigma(i)} \]

\(\text{det}\) 有高效演算法（Gaussian 消去， \(O(n^3)\) ）。
\(\text{perm}\) 是 #P-完備（Valiant 1979）——計數版本的 NP。

Valiant 假設： \(\text{perm}\) 不能被 \(\text{det}\) 的多項式次數冪表示：

\[ \text{perm}_n \notin \langle \text{det}_{m} \rangle, \quad m = n^{O(1)} \]

關鍵事實（Valiant 1979 / Koiran 等）：

\[ \text{perm} \in \text{VP}_{ws} \ \text{且} \ \text{VP} = \text{VQP} \iff \text{perm 的 det-複雜度為準多項式} \]

更強的：若 \(\text{VP} = \text{VNP}\) （代數版 P vs NP），則 \(\text{perm}\) 可被 determinant 的高次冪表示。反之，證明 \(\text{perm} \notin \langle \text{det}_{\text{poly}} \rangle\) 即證明代數版 VP ≠ VNP，進而暗示布爾版 P ≠ NP。

GCT 攻擊路線： 1. 將 \(\text{perm}_n\) 與 \(\text{det}_{m}\) 視為 \(\text{GL}_{nm}\) 表示的向量。 2. \(\text{perm}_n \in \overline{\text{GL}_{nm} \cdot \text{det}_m}\) （軌道閉包）？ 3. 用表示論障礙：找一個不可約表示 \(S_\lambda(\mathbb{C}^{nm})\) ，其出現於 \(\text{det}_m\) 的軌道閉包的穩定子群表示中，但不出現於 \(\text{perm}_n\) 。 4. GCT-A（Weyl 軌道模型）+ GCT-C（量子群/飽和）：用權格組合學與量子覆蓋群系統化枚舉障礙。 5. Mulmuley 證明（2008/2011）：若證明「 \(\text{perm}_n \notin \overline{G \cdot \text{det}_m}\) 」對 \(m = \text{poly}(n)\) ，配合正規化技術，可得 \(\text{perm} \notin \text{det}\) 的下界。

4. 2019 年 Mulmuley 宣稱的進展#

2019 年：Mulmuley 發表長篇論文（GCT 系列第 VII/VIII 部分），宣稱「針對 \(\text{perm}_n \notin \overline{G \cdot \text{det}_{m}}\) （ \(m = \text{poly}(n)\) ）的 GCT 證明路徑已具體化」，給出障礙的漸近結構分析（obstruction design、量子群飽和）。
同期：Bürgisser–Ikenmeyer–Panova（2016/2019）以表示論計算具體障礙，證明「GCT 的軌道閉包方法無法直接證明 \(\text{perm}_n \notin \langle \text{det}_m \rangle\) 對某些參數」——即 GCT 的「最簡版本」也有障礙，需更精細的技術。
這構成 GCT 內部的「偵探辯證」：Mulmuley 的路線 vs Ikenmeyer 等的否定結果，推動理論不斷修正。

5. 程式碼範例：permanent vs determinant 的直觀對照#

import itertools

def perm(X):
    """積和式：#P-完備，n! 項（無高效演算法已知）"""
    n = len(X)
    return sum(
        prod(X[i][p[i]] for i in range(n))
        for p in itertools.permutations(range(n))
    )

def det(X):
    """行列式：O(n^3) 高斯消去，有高效演算法"""
    n, A, sign = len(X), [row[:] for row in X], 1
    for i in range(n):
        piv = max(range(i, n), key=lambda r: abs(A[r][i]))
        if A[piv][i] == 0: return 0
        if piv != i: A[i], A[piv] = A[piv], A[i]; sign = -sign
        for r in range(i + 1, n):
            f = A[r][i] / A[i][i]
            A[r] = [a - f * b for a, b in zip(A[r], A[i])]
    return sign * prod(A[i][i] for i in range(n))

X = [[2, 1], [3, 4]]
print(perm(X))   # 2*4 + 1*3 = 11（積和式）
print(det(X))    # 2*4 - 1*3 = 5 （行列式）

兩者只差 \(\text{sgn}(\sigma)\) ，複雜度卻天壤之別——這正是 GCT 要解釋的「幾何之謎」。

結案 -- 後果與影響#

未結案：P vs NP 仍未解，但 GCT 提供了 21 世紀最系統化的偵辦路線。
影響 1：確立「代數複雜度 + 表示論」為下界研究的新戰場，衍生永久 vs 行列式幾何（geometric complexity of perm/det）的龐大文獻。
影響 2：Williams 的 NEXP ⊄ ACC⁰（2010）證明「演算法進步 ⟹ 下界進步」的對偶原理，為電路下界開新路。
影響 3：Bürgisser–Ikenmeyer–Panova 的否定結果顯示「最簡 GCT 不夠」，催生「超越軌道閉包」的修正路線。
影響 4：量子複雜度（BQP）崛起：Shor 演算法（1994）顯示量子電腦可解因數分解，BQP 與 NP 的關係（ \(\text{BQP} \stackrel{?}{\subseteq} \text{NP}\) 、 \(\text{NP} \not\subseteq \text{BQP}\) 的相對化證明）成為新懸案；量子資訊的表示論（如 SU(2) 自旋網絡）與 GCT 語言互通。
影響 5：複雜性理論與機器學習交叉：神經網路的「可學習性 vs 表達能力」可用電路複雜度刻畫；GCT 的「表示論不變量」被借鏡到張量分解與深度學習理論（tensor rank、混合模型）。
展望：未來 20 年可能的偵辦方向——量子複雜度與經典複雜度的深度融合、代數幾何方法的實證化、機器學習輔助找「表示論障礙」。

關鍵人物與文獻#

Ketan Mulmuley（芝加哥大學）：GCT 創始者，與 Milind Soohoni 於 1998/2001 提出。
Ryan Williams（MIT）：NEXP ⊄ ACC⁰（2010/2011），演算法—下界對偶。
Johan Håstad：AC⁰ 指數下界（1987）。
Razborov–Smolensky（1992）：常數深度多數閘電路下界。
Leslie Valiant（1979）：#P-完備性、perm vs determinant，2010 年圖靈獎。
Bürgisser–Ikenmeyer–Panova：GCT 障礙的具體計算與否定結果。
文獻：K. Mulmuley, "Geometric Complexity Theory VII/VIII" (arXiv, 2019)；K. Mulmuley, M. Soohoni, "Geometric complexity theory I", SIAM J. Comput., 2001。