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

## 多項式表示變換閉包與閉包悖論：逃生門能否被形式化？

**Round 06: Polynomial Representation-Transformation Closure and the Closure Dilemma**

- **主導研究者：** Neo.K（許筌崴）
- **協作整理：** Aletheia
- **機構：** EveMissLab（一言諾科技有限公司）
- **日期：** 2026 年 8 月 1 日
- **版本：** v1.0
- **研究狀態：** 第六輪雙假設預演
- **前置文件：** `00`–`05`
- **遊戲態度：** 等號隊與不等號隊繼續互拆模型
- **文件標準：** 遊戲化敘事，正式數學邊界

---

## 摘要

第五輪提出「表示逃逸剖面」 REP，並留下核心問題：如果每當某一表示出現下界時，等號隊都可以宣稱「還有另一種未知表示」，那麼不等號隊是否能把所有低成本表示革命一起納入一個可分析的閉包？

本輪嘗試建立「多項式表示變換閉包」。令一個表示系統為語義等價的有限描述類，若存在一個統一、多項式時間、多項式輸出長度且保持問題答案的變換，則在兩種表示間連一條有向邊。由此得到一個表示變換圖或範疇。

然而，本輪立刻發現一個關鍵陷阱：**若允許任意多項式時間變換，則「SAT 能否到達可處理正規形」與「SAT 是否在 P」完全等價。**若 $P=NP$，求解器本身就能把任何 SAT 實例直接編譯成常數 TRUE 或 FALSE；反之，只要能在多項式時間把 SAT 編譯到一個可多項式判定的目標類，SAT 就在 P。這使「完整多項式閉包」退化為原問題的同義反覆。

於是出現本輪核心「閉包悖論」：

$$
\boxed{
\text{閉包太寬}\Rightarrow\text{與 }P/NP\text{ 同義反覆；}
\qquad
\text{閉包太窄}\Rightarrow\text{只能得到受限模型下界。}
}
$$

本輪因此把研究方向從「封鎖所有表示」改為「尋找非循環、可獨立定義、又能保留足夠多表示革命的變換不變性」。外部理論中，Schaefer 型布林 CSP 二分定理與更一般 CSP 的 polymorphism 方法提供了一個重要提示：有時真正穩定的不是表面語法，而是某類變換下保持的代數操作／關係閉包。這為下一輪「不變量不是大小，而是保存什麼代數結構」提供入口。

---

# 一、上輪留下的無限逃生門

第五輪建立困難矩陣後，得到兩個同時成立的觀察：

1. 強下界通常綁定某個模型；
2. 漂亮的多項式算法通常利用某種特殊表示或結構。

因此，只要不等號隊說：

$$
R_1\text{ 很大},
$$

等號隊就能回答：

$$
R_1\rightarrow R_2\rightarrow R_3\rightarrow\cdots
$$

也許存在一個尚未發現的 $R_k$ 很小。

所以本輪首先嘗試把「表示革命」本身形式化。

---

# 二、表示系統與多項式變換

令表示系統

$$
\mathfrak R=(\mathrm{Rep},\llbracket\cdot\rrbracket,Q)
$$

包含：

- $\mathrm{Rep}$：有限描述集合；
- $\llbracket r\rrbracket$：表示 $r$ 的語義；
- $Q$：我們關心的查詢，例如 SAT、模型計數、等價性等。

兩表示系統 $\mathfrak R_i,\mathfrak R_j$ 間的答案保持變換為：

$$
\tau_{ij}:\mathrm{Rep}_i\rightarrow\mathrm{Rep}_j,
$$

滿足：

$$
Q(r)=Q(\tau_{ij}(r)).
$$

若：

$$
T_{\tau_{ij}}(|r|)\in\operatorname{poly}(|r|)
$$

且：

$$
|\tau_{ij}(r)|\in\operatorname{poly}(|r|),
$$

則記為：

$$
\mathfrak R_i\xrightarrow{\mathrm{poly}}\mathfrak R_j.
$$

