# P/NP 辯論遊戲研究區｜第五輪

## 表示逃逸錦標賽：哪些困難被哪種數學武器打穿？

**Round 05: Representation Escape Tournament and Hardness Matrix**

- **主導研究者：** Neo.K（許筌崴）
- **協作整理：** Aletheia
- **機構：** EveMissLab（一言諾科技有限公司）
- **日期：** 2026 年 8 月 1 日
- **版本：** v1.0
- **研究狀態：** 第五輪雙假設預演
- **前置文件：** `00`–`04`
- **遊戲態度：** 讓不同數學表示互毆；文件仍依正式研究規格記錄

---

## 摘要

前四輪逐步淘汰了幾條過度簡化的 $P\neq NP$ 路線：候選數量大不等於必須逐項搜索；固定表示下的爆炸不等於跨表示爆炸；局部一致而全域矛盾，也可能被新的數學坐標系直接壓縮。第四輪的 Tseitin parity 案例尤其重要：同一族公式可在 resolution 類證明系統中呈現強下界，卻可在 $\mathbb F_2$ 線性表示中用 Gaussian elimination 多項式時間處理。

因此第五輪不再先猜一個「終極不變量」，而採用表示逃逸錦標賽：選取多種經典困難族，分別投入邏輯證明、代數化、圖分解、知識編譯、單調電路與線性擴展等表示空間，記錄每一族在哪裡被壓縮、在哪裡仍出現已知下界，以及哪些結論不能跨模型外推。

本輪最重要的觀察是：目前已知的強下界大多具有**表示限定性**，而已知的高效逃逸則大多依賴**可辨識的結構條件**。這使研究焦點從「哪個問題最難」轉為：

$$
\boxed{
\text{什麼結構決定某個問題能否找到一個低成本表示逃逸？}
}
$$

我們暫時將其稱為**表示逃逸剖面**（Representation Escape Profile, REP），它不是證明 $P\neq NP$ 的不變量，而是對一個問題族在多種表示下的壓縮／爆炸模式做向量化紀錄。若未來能找到某個 NP-complete 問題族，使其 REP 在一個足夠廣且可證明完備的表示變換族中都維持超多項式負載，才可能真正逼近「表示抗性耦合核心」。

---

# 一、第五輪遊戲規則

本輪不允許任何一隊只拿單一表示宣判勝負。

對一個問題族 $\mathcal F$，我們選擇若干表示／演算武器：

$$
\mathfrak R
=
\{
R_{\mathrm{res}},
R_{\mathrm{alg}},
R_{\mathrm{mono}},
R_{\mathrm{decomp}},
R_{\mathrm{KC}},
R_{\mathrm{LP}}
\}.
$$

分別代表：

- resolution／證明系統；
- 代數表示；
- monotone circuit；
- treewidth／separator／backdoor 類分解；
- knowledge compilation；
- LP extended formulation。

每一格只允許三種裁定：

1. **逃逸：** 有已知高效方法把原先困難結構壓縮；
2. **下界：** 在該受限表示模型中存在已知強下界；
3. **未知／不可外推：** 沒有足夠結果，或結論只限制其他模型。

最重要的規則是：

$$
\boxed{
\text{某一格「下界」}\neq\text{一般 }P\neq NP
}
$$

以及：

$$
\boxed{
\text{某一格「逃逸」}\neq\text{一般 }P=NP.
}
$$

---

# 二、參賽問題族

## 2.1 Tseitin / XOR 類約束

其核心是圖上的 parity 約束。作為 CNF 編碼時，它能對 resolution 形成經典困難族；但其語義本質是 $\mathbb F_2$ 線性方程。

此族是第五輪的基準選手，因為它同時展示：

$$
\text{同一語義問題}
\quad\text{可以在一個表示中困難、另一表示中簡單。}
$$

## 2.2 Pigeonhole Principle（PHP）

鴿巢原理公式是 proof complexity 的經典困難族。Haken 型結果以及後續工作給出 resolution 的指數大小下界，弱鴿巢與稀疏圖版本也存在強下界。

它用來測試：

$$
\text{組合計數矛盾是否能跨表示維持困難？}
$$

## 2.3 Clique

Clique 在 monotone circuit 中具有經典超多項式／指數型下界；近年的工作仍持續加強不同參數範圍內的 monotone lower bounds。

但這些結果只限制**單調電路**：一般電路可以使用 negation，故不能直接推成一般 circuit lower bound。

## 2.4 一般 SAT 與結構受限 SAT

一般 SAT 是核心 $NP$-complete 競技場，但某些結構條件能大幅降低難度。例如 bounded treewidth 與 small strong backdoor 可使 SAT 或 #SAT 進入高效或固定參數可處理範圍。

此族用來展示：

$$
\text{NP-complete 的一般類別}
\neq
\text{每個結構子族都一樣困難。}
$$

## 2.5 TSP / CUT / Stable Set 的多面體表示

這些組合優化問題的自然多面體在 LP extended formulation 模型中存在指數擴展複雜度下界：即使允許升到更高維再投影，也不存在某類多項式大小線性描述。

這是非常重要的案例，因為它證明：

> 「加入輔助維度」不是在所有表示模型中都能逃逸。

但此結果仍然只排除 LP 類線性擴展表示，不排除一般演算法。

---

# 三、表示逃逸矩陣

下表的「下界」均指該模型中的已知限制，不代表一般計算下界。

| 問題族 | Resolution / Proof | 代數化 | Monotone Circuit | Treewidth / Decomposition | Knowledge Compilation | LP Extended Formulation | 一般演算法裁定 |
|---|---|---|---|---|---|---|---|
| Tseitin / XOR | **強下界**（若干 resolution 模型） | **逃逸**：$\mathbb F_2$ Gaussian elimination | 非核心結果 | 圖結構可影響求解 | 某些編譯語言可能壓縮，依結構而定 | 非核心模型 | **可多項式求解其線性語義** |
| Pigeonhole Principle | **強下界**：resolution 指數型結果 | 無一般「一招打穿」結論 | 非核心 | 圖結構版本可改變 proof complexity | 依編譯語言而異 | 非核心 | **不能由 resolution 下界推出一般困難** |
| Clique | 某些證明系統可研究 | 非線性一般表示未解 | **強下界**：monotone circuits | 特定圖寬／參數下可做 DP | 依表示語言與參數而定 | 可有組合優化表示研究 | **單調下界不能外推一般電路** |
| SAT（一般） | 多種難公式族有 proof lower bounds | 某些子類可代數化 | 非核心 | **逃逸子族**：bounded treewidth、small backdoor | **明確 tradeoff**：succinctness vs tractable queries | 非主要一般 SAT 模型 | **核心未知** |
| TSP / CUT / Stable Set polytopes | 非主要模型 | 可有其他優化表示 | 非主要 | 特殊圖類可簡化 | 非核心 | **強下界**：無多項式大小 LP extension（對相應多面體） | **LP 下界不能外推一般算法** |

這張矩陣立刻展示：

$$
\boxed{
\text{沒有任何一列目前能在所有欄位同時形成一般下界。}
}
$$

也沒有任何一種武器能在所有列上形成普遍逃逸。

---

# 四、第一場：Tseitin 再戰——「困難」其實可能只是坐標不對

## 4.1 不等號隊出牌

在 resolution 中，Tseitin 公式能形成高 proof width 與長 refutation。若只看 CNF + resolution，這非常像一個真正的全域耦合障礙。

不等號隊主張：

$$
\text{局部 clause 推理}
\rightarrow
\text{需要大範圍全域協調}.
$$

## 4.2 等號隊反擊

把 parity 約束改寫成：

$$
Ax=b\pmod 2.
$$

Gaussian elimination 直接在多項式時間判斷一致性。

因此 resolution 的高寬度不是問題語義本身的普遍下界，而是：

$$
\boxed{
\text{resolution 對 parity 結構的表示不匹配成本。}
}
$$

### 本場裁定

$$
P=NP\text{ 隊勝一小局。}
$$

但只能得到：

> 某些看似全域困難的 CNF 結構可以被更合適的代數表示打穿。

不能得到一般 $P=NP$。

---

# 五、第二場：Pigeonhole——組合計數矛盾能否被換表示消失？

## 5.1 不等號隊出牌

PHP 是 resolution 下界的經典來源。已有結果證明 generalized PHP 與後續不同版本的 resolution proof 需要指數大小，說明某些非常簡單的組合真理，對特定證明系統也可能極度昂貴。

這支持一個重要直覺：

$$
\text{語義上「顯然」}
\not\Rightarrow
\text{某個形式系統中有短證明}.
$$

## 5.2 等號隊反擊

但 $P/NP$ 要問的不是：

$$
\text{resolution 能否短證明 PHP？}
$$

而是所有一般多項式算法是否都被迫支付類似成本。

PHP 的 combinatorial counting 可能在更強證明系統、算術推理或其他 representation 中被更短地表達。

因此：

$$
\boxed{
\text{proof-system hardness}
\neq
\text{general computational hardness}.
}
$$

### 本場裁定