所有這種邊形成一張表示變換圖：

$$
\mathcal G_{\mathrm{rep}}=(\mathcal V,\mathcal E_{\mathrm{poly}}).
$$

若從初始表示 $R$ 經有限條多項式邊可達 $R'$，記為：

$$
R\leadsto_{\mathrm{poly}}R'.
$$

於是定義完整多項式表示閉包：

$$
\operatorname{Cl}_{\mathrm{poly}}(R)
=
\{R'\mid R\leadsto_{\mathrm{poly}}R'\}.
$$

---

# 三、等號隊第一招：可處理正規形

等號隊提出：

> $P=NP$ 也許等價於 SAT 的一般表示能在多項式表示閉包內到達某個 tractable normal form。

令 $\mathcal T$ 為一個可處理目標表示族，滿足：

$$
Q|_{\mathcal T}\in P.
$$

例如某些固定類型下的：

- 2-CNF；
- Horn；
- affine/XOR；
- bounded-treewidth 表示；
- 已成功編譯的 d-DNNF／OBDD 子族。

若存在：

$$
\tau:\mathrm{SAT}\rightarrow\mathcal T
$$

使 $\tau$ 為統一多項式變換並保持可滿足性，則：

$$
\mathrm{SAT}\in P.
$$

所以等號隊把自己的勝利條件寫成：

$$
\boxed{
\mathrm{SAT}\cap\operatorname{Reach}_{\mathrm{poly}}(\mathcal T)\neq\varnothing
}
$$

更口語地說：找到一條便宜的「變身路線」，把一般 SAT 變成已知容易世界。

---

# 四、不等號隊反擊：這可能只是把答案藏進編譯器

不等號隊立刻要求：

> 這個變換 $\tau$ 到底能不能在轉換過程中直接求解 SAT？

若沒有任何限制，假設 $P=NP$ 且有決定器 $A$，便可定義：

$$
\tau_A(\varphi)
=
\begin{cases}
\top,&A(\varphi)=1,\\
\bot,&A(\varphi)=0.
\end{cases}
$$

其中 $\top$ 與 $\bot$ 是大小為常數、答案顯然的目標表示。

由於 $A$ 為多項式時間：

$$
T_{\tau_A}\in P.
$$

輸出大小甚至是：

$$
O(1).
$$

所以如果允許「任意多項式時間表示變換」，那麼只要 $P=NP$，SAT 當然能一步抵達最簡單的 tractable normal form。

反方向也一樣：若存在多項式時間變換

$$
\tau:\mathrm{SAT}\rightarrow\mathcal T
$$

且 $\mathcal T$ 的答案能多項式時間判定，則組合算法：

$$
\varphi
\xrightarrow{\tau}
\tau(\varphi)
\xrightarrow{Q_{\mathcal T}}
\{0,1\}
$$

就是 SAT 的多項式算法。

因此得到本輪第一個正式引理。

---

# 五、完整閉包平凡化引理

## 引理 5.1｜Tractable-Reachability Equivalence

令 $L$ 為任意判定語言，$\mathcal T$ 為至少包含一個固定 YES 實例 $t_1$ 與固定 NO 實例 $t_0$ 的可多項式判定語言。以下兩者等價：

1. $L\in P$；
2. 存在統一多項式時間映射 $\tau$，使：

$$
x\in L
\iff
\tau(x)\in\mathcal T.
$$

### 證明

若 2 成立，先計算 $\tau(x)$ 再執行 $\mathcal T$ 的 P 算法，即得 $L\in P$。

若 1 成立，令 $A$ 為 $L$ 的 P 決定器，定義：

$$
\tau(x)
=
\begin{cases}
 t_1,&A(x)=1,\\
 t_0,&A(x)=0.
\end{cases}
$$

則 $\tau$ 為多項式時間且保持答案。證畢。

---

## 推論

若「多項式表示閉包」允許所有統一 P-time answer-preserving transformations，則：