不等號隊拿到**局部強武器**，但沒有封鎖所有逃生門。

---

# 六、第三場：Clique——單調電路大爆炸

## 6.1 不等號隊出牌

Clique 是 monotone circuit lower bounds 的經典戰場。對某些參數範圍，已有超多項式甚至強指數型單調電路下界。

這看起來非常接近我們想要的：

$$
\text{函數本身固定，電路可以任意重排，仍然很大。}
$$

## 6.2 等號隊反擊：你禁止了 negation

Monotone circuit 不允許 NOT gate。一般 circuit 則可以使用 negation，表示能力更強。

因此單調下界證明的是：

$$
\operatorname{size}_{\mathrm{monotone}}(\mathrm{CLIQUE})
\text{ 很大},
$$

不是：

$$
\operatorname{size}_{\mathrm{general}}(\mathrm{CLIQUE})
\text{ 很大}.
$$

### 本場裁定

這一局對本計畫非常重要：

> 「跨語法」還不夠；真正的跨表示必須明確列出允許的運算原語。

一旦增加一個新的原語，例如 negation、XOR、extension variable、oracle-like summary，都可能讓原來的下界失效。

---

# 七、第四場：SAT 的 treewidth / backdoor 逃逸

## 7.1 等號隊出牌

一般 SAT 是 NP-complete，但若約束圖有 bounded treewidth，或存在小的 strong backdoor 使少量變數賦值後落入 tractable class，則可以利用分解進行高效計算。

這說明：

$$
\boxed{
\text{困難常集中在少量「破壞可分解性」的結構上。}
}
$$

如果能找到小 backdoor，原來的大搜索空間可能迅速坍縮。

## 7.2 不等號隊反擊

這不是 $P=NP$ 證據，因為：

1. 一般 SAT 不保證 bounded treewidth；
2. backdoor 可能很大；
3. 找到小 backdoor 本身也可能困難；
4. 參數化算法的指數部分可能藏在 treewidth 或 backdoor size 中。

可將典型時間寫成：

$$
T(n,k)
=
\operatorname{poly}(n)\cdot f(k),
$$

若：

$$
k=\Theta(n),
$$

則仍可能是指數時間。

### 本場裁定

等號隊成功展示「結構條件可以讓 NP-hard 外觀坍縮」；不等號隊則守住「一般最壞情況」邊界。

---

# 八、第五場：LP 擴展表示——升維不是萬能逃生門

第四輪等號隊常用一個強力反擊：

> 原空間難表示，就引入輔助變數、升到更高維再投影回來。

第五輪讓不等號隊拿出 extended formulation lower bounds。

對 traveling salesman、cut、stable set 等多面體，已有結果證明不存在多項式大小的線性 extended formulation；即使允許較高維輔助空間，仍需要指數大小線性描述。

因此：

$$
\boxed{
\text{擴維可消除某些複雜度，但在線性表示世界中不是無限能力。}
}
$$

## 等號隊反擊

這依然只限制：

$$
\text{線性不等式 + 投影}
$$

這一表示類。

一般算法可以是非線性的、離散的、遞迴的、動態的或完全不經過多面體描述。

### 本場裁定

不等號隊獲得一個重要原則：

> 「引入新維度」本身不能當作永遠有效的表示逃逸公理。

但仍未封鎖一般計算。

---

# 九、Knowledge Compilation：雙方共同的裁判台

Knowledge compilation 特別適合本計畫，因為它明確把兩件事拆開：

$$
\text{表示有多簡潔？}
$$

與：

$$
\text{哪些查詢／轉換可在多項式時間完成？}
$$

某個 target language 可能非常 succinct，但不支持某些 tractable queries；另一個 target language 可能支援快速 query，卻要求巨大編譯結果。

這與我們的中介層完全一致：

$$
\text{construct}
\rightarrow
\text{represent}
\rightarrow
\text{evaluate}.
$$

所以第五輪得到一個非常實用的研究紀律：

> 任何「我把 NP 問題變成一個容易求值的函數」的提案，都必須同時交代函數／結構的生成成本與表示尺寸。

即：

$$
T_{\mathrm{compile}}
+
L_{\mathrm{representation}}
+
T_{\mathrm{query}}.
$$

不能只展示：

$$
T_{\mathrm{query}}\in\operatorname{poly}(n).
$$

---

# 十、表示逃逸剖面 REP

本輪不嘗試直接定義一個終極不變量，而先建立描述工具。

對問題族 $\mathcal F$ 與表示族：

$$
\mathfrak R
=
\{R_1,\ldots,R_m\},
$$

定義其表示逃逸剖面：