$$
L\text{ 可達 tractable normal form}
\iff
L\in P.
$$

對 SAT 而言：

$$
\boxed{
\mathrm{SAT}\leadsto_{\mathrm{poly}}\mathcal T
\iff
P=NP.
}
$$

所以「能否逃到容易表示」本身沒有自動提供新的證明槓桿。

它只是把原問題改寫成一張圖上的可達性。

---

# 六、閉包悖論

這使我們得到本輪真正重要的結構：

## 太寬

若允許：

$$
\mathcal E=\text{所有 P-time 答案保持變換},
$$

則閉包問題與原 $P/NP$ 問題等價。

沒有新資訊。

## 太窄

若只允許：

- 局部重寫；
- 固定大小 gadget；
- 特定代數操作；
- 特定知識編譯語言；
- 特定圖分解；
- 特定證明系統；

那麼即使證明 SAT 無法到達 tractable normal form，也只能得到：

$$
\text{在這個變換族中不可達}.
$$

仍不能推出一般：

$$
P\neq NP.
$$

因此：

$$
\boxed{
\text{閉包越完整，越循環；閉包越可分析，越受限。}
}
$$

本文稱之為：

$$
\boxed{
\text{Representation-Closure Dilemma（表示閉包悖論）}
}
$$

---

# 七、等號隊乘勝追擊：所有「禁止求解的轉換」都很可疑

不等號隊自然想補一條：

> 好，那我們只允許「不偷偷求解 SAT」的結構變換。

等號隊反問：

$$
\text{怎麼在不先知道 }P\stackrel{?}{=}NP\text{ 的情況下形式化「不求解」？}
$$

例如一個全域代數變換看似只是重寫，但它可能恰好已經完成了最關鍵的推理。

反過來，一個很局部的 rewrite chain 也可能累積出完整求解能力。

所以「solution-oblivious」「不看答案」「只是表示變換」若沒有獨立數學定義，都很容易成為語義口號。

這擊破第二條直覺路線：

$$
\boxed{
\text{不能靠自然語言區分「真正求解」與「純表示」。}
}
$$

計算本身就是狀態與表示的轉換。

---

# 八、不等號隊改變問題：不要封鎖所有轉換，找「被某類轉換保存的性質」

既然完整閉包不可分析，受限閉包又不夠一般，不等號隊改變方向：

> 不直接列舉所有可能表示，而研究哪些語義／代數性質在一大類自然、可獨立定義的變換下被保存。

也就是從：

$$
\text{Representation Size}
$$

轉向：

$$
\text{Transformation-Preserved Structure}.
$$

這與第五輪「困難可能不是大小，而是某種無法被表示革命抹去的結構」接軌。

---

# 九、Schaefer 二分定理帶來的提示

對布林 constraint language $\Gamma$，Schaefer 型結果表明：固定允許關係族後，其 SAT 問題存在清楚的 tractable／NP-complete 分界。經典 tractable 情形包括 Horn、dual-Horn、bijunctive、affine，以及常數有效類型；否則進入 NP-complete 一側。

這一點非常重要，因為它顯示：

$$
\boxed{
\text{某些困難分界真的可以由「允許關係具備何種結構」決定，}
}
$$

而不是由公式表面的長短決定。

更一般有限域 CSP 的 dichotomy 工作進一步把這種分界連到 polymorphism／代數操作結構。

因此，我們得到一個對本系列很重要的新提示：

> 真正值得尋找的跨表示量，也許不是「有多少條 clause」「有多少狀態」「某張圖多寬」，而是問題語義保留／缺失哪些可使推理閉合的操作結構。

---

# 十、從 representation closure 轉向 algebraic closure

令 $R\subseteq D^k$ 為一個關係。若操作：

$$
f:D^m\rightarrow D
$$

對任意 $m$ 個 $R$ 中 tuple 做座標逐點作用後仍得到 $R$ 中 tuple，則稱 $f$ 保存 $R$。