$$
\operatorname{REP}(\mathcal F)
=
(E_1,E_2,\ldots,E_m),
$$

其中每個 $E_i$ 記錄在表示 $R_i$ 中的：

$$
E_i
=
(
C_{\mathrm{construct}},
L_{\mathrm{repr}},
T_{\mathrm{eval}},
M,
P_{\mathrm{precision}}
).
$$

REP 的用途不是說：

$$
\operatorname{REP}(\mathcal F)\text{ 大}
\Rightarrow
P\neq NP.
$$

它只是讓我們能夠比較：

- 哪些問題族只在某一個表示中困難；
- 哪些問題族在很多表示中都反覆爆炸；
- 哪些逃逸依賴非常特殊的代數結構；
- 哪些下界其實是在測同一個更深層特徵。

---

# 十一、第五輪首次出現的共同模式

跨越上述案例後，可以觀察到四種反覆出現的模式。

## 11.1 可線性化

若問題的全域耦合可被轉為：

$$
Ax=b
$$

或其他具閉合消去規則的代數系統，則巨大組合空間可能被直接折疊。

Tseitin / XOR 是代表案例。

## 11.2 可分解

若約束交互圖能由小 separator、bounded treewidth 或小 backdoor 切開，則全域問題可由局部 table 合成。

其基本形式為：

$$
\text{global}
=
\operatorname{Combine}
(\text{small local summaries}).
$$

## 11.3 可編譯

若問題可轉入一個 target representation，使後續 query 變得容易，則搜索成本被移入 compilation。

這類逃逸是否真正多項式，取決於：

$$
L_{\mathrm{compiled}}
\quad\text{與}\quad
T_{\mathrm{compile}}.
$$

## 11.4 原語升級

某模型困難，加入新的操作原語後可能突然變簡單：

$$
\text{Resolution}+\mathrm{XOR}
$$

$$
\text{Monotone circuits}+\mathrm{NOT}
$$

$$
\text{Original space}+\text{extension variables}.
$$

因此，真正的下界研究必須回答：

> 為什麼「下一個原語」也救不了？

這個問題比證明某個固定模型困難更接近 $P\neq NP$ 的核心。

---

# 十二、不等號隊的新戰略：尋找「不可同時線性化、分解、編譯、擴維」的族

不等號隊不再要求：

$$
\text{某個 representation size 很大}.
$$

而提出新的思維實驗：尋找一個 NP-complete 族 $\mathcal H_n$，使它同時抵抗幾種主要逃逸：

$$
\begin{aligned}
&\text{NoLowDimLinearize}(\mathcal H_n),\\
&\text{NoSmallSeparator}(\mathcal H_n),\\
&\text{NoSmallBackdoor}(\mathcal H_n),\\
&\text{NoSuccinctTractableCompilation}(\mathcal H_n),\\
&\text{NoSmallExtension}(\mathcal H_n).
\end{aligned}
$$

這些目前都只是研究條件，不是已證明共同存在的性質。

不等號隊的遠期目標是建立某種：

$$
\boxed{
\text{逃逸覆蓋不完備定理}
}
$$

即證明一個足夠大的多項式算法族必須落入某一種可分析的結構逃逸模式；然後再為每種模式提供相應下界。

但這一步極其困難，因為若我們真能對「所有多項式算法」建立有限完備分類，本身已接近解決原問題。

---

# 十三、等號隊的新戰略：表示革命假說

等號隊則把影片的啟發推到最強：

> 歷史上很多「看起來需要大量分支」的問題，最後不是靠更快枚舉，而是靠找到新的數學表示。

因此提出：

$$
\boxed{
\text{Representation Revolution Hypothesis}
}
$$

即對 SAT 的存在量詞，也可能存在目前尚未納入上述矩陣的新表示原語 $R_*$，使：

$$
C_{\mathrm{construct}}(R_*)
+
L(R_*)
+
T_{\mathrm{eval}}(R_*)
\in
\operatorname{poly}(n).
$$

等號隊不需要現在知道 $R_*$ 是什麼；但如果不等號隊要證明 $P\neq NP$，就必須排除所有可能的 $R_*$，而不能只排除已知表示語言。

這是 $P\neq NP$ 方最麻煩的終極逃逸口。

---

# 十四、本輪淘汰的錯誤路線

以下論法正式加入黑名單：