這類保存操作即 polymorphism 思路的核心。

對 constraint language $\Gamma$，可考察：

$$
\operatorname{Pol}(\Gamma).
$$

重要之處在於：它不是某一條 CNF 的字面語法，而是在關係層面描述「哪些合成操作仍保持可行解結構」。

這與我們前幾輪想找的東西極其接近：

$$
\boxed{
\text{換表示後仍存在的結構性。}
}
$$

但必須強調：

- CSP dichotomy 已經解決的是固定 constraint language 的分類；
- 一般 SAT 允許的關係足以表達 NP-complete 結構；
- polymorphism 理論本身不直接證明 $P\neq NP$。

它提供的是一個**如何成功建立非語法 tractability invariant 的示範**。

---

# 十一、等號隊反擊：Schaefer 正好也支持我

等號隊說：

Schaefer 不只是告訴你「有困難代數結構」，它也告訴你：

$$
\text{一旦問題落入某些特殊 closure，整個問題就變 P。}
$$

這正是等號隊一直尋找的數學壓縮器精神。

例如 affine 結構不是靠檢查所有解，而是換成線性代數世界：

$$
Ax=b\pmod 2.
$$

Horn 結構也具有自己的閉合性與有效推理程序。

所以等號隊提出：

> 也許一般 SAT 只是尚未找到更高階的「隱藏 polymorphism／隱藏正規結構」。

不等號隊不能用「目前已知分類沒有」證明不存在。

因此比分沒有被拉開。

---

# 十二、知識編譯再次介入：編譯成本不能隱形

Knowledge Compilation 的核心做法之一，是把原始表示離線轉成另一種 target language，再研究：

1. target 是否 succinct；
2. 哪些 query 可多項式回答；
3. 哪些 transformation 可多項式完成。

這與本輪表示圖完全同構。

但它同時再次提醒：

$$
T_{\mathrm{compile}}
+
L_{\mathrm{target}}
+
T_{\mathrm{query}}
$$

必須一起計量。

若 query 變成線性時間，但 target 需要指數大小，並沒有取得傳統 $P=NP$ 的勝利。

若允許任意昂貴離線 preprocessing，也不能把它偷偷排除在 uniform complexity 外。

因此，本輪保留第五輪 REP，並新增閉包版成本：

$$
\operatorname{PathCost}
(R_0\rightarrow\cdots\rightarrow R_k)
=
\sum_{i=0}^{k-1}
C(\tau_i)
+
L(R_k)
+
Q(R_k).
$$

真正有效的逃逸路徑必須整條路都為多項式。

---

# 十三、建立「表示逃逸階層」而非單一閉包

為避免完整閉包平凡化，本輪先建立研究用階層，而不宣稱它涵蓋所有算法：

## E0｜表面等價重寫

- clause 重排；
- Boolean identity；
- 常數傳播；
- 明顯冗餘消除。

## E1｜局部 gadget 與 definitional extension

- 引入多項式數量輔助變數；
- Tseitin-style definitional encoding；
- bounded-local replacement。

## E2｜結構分解

- tree decomposition；
- backdoor decomposition；
- component decomposition。

## E3｜代數化／幾何化

- XOR 線性化；
- polynomial encoding；
- polyhedral lifting；
- spectral／matrix representation。

## E4｜知識編譯

- OBDD；
- d-DNNF；
- SDD 等 target language。

## E5｜任意統一 P-time answer-preserving transformation

到 E5 時：

$$
\text{tractable reachability}\iff L\in P.
$$

所以 E5 不再是證明工具，而是原問題的完整語義邊界。

這個階層的價值不在於宣稱完整，而在於觀察：

$$
\text{某個候選困難核心究竟在哪一層被打穿？}
$$

---

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

以下說法不得直接用作一般 $P\neq NP$ 證明：