1. Resolution 指數下界 $\Rightarrow P\neq NP$；
2. Monotone circuit 指數下界 $\Rightarrow$ 一般 circuit 指數下界；
3. LP extension complexity 指數下界 $\Rightarrow$ 不存在一般多項式算法；
4. bounded treewidth SAT 很容易 $\Rightarrow$ 一般 SAT 也容易；
5. 某表示可高效 query $\Rightarrow$ compilation 本身也高效；
6. 引入輔助維度總能壓縮困難；
7. 目前所有已知表示都失敗 $\Rightarrow$ 不存在未知表示革命。

---

# 十五、本輪暫定成果

## 15.1 第一成果：建立「表示逃逸矩陣」

研究開始從單一路線轉為跨模型比較，而不是讓每個下界在自己的模型中自我勝利。

## 15.2 第二成果：困難與表示之間是二元關係

更準確的研究對象不是：

$$
\operatorname{Hardness}(F),
$$

而是：

$$
\operatorname{Hardness}(F\mid R).
$$

只有當我們能控制表示變換族時，才有資格談跨表示困難。

## 15.3 第三成果：表示革命是等號隊最強逃逸口

只要存在某個未知 $R_*$，所有目前的局部下界仍可能被繞開。

## 15.4 第四成果：不等號隊的目標從「找一個下界」變成「限制表示革命空間」

下一步要問的不只是：

$$
\text{哪種表示很難？}
$$

而是：

$$
\boxed{
\text{所有可由多項式時間實現的表示革命，是否共享某些有限可分類的結構？}
}
$$

---

# 十六、本輪遊戲比分

第五輪中：

- 等號隊用 Tseitin 線性化、SAT treewidth/backdoor 再次證明表示革命確實能發生；
- 不等號隊用 resolution、monotone circuits 與 LP extension complexity 證明某些表示逃逸門確實可以被嚴格封死。

因此本輪各得一分：

$$
P=NP:4
\qquad
P\neq NP:4.
$$

比分只是遊戲介面，不是數學證據。

---

# 十七、第六輪入口：表示變換本身能否被分類？

第五輪真正留下的新問題是：

$$
\boxed{
\text{如果任意未知表示都可以被拿來逃逸，我們怎麼可能證明跨表示下界？}
}
$$

所以第六輪將研究：

## **多項式表示變換閉包**

設兩種表示 $R_i,R_j$ 之間存在多項式時間編譯：

$$
R_i\xrightarrow{\operatorname{poly}}R_j.
$$

可否把所有「不增加超多項式資源」的表示變換組成一個變換圖／範疇：

$$
\mathfrak C_{\mathrm{poly}}?
$$

然後追問：

1. 哪些下界在這個閉包下保持？
2. 哪些困難只是 representation artifact？
3. 是否可能存在一個 canonical / minimal representation class？
4. 若 $P=NP$，是否意味著 SAT 在此閉包中存在一個 tractable normal form？
5. 若 $P\neq NP$，是否可表述為 SAT 無法在此閉包中到達任何 tractable normal form？

這會把「表示革命」第一次變成一個可研究的數學對象，而不是無限未知逃生門。

---

# 十八、外部理論參照

1. Darwiche, A.; Marquis, P. **A Knowledge Compilation Map.** *Journal of Artificial Intelligence Research* 17 (2002), 229–264. 其核心框架比較表示語言的 succinctness，以及可在多項式時間支援的 queries / transformations。
2. Ben-Sasson, E.; Wigderson, A. **Short Proofs Are Narrow—Resolution Made Simple.** *Journal of the ACM* 48(2), 2001. 將 resolution proof width 與 proof length 連結，並統一多種經典指數下界。
3. de Rezende, S. F.; Nordström, J.; Risse, K.; Sokolov, D. **Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.** CCC 2020.
4. Razborov / Alon–Boppana 系列以及後續 monotone circuit 工作：Clique 在 monotone circuit 模型中具有強下界；但此限制不能直接外推一般 circuit。
5. Fiorini, S.; Massar, S.; Pokutta, S.; Tiwary, H. R.; de Wolf, R. **Exponential Lower Bounds for Polytopes in Combinatorial Optimization.** *Journal of the ACM* 62(2), 2015. 對 TSP、cut、stable set 等多面體給出指數 LP extension complexity 下界。
6. Gaspers, S.; Szeider, S. **Strong Backdoors to Bounded Treewidth SAT.** 研究 small backdoor 與 bounded treewidth 如何形成 SAT / #SAT 的 tractable 結構入口。

---

## 本輪裁定

$$
\boxed{
\text{第五輪沒有找到跨表示不變量，但第一次畫出了「困難在哪裡、又從哪裡逃掉」的地圖。}
}
$$

$$
\boxed{
\text{下一步不再追著每個表示跑，而要研究「多項式表示變換」本身。}
}
$$