1. SAT 無法被某一已知表示變換成 Horn，所以 $P\neq NP$；
2. 把所有 P-time 變換放進閉包後，證明 tractable normal form 不可達；
3. 定義「不允許求解 SAT 的變換」，但沒有獨立形式條件；
4. 把 representation graph 的最短路徑成本直接定義為 SAT 最佳算法時間；
5. 以「未知表示不存在」作前提；
6. 認為所有 tractable normal form 都必須是現有 Horn／2-SAT／affine 類型；
7. 用固定 constraint-language dichotomy 直接外推一般 $P\neq NP$。

---

# 十五、本輪真正成果

## 15.1 完整閉包平凡化

得到清楚等價：

$$
\boxed{
L\in P
\iff
L\text{ 可經任意 uniform P-time reduction 到達固定 tractable target。}
}
$$

因此「完整多項式表示閉包」不能直接作為新的證明突破。

## 15.2 找到閉包悖論

$$
\boxed{
\text{太寬}=\text{循環，}
\qquad
\text{太窄}=\text{受限。}
}
$$

這成為之後所有「跨表示封鎖」方案的必要審查器。

## 15.3 研究焦點改變

不再問：

$$
\text{所有表示中哪個最小？}
$$

而開始問：

$$
\boxed{
\text{哪些代數／語義結構，在足夠廣且可獨立定義的變換下仍被保存？}
}
$$

## 15.4 Schaefer／CSP 提供成功範例

CSP 理論顯示，tractability 確實能與非表面語法的 closure／polymorphism 性質連結。

這不是 $P/NP$ 答案，但它展示了我們想要的不變量應該長什麼樣子。

---

# 十六、比分

等號隊：

- 證明完整閉包一旦允許所有 P-time 變換，就可在 $P=NP$ 世界直接壓成常數答案；
- 擊破「表示可達性本身就是新證明工具」。

不等號隊：

- 找到完整閉包的循環陷阱；
- 成功把研究目標從表示大小轉到變換保存結構；
- 從 CSP/polymorphism 找到一個真正已有成功先例的方向。

本輪：

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

仍然平手。

---

# 十七、第七輪入口

下一輪題目：

## 代數不變量爭奪戰：tractability 是否總伴隨某種可保存運算？

核心思維實驗：

1. 把 Horn、2-SAT、affine、bounded-width CSP 的「容易」來源寫成 closure／polymorphism；
2. 把一般 3-SAT 的 relation clone 放進同一視角；
3. 讓不等號隊嘗試提出「缺乏足夠 polymorphism = 無法壓縮」的廣義猜想；
4. 讓等號隊指出一般演算法可以完全脫離固定 constraint-language 表示，因此 CSP invariants 未必封鎖 P-time SAT solver；
5. 尋找是否存在比固定 polymorphism 更高階、與 computation trajectory／compilation closure 共同作用的動態代數不變量。

暫定研究式：

$$
\boxed{
\text{Tractability}
\stackrel{?}{\Longleftrightarrow}
\text{存在某種可被低成本合成且保存解結構的運算族。}
}
$$

這不是定理，是第七輪辯論題。

---

# 十八、外部理論參照

1. A. Darwiche, P. Marquis, **A Knowledge Compilation Map**, JAIR 17 (2002), 229–264。
2. M. Cadoli, F. M. Donini, P. Liberatore, M. Schaerf, **Preprocessing of Intractable Problems**, Information and Computation 176(2), 2002。
3. T. J. Schaefer, **The Complexity of Satisfiability Problems**, STOC 1978。
4. A. Bulatov / D. Zhuk, finite-domain CSP dichotomy 系列工作。
5. CSP algebraic approach：constraint languages、relational clones、polymorphisms 與 tractability 分類。

---

## 本輪裁定

$$
\boxed{
\text{「表示革命」不能靠列舉表示被一次封死；}
}
$$

$$
\boxed{
\text{但我們第一次看清：真正候選不變量應該研究「變換保存什麼」，而非「表示長什麼」。}
}
$$

這將研究從 representation size game 推向 transformation-invariant structure game。