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

## 多重反結構核心與異質黏合債務：把已知逃生門一起堵上之後，困難究竟在哪裡？

**Round 10: Multi-Anti-Structure Cores and Heterogeneous Gluing Debt**

- **主導研究者：** Neo.K（許筌崴）
- **協作整理：** Aletheia
- **機構：** EveMissLab（一言諾科技有限公司）
- **日期：** 2026 年 8 月 1 日
- **版本：** v1.0
- **研究狀態：** 第十輪雙假設預演
- **前置文件：** `00`–`09` 全部歷史輪次
- **遊戲態度：** 把已知逃生門一起堵上，再看等號隊從哪裡鑽出去
- **文件標準：** 所有一般性結論仍必須區分「模型內定理」「外部已知結果」「研究猜想」「思維實驗」

---

## 摘要

第九輪建立了「SAT 的局部 Blossom」與商化債務（Quotient Debt）框架：Variable Elimination、OBDD/DNNF、XOR/Affine extraction、Symmetry quotient、Backdoor、CDCL learned clauses 都能在特定結構上精確商掉大量候選，但沒有一種已知商化方法被證明能以 uniform polynomial cost 處理所有 SAT 實例。

第十輪原本的直觀任務是尋找一個 **Multi-Anti-Structure Core（MASC，多重反結構核心）**：同時具有高消去寬度、缺乏小 backdoor、缺乏有用 symmetry、難以 knowledge compilation、缺乏 affine 可抽取性、且在若干 proof systems 中需要大資源的 SAT 公式族。

本輪的第一個重要修正是：即使真的找到這種家族，也不能直接推出 $P\neq NP$。原因與前九輪一致——這仍可能只是「同時擊敗目前列出的有限武器庫」，而不是擊敗所有可能的確定性多項式時間演算法。

然而，本輪在比較 Schaefer 型 CSP、Monotone 3-SAT、expander-based DNNF lower bounds、random-CNF resolution lower bounds、heterogeneous backdoors 與 bottom-up knowledge compilation 後，得到一個更有價值的新焦點：

$$
\boxed{
\text{真正的困難可能不在局部子問題本身，而在不同局部可解結構的「黏合」。}
}
$$

最簡潔的示意是：正 3-clause 與負 3-clause 各自形成非常容易的單一模式；但允許兩者混合的 Monotone 3-SAT 已知仍可 NP-complete。更一般地，Schaefer dichotomy 告訴我們，Boolean constraint language 是否 tractable 取決於整個語言是否共享某些閉包／polymorphism 結構，而不是每個 constraint 單獨看起來是否容易。

因此，本輪提出新的研究物件：

$$
\boxed{\text{HGD = Heterogeneous Gluing Debt／異質黏合債務}}
$$

它描述「若問題被拆成多個各自可低成本求解／商化的局部塊，將這些局部摘要精確黏合為全域答案時，還需要付出多少介面成本」。這使前幾輪的局部—全域障礙、商化債務、polymorphism、treewidth、backdoor 與 knowledge compilation 可以被放進同一張圖中。

本輪仍沒有得到一般時間下界；但研究焦點從「多種反結構的堆疊」推進為「**局部 tractability 的不相容性與全域黏合成本**」。

---

# 一、上輪戰果：SAT 有很多 Blossom，但沒有通用 Blossom

第九輪將 SAT 中已知的精確壓縮方法整理為 quotient portfolio：

$$
\mathcal Q
=
\{
Q_{\mathrm{elim}},
Q_{\mathrm{KC}},
Q_{\oplus},
Q_{\mathrm{sym}},
Q_{\mathrm{bd}},
Q_{\mathrm{learn}}
\}.
$$

每個 $Q_i$ 都能在某些公式族上把大量微觀候選壓縮成較小的精確摘要。

但每一種方法都有明確債務：

$$
\mathbf D_Q(F)
=
(
D_{\mathrm{build}},
D_{\mathrm{size}},
D_{\mathrm{width}},
D_{\mathrm{residual}},
D_{\mathrm{detect}},
D_{\mathrm{proof}},
D_{\mathrm{lift}}
).
$$

因此第九輪留下的直接問題是：

> 能不能找到一族公式，讓上述多個已知 quotient 通道同時失效？

這就是本輪最初的 MASC 計畫。

---

# 二、多重反結構核心 MASC：第一版定義

對 SAT 公式 $F$，定義一個相對於目前已知工具庫的反結構向量：

$$
\mathbf A(F)
=
(
A_{\mathrm{elim}},
A_{\mathrm{bd}},
A_{\mathrm{sym}},
A_{\mathrm{KC}},
A_{\oplus},
A_{\mathrm{proof}}
).
$$

可暫時理解為：

- $A_{\mathrm{elim}}$：最佳已知消去／分解後仍需承擔的 width 或 fill-in；
- $A_{\mathrm{bd}}$：進入指定 tractable base classes 所需的最小 backdoor 規模；
- $A_{\mathrm{sym}}$：可被有效 symmetry quotient 消去的自由度之反面；
- $A_{\mathrm{KC}}$：在指定 compilation language 中所需的最小 representation size；
- $A_{\oplus}$：最大 affine/XOR 抽取後留下的非線性 residual；
- $A_{\mathrm{proof}}$：指定 proof system 中的 width、space 或 length 資源。

若某個公式族 $\mathcal F=\{F_n\}$ 在多項已知量上同時保持高值，可稱為相對於工具庫 $\mathcal Q$ 的：

$$
\boxed{\operatorname{MASC}_{\mathcal Q}}.
$$

注意下標 $\mathcal Q$ 非常重要。

本輪不允許直接寫成「MASC」，因為目前只能說它抵抗某個有限、明示的工具 portfolio，而不能說它抵抗所有可能表示。

---

# 三、不等號隊出牌：把所有已知逃生門一起堵上

不等號隊提出以下思維實驗。

尋找公式族 $F_n$，使：

$$
\operatorname{tw}(F_n)=\Omega(n)
$$

或其他消去相關 width 很大；同時沒有已知小 strong/heterogeneous backdoor；其主要 incidence/primal graph 缺乏可利用的大型 automorphism；其 DNNF/structured-DNNF/OBDD 等若干 compilation language 需要超多項式甚至指數大小；可抽取的 XOR 部分不足以決定整體；並且在 resolution 類 proof systems 中需要大 width/space/size。

如果這些特徵由同一個底層原因造成，也許存在某種更深的不變量。

## 3.1 Expander 結構作為候選來源

已知存在由 expander graph 建構的 CNF 家族，對 DNNF 需要 strongly exponential size。這證明某些「高連接、難分解」結構確實可以對相當強的 knowledge-compilation language 產生無條件表示下界。

另一方面，resolution proof complexity 中 expansion 也長期是 width、space 與 size 下界的重要來源；random $k$-CNF 的 clause-space 下界亦可由相關 expansion/game 方法建立。

所以不等號隊提出第一個統合直覺：

$$
\boxed{
\text{Expansion／高耦合可能同時推高多種 quotient debt。}
}
$$

但這一項目前只是跨文獻的共同模式，不是一般演算法下界定理。

---

# 四、等號隊第一波反擊：同時擊敗十把武器，不等於擊敗所有武器

等號隊的回答很直接：

假設我們成功證明：

$$
A_1(F_n),A_2(F_n),\ldots,A_{100}(F_n)
$$

全部超多項式。

這最多得到：

$$
F_n
\text{ 對已列入的 100 種方法困難。}
$$

並不能得到：

$$
F_n\notin P.
$$

因為第九輪已經用 OBDD 反例明確看到：

$$
\text{一個 P-time function}
$$

仍可能對某個相當一般、相當有用的精確表示語言具有指數 representation lower bound。

所以：

$$
\boxed{
\text{多個 representation/proof lower bounds 的交集，仍不是 general time lower bound。}
}
$$

除非能額外建立「所有 P-time 演算法都必然誘導至少一種被我們量測的結構」的橋接定理。

這又回到第七輪的 Algorithm-to-Algebra Bridge Problem。

---

# 五、真正有趣的反轉：局部都容易，混起來反而難

這輪最值得保留的例子不是「某個公式同時很難」，而是相反：

> 每一種局部 constraint 類型單獨看都很容易，但它們混合後，整個問題類別可以進入 NP-complete 側。

## 5.1 Monotone 3-SAT 的最小示意

考慮兩種 clause：

$$
R_+(x,y,z)=x\lor y\lor z,
$$

以及：

$$
R_-(x,y,z)=\neg x\lor\neg y\lor\neg z.
$$

若公式只允許 $R_+$，令所有變數為 $1$ 即可滿足；若只允許 $R_-$，令所有變數為 $0$ 即可滿足。

即：

$$
\operatorname{SAT}(\{R_+\})\in P,
$$

$$
\operatorname{SAT}(\{R_-\})\in P.
$$

但允許正 monotone 3-clauses 與負 monotone 3-clauses 混合的 Monotone 3-SAT，已知有 NP-complete 版本；甚至在變數出現次數受到相當強限制時仍保持 NP-complete。

因此出現一個非常重要的現象：

$$
\boxed{
\text{Easy local languages}
+
\text{Easy local languages}
\not\Rightarrow
\text{Easy global language}.
}
$$

這裡的重點不是拿 NP-complete 偷渡成 non-P，而是：**局部 tractability 不具有簡單的加法封閉性。**

---

# 六、Schaefer dichotomy 給出的正式結構版本

Schaefer 的 Boolean CSP dichotomy 將固定 finite Boolean constraint language $\Gamma$ 分成 tractable 與 NP-complete 兩側。

其 tractable 情形不是「每個 constraint individually 很容易」而已，而是整個 language $\Gamma$ 共同落入某些 closure 類型，例如 Horn、dual-Horn、bijunctive、affine，以及 0-valid／1-valid 等情況。

代數語言中，可以將這件事理解成：所有 relations 之間必須共享足夠強的 polymorphism／保存運算。

所以若：

$$
\Gamma_1
$$

與：

$$
\Gamma_2
$$

各自有自己的 tractable structure，卻沒有足夠的共同保存結構，那麼：

$$
\Gamma_1\cup\Gamma_2
$$

可能落到 dichotomy 的 NP-complete 側。

這讓第七輪的 polymorphism 與本輪 MASC 連起來：

$$
\boxed{
\text{困難可能來自「可解結構之間的不相容」，而不只是「缺乏結構」。}
}
$$

---

# 七、從 Multi-Anti-Structure 升級成 Heterogeneous Gluing Debt

因此，本輪提出新的研究物件：

$$
\boxed{
\operatorname{HGD}
=
\text{Heterogeneous Gluing Debt}
}
$$

中文暫稱：**異質黏合債務**。

假設問題被分割成局部塊：

$$
F
=
F_1\land F_2\land\cdots\land F_m,
$$

每一個 $F_i$ 都屬於某個局部 tractable family：

$$
F_i\in\mathcal T_i.
$$

如果每個 $F_i$ 都能單獨在 polynomial time 求解，仍然不能直接推出 $F$ 容易，因為各塊共享 interface variables。

令：

$$
\partial F_i
$$

表示 $F_i$ 與其他區塊共享的邊界變數。

局部塊真正需要傳給全域系統的，不是單一 YES/NO，而是它對邊界賦值的可接受關係：

$$
R_i(\partial F_i)
=
\left\{
\alpha:
F_i\mid_{\partial F_i=\alpha}
\text{ 可延伸滿足}
\right\}.
$$

全域問題變成：

$$
\exists\text{ compatible }\alpha_1,\ldots,\alpha_m
$$

使所有局部 relation 同時成立。

因此：

$$
\boxed{
\text{局部求解成本低}
\not\Rightarrow
\text{局部摘要黏合成本低}.
}
$$

這就是 HGD。

---

# 八、最簡單的黏合帳本：Boundary State Explosion

如果某個區塊的 interface 有 $k$ 個 Boolean variables：

$$
|\partial F_i|=k,
$$

那麼最直接的 exact boundary table 有：

$$
2^k
$$

個可能邊界賦值。

若無其他結構，局部摘要大小可能是：

$$
\Theta(2^k).
$$

這就是 treewidth／separator-based dynamic programming 中熟悉的指數參數依賴來源。

但等號隊立刻提醒：

$$
2^k
\text{ 個邊界賦值}
$$

不代表真的需要 $2^k$ 個獨立狀態。

如果 relation $R_i$ 是 affine、cardinality、interval、matroidal 或其他可高度壓縮結構，它可能有很短的數學描述。

所以不能把：

$$
|\partial F_i|=k
$$

直接升格成：

$$
\text{需要 }2^k\text{ 時間}.
$$

真正要量的是**不同 boundary behavior 能否被精確商化**。

---

# 九、Boundary Semantic Quotient：把第二輪拉回來

對局部區塊 $F_i$ 的 boundary assignments $\alpha,\beta$，定義：

$$
\alpha\equiv_i\beta
$$

若它們對其餘全域問題具有完全相同的可延伸作用。

則真正的局部 interface state 數量不是：

$$
2^{|\partial F_i|},
$$

而是：

$$
N_i^{\partial}
=
\left|
\{0,1\}^{\partial F_i}/\!\equiv_i
\right|.
$$

定義：

$$
H_i^{\partial}
=
\log_2 N_i^{\partial}.
$$

這其實是第二輪「殘餘可分辨性」的區塊化版本。

於是 HGD 可以暫時被理解為：

$$
\operatorname{HGD}(F,\mathcal D)
=
\text{在分解 }\mathcal D\text{ 下，精確組合所有 boundary semantic quotients 的成本}.
$$

注意：這仍然依賴分解 $\mathcal D$，所以還不是一般不變量。

---

# 十、等號隊第二波反擊：黏合也可以被「再商化」

等號隊提出四種逃逸。

## 10.1 共同代數逃逸

即使兩個 block 用不同局部算法，只要其 boundary relations 在另一個代數中有共同短表示，就可以不用枚舉 interface table。

XOR 系統再次是最簡單例子：表面上 boundary assignments 很多，但線性子空間可用矩陣基底壓縮。

## 10.2 更換分解逃逸

一個分解的 interface 很大，不代表另一個分解也大。

因此任何 HGD 下界必須說明：

$$
\text{為什麼不存在另一個 polynomially constructible decomposition？}
$$

否則只是在證明某個 DP 架構困難。

## 10.3 全域演算法逃逸

演算法根本不需要「先解局部，再黏起來」。

例如 determinant／matching／flow 的高效算法都提醒我們：全域變換有時可以繞開人為設定的局部 decomposition。

## 10.4 隱藏新語言逃逸

也許 $\Gamma_1$ 與 $\Gamma_2$ 沒有 classical Schaefer polymorphism，但存在一個更高階表示，把兩種 constraints 一起送進另一種 tractable normal form。

這正是等號隊一直保留的「未知座標系」權利。

---

# 十一、不等號隊升級：不是「缺乏結構」，而是「共同結構崩塌」

不等號隊因此改變敘事。

過去我們一直找：

$$
\text{公式有沒有某個好結構？}
$$

現在改問：

$$
\boxed{
\text{各局部結構之間，是否存在一個可多項式維持的共同結構？}
}
$$

令每個局部 constraint family $\Gamma_i$ 有一組保存運算：

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

共同可用的保存結構至少要落在：

$$
\bigcap_i\operatorname{Pol}(\Gamma_i).
$$

若交集仍包含足夠強的 tractability operation，則局部結構可能可以被全域統一。

若交集快速崩塌，只剩 trivial projections 或不足以支撐已知 tractability 的運算，則局部演算法無法直接共享同一 closure。

這產生一個新的暫定量：

$$
\boxed{
\operatorname{PIS}(\Gamma_1,\ldots,\Gamma_m)
=
\text{Polymorphism Intersection Spectrum}
}
$$

中文可稱：**多型交集譜**。

它研究的不是「一個問題難不難」，而是：

$$
\text{局部可解代數在組合時還剩下多少共同結構。}
$$

---

# 十二、Monotone 3-SAT 作為「共同結構崩塌」玩具模型

回到：

$$
R_+=x\lor y\lor z,
$$

$$
R_-=\neg x\lor\neg y\lor\neg z.
$$

單獨看：

$$
R_+
$$

有全 1 的 trivial global assignment；

$$
R_-
$$

有全 0 的 trivial global assignment。

但混合後，這兩個「一招解」彼此直接衝突。

因此即使不使用完整 universal-algebra machinery，也能看見：

$$
\boxed{
\text{局部最佳摘要可能彼此不相容。}
}
$$

這種「摘要不相容」正是 HGD 的最小直覺模型。

它不是 $P\neq NP$ 證明，因為 Monotone 3-SAT 的 NP-completeness 仍只表示：若它在 $P$，則 $P=NP$。

但它非常適合用來測試：

> Hybrid Quotient Portfolio 是否真的能只靠「辨識每個局部 easy structure」就保證全域 polynomial？

答案至少是：**不能僅靠局部分類。**

---

# 十三、Knowledge Compilation 給出的另一種「黏合債務」證據

Knowledge compilation 中存在兩種與本輪極契合的現象。

第一，expander-based CNF 可以對 DNNF 產生 strongly exponential representation lower bound。這表示某些高連接公式不能被某一類相當強的 decomposable representation 低成本商化。

第二，更微妙的是：甚至當輸入最終存在很小的 structured DNNF 表示時，某些 bottom-up compilation paradigms 仍可能被迫產生指數大的中間結果。

這給 HGD 一個重要提醒：

$$
\boxed{
\text{最終摘要很小}
\not\Rightarrow
\text{構造／黏合摘要的路徑也很小。}
}
$$

所以完整帳本至少應區分：

$$
\operatorname{HGD}_{\mathrm{final}}
$$

與：

$$
\operatorname{HGD}_{\mathrm{path}}.
$$

後者研究中間表示爆炸。

這與原系列「構造成本不能藏到執行之前」的主張完全接軌。

---

# 十四、Backdoor 也從「單一捷徑」升級成「異質捷徑」

Backdoor 研究本身已經有 heterogeneous base classes：不同 backdoor assignments 可以把公式送入不同 tractable classes。

這對等號隊是一個真實加分：

$$
\text{不需要所有分支都進入同一種 easy language。}
$$

Hybrid solver 可以依分支使用不同結構。

但它也讓不等號隊得到新的檢查問題：

$$
\boxed{
\text{找到／表示／遍歷 heterogeneous backdoor 的成本是否仍保持 polynomial？}
}
$$

若 backdoor 大小為 $k$，典型窮舉仍帶來：

$$
2^k
$$

級分支；因此真正需要的是：

$$
k=O(\log n)
$$

或存在更進一步的 quotient／aggregation。

所以 heterogeneous structure 不是免費午餐，只是把「一種 easy structure」升級成「多種 easy structure 的導航」。

---

# 十五、Random / Expander 家族：適合當壓力測試，不適合被神話

Random CNF 與 expander-based formulas 在 resolution space/size、knowledge compilation 等多個受限框架中有很強下界，因此非常適合作為 MASC 壓力測試來源。

例如 random $k$-CNF 的 resolution clause space 可以有線性級下界，某些 treelike resolution size 亦有指數下界；expansion 是建立這些結果的重要組合工具之一。

但本輪禁止以下跳躍：

$$
\text{random formula 對 resolution hard}
\Rightarrow
P\neq NP.
$$

也禁止：

$$
\text{expander CNF 對 DNNF hard}
\Rightarrow
P\neq NP.
$$

這些公式的角色是：

$$
\boxed{
\text{測試候選「共同耦合機制」是否能同時解釋多個局部下界。}
}
$$

而不是直接充當傳統分離證明。

---

# 十六、MASC 的第一次降級：從「核心」改成「Portfolio-relative stress profile」

本輪決定暫時不把 MASC 當作本體性 hardness object。

更安全的定義是：

$$
\boxed{
\operatorname{MASC}_{\mathcal Q}(F)
=
\text{formula }F\text{ 對已指定 quotient portfolio }\mathcal Q\text{ 的反結構剖面。}
}
$$

用途是：

1. 系統找出現有方法的共同失效區；
2. 測試不同下界是否具有相同底層成因；
3. 尋找新 quotient 技術；
4. 生成下一輪的理論候選。

它不是：

$$
\text{general hardness certificate}.
$$

這一降級是本輪重要的自我校正。

---

# 十七、HGD 的第一版資源帳本

對一個分解：

$$
\mathcal D=(F_1,\ldots,F_m;I),
$$

其中 $I$ 是局部區塊間的 interface structure，定義暫定黏合債務向量：

$$
\mathbf D_G(F,\mathcal D)
=
(
D_{\mathrm{partition}},
D_{\mathrm{local}},
D_{\mathrm{boundary}},
D_{\mathrm{summary}},
D_{\mathrm{compat}},
D_{\mathrm{reconstruct}}
).
$$

其中：

- $D_{\mathrm{partition}}$：找到有用分解的成本；
- $D_{\mathrm{local}}$：各區塊求解／商化成本；
- $D_{\mathrm{boundary}}$：介面自由度；
- $D_{\mathrm{summary}}$：精確表示 boundary behavior 的成本；
- $D_{\mathrm{compat}}$：將不同局部摘要做全域一致化的成本；
- $D_{\mathrm{reconstruct}}$：由一致摘要恢復 witness／最終答案的成本。

若：

$$
D_{\mathrm{local}}\in\operatorname{poly}(n)
$$

但：

$$
D_{\mathrm{compat}}
$$

或：

$$
D_{\mathrm{summary}}
$$

爆炸，則局部容易仍不能推出全域容易。

---

# 十八、等號隊的新戰略：不要找「一個共同 polymorphism」，而是動態切換代數

等號隊拒絕被 PIS 綁死。

它提出：

> 為什麼全域算法一定要有一個固定共同 polymorphism？

也許演算法可以：

1. 在 affine 區塊使用 Gaussian elimination；
2. 在 Horn 區塊使用 implication propagation；
3. 在 bijunctive 區塊使用 implication graph；
4. 在 graph-like 區塊使用 separator DP；
5. 在剩餘核心使用 learning/search；
6. 在過程中持續重寫 interface，讓每一階段使用不同 algebra。

形式上：

$$
\mathcal A_t
\in
\{\mathcal A_{\mathrm{Horn}},\mathcal A_{\mathrm{aff}},\mathcal A_{2SAT},\ldots\}
$$

且：

$$
\mathcal A_t\neq\mathcal A_{t+1}
$$

完全允許。

這可稱為：

$$
\boxed{
\text{Dynamic Algebra Switching}
}
$$

若存在一個 polynomial-time orchestrator 自動切換代數並保持所有 interface polynomially succinct，就可能逃離「共同 polymorphism 崩塌」。

這是等號隊下一階段最強的新逃生門。

---

# 十九、不等號隊的新戰略：研究「切換本身」

不等號隊的回答是：好，那就把切換也記帳。

令算法使用表示／代數序列：

$$
\mathcal A_0
\rightarrow
\mathcal A_1
\rightarrow
\cdots
\rightarrow
\mathcal A_T.
$$

每次切換需要一個 exact bridge：

$$
B_t:
S_t
\rightarrow
S_{t+1}.
$$

於是總成本包含：

$$
\sum_t C(B_t).
$$

新的問題不是：

$$
\text{有沒有單一共同 algebra？}
$$

而是：

$$
\boxed{
\text{是否存在一條 polynomial-cost algebra switching path？}
}
$$

注意這再次很接近第六輪的 representation closure paradox，因此下一輪必須避免把「所有 polynomial bridges」直接放進定義。

---

# 二十、這輪最重要的思維實驗：兩個一招解的世界，黏起來後怎麼辦？

世界 A：所有 constraint 都可由：

$$
\mathbf x=\mathbf 1
$$

解掉。

世界 B：所有 constraint 都可由：

$$
\mathbf x=\mathbf 0
$$

解掉。

單獨：

$$
T_A(n)=O(n),
$$

$$
T_B(n)=O(n).
$$

現在交錯混合 A 與 B 的 constraints。

問題不再是「A 難不難」或「B 難不難」，而是：

$$
\boxed{
\text{如何找到一個同時滿足兩套互相競爭局部偏好的全域 assignment？}
}
$$

這就是異質黏合問題的最低階版本。

影片最初展示：

$$
\text{多個規則可以被壓成一個函數。}
$$

本輪則把問題反過來：

$$
\boxed{
\text{當多個各自可壓縮的規則系統彼此耦合，是否還能再壓成一個 polynomial-size 函數？}
}
$$

這正是接下來值得繼續玩的核心。

---

# 二十一、障礙審查

## 21.1 NP-complete 不等於 unconditional non-P

Monotone 3-SAT、Schaefer hard side 等結果只能證明 NP-completeness。

若直接寫：

$$
\text{NP-complete}\Rightarrow\text{不存在 polynomial algorithm},
$$

就是把 $P\neq NP$ 當前提。

**狀態：已封鎖。**

## 21.2 多模型 lower bound 疊加不等於 general lower bound

Resolution、DNNF、OBDD、backdoor、treewidth 等可以一起當 stress test，但沒有橋接定理時不能相乘成一般下界。

**狀態：已封鎖。**

## 21.3 HGD 不能定義成「最佳剩餘求解時間」

否則：

$$
\operatorname{HGD}(F)=\min_A T_A(F)
$$

只是原問題換名。

**狀態：已封鎖。**

## 21.4 動態代數切換可能重演閉包悖論

若允許任意 polynomial-time bridge，則「能否 polynomial switching 到 tractable target」再次與 $L\in P$ 同義。

**狀態：下一輪重點。**

---

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

1. 「一個公式同時對 OBDD、DNNF、resolution 都難，所以 $P\neq NP$。」——不成立。
2. 「Random 3-SAT 很難，所以它就是一般下界家族。」——只在特定模型／平均分布研究中成立相應結果。
3. 「高 treewidth 必然不在 P。」——錯；很多 P 問題可有高 treewidth 實例，且算法未必依 treewidth 分解。
4. 「沒有小 backdoor 就沒有 polynomial algorithm。」——錯；backdoor 是一類捷徑，不是所有捷徑。
5. 「每個局部 block 在 P，所以全域一定在 P。」——錯；黏合可破壞共同 tractable structure。
6. 「局部 tractable languages 混合後 NP-complete，所以證明了 $P\neq NP$。」——循環。
7. 「所有 tractable 結構必須共享一個固定 polymorphism。」——對固定 CSP language 很有力，但尚不能限制一般動態算法。
8. 「MASC 是本體性的 hardness core。」——目前只能是 portfolio-relative stress profile。

---

# 二十三、本輪暫定成果

## 23.1 MASC 被重新定位

$$
\operatorname{MASC}_{\mathcal Q}
$$

只表示對已知 quotient portfolio 的多重反結構壓力，不代表一般不可解性。

## 23.2 找到新的共同問題：異質黏合債務

$$
\boxed{
\operatorname{HGD}
}
$$

把局部 tractability 與全域 compatibility 分開計量。

## 23.3 Schaefer 給出「結構不相容」的正式樣板

Boolean CSP 的 tractability 依賴整個 constraint language 的共同 closure／polymorphism，而不是每一個 constraint 單獨是否容易。

因此：

$$
\boxed{
\text{Hardness-like behavior 可以來自「好結構的交集崩塌」。}
}
$$

## 23.4 引入 PIS

$$
\operatorname{PIS}(\Gamma_1,\ldots,\Gamma_m)
$$

追蹤局部 tractable languages 合併時共同 polymorphism 的剩餘結構。

## 23.5 等號隊提出 Dynamic Algebra Switching

不要求一個固定共同 closure，而允許算法依時間切換不同 algebra／representation。

這將下一輪問題推向：

$$
\boxed{
\text{局部代數之間的 bridge 是否可以始終 polynomially cheap？}
}
$$

---

# 二十四、本輪比分

不等號隊：

- 成功把「很多方法都失效」升級成「局部可解結構的相容性可能才是核心」；
- 引入 HGD 與 PIS；
- 以 expander、resolution、knowledge compilation 等結果支持「高耦合會在多個局部模型中留下債務」的研究方向。

等號隊：

- 成功阻止 MASC 被誤升格為一般時間下界；
- 指出局部 polymorphism 不相容仍可能被 dynamic representation/algebra switching 繞過；
- 保留「未知全域座標系」逃生門。

本輪比分：

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

又平手。

這不是故意控分；只是兩邊目前都還沒有拿到能跨越模型邊界的致命武器。

---

# 二十五、第十一輪入口

下一輪暫定題目：

## 共同保存結構崩塌與動態代數切換

核心對決：

### 不等號隊

研究：

$$
\operatorname{Pol}(\Gamma_1)
\cap
\operatorname{Pol}(\Gamma_2)
\cap\cdots
$$

如何隨異質 constraints 混合而崩塌，並嘗試把這種崩塌連接到 interface/gluing debt。

### 等號隊

不接受「必須共享一個固定 polymorphism」，提出：

$$
\Gamma_1
\xrightarrow{B_1}
\Gamma_2
\xrightarrow{B_2}
\cdots
\xrightarrow{B_T}
\mathcal T
$$

的 dynamic algebra switching，嘗試證明局部沒有共同 algebra 也能沿一條 polynomial bridge path 求解。

### 共同問題

$$
\boxed{
\text{能否定義一個不循環的「代數切換成本」，並找出其不可壓縮的結構來源？}
}
$$

---

# 二十六、歷史依賴

本輪直接依賴：

1. **第二輪**：殘餘可分辨性——被重新解讀成 boundary semantic quotient；
2. **第四輪**：局部—全域障礙——本輪將其升級為異質局部 tractability 的黏合問題；
3. **第六輪**：表示閉包悖論——限制 Dynamic Algebra Switching 不能任意放寬；
4. **第七輪**：polymorphism／Algorithm-to-Algebra Bridge——本輪形成 PIS；
5. **第八輪**：PEQS／Exact Quotientability——本輪把 quotient 推向 block interface；
6. **第九輪**：Hybrid Quotient Portfolio／Quotient Debt——本輪建立 MASC 與 HGD。

與 Neo.K 舊動態速率系列的關係：舊系列強調問題難度會隨智慧體的結構識別、知識與表示能力改變；本輪把這一點轉成更細的演算法問題——統籌者不只要辨認「哪個局部結構容易」，還必須處理不同容易結構之間的全域相容性。這與七角色框架中的 ORCH（統籌者）角色直接相接。

---

# 二十七、外部理論參照

1. Thomas J. Schaefer, **The Complexity of Satisfiability Problems**, STOC 1978.
   - Boolean CSP dichotomy；固定 Boolean constraint languages 的 tractable／NP-complete 分界。
2. Andreas Darmann, Janosch Döcker 等，**Monotone 3-SAT** 系列結果（2016–2021）。
   - 顯示正 monotone clauses 與負 monotone clauses 混合後，即使施加強出現次數限制仍可保持 NP-complete。
3. Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky, **A Strongly Exponential Separation of DNNFs from CNF Formulas**, 2014/2016.
   - expander-based CNF 對 DNNF 的 strongly exponential size lower bounds。
4. Antoine Amarilli, Mikaël Monet, Pierre Senellart, **Connecting Width and Structure in Knowledge Compilation**, 2017.
   - 將 treewidth/pathwidth 與 structured representations 的 upper/lower bounds 連結。
5. Alexis de Colnet, Stefan Mengel, **Lower Bounds on Intermediate Results in Bottom-Up Knowledge Compilation**, AAAI 2022.
   - 即使最終存在很小 structured representation，bottom-up compilation 仍可能被迫生成 exponential intermediate results。
6. Marko Samer, Stefan Szeider, **Backdoor Trees**, AAAI 2008；Serge Gaspers et al., **Backdoors into Heterogeneous Classes of SAT and CSP**, AAAI 2014.
   - hidden structure、strong backdoors 與 heterogeneous tractable base classes。
7. Eli Ben-Sasson, Nicola Galesi, **Space Complexity of Random Formulae in Resolution**, 2001.
   - random $k$-CNF 的 resolution space lower bounds 與 expansion 關係。
8. Eli Ben-Sasson, Avi Wigderson, **Short Proofs Are Narrow—Resolution Made Simple**, 1999/2001.
   - resolution width 與 proof size 關係，並將 expansion 用於多個下界。

---

## 第十輪一句話結論

$$
\boxed{
\text{真正值得追的「反結構」，可能不是沒有好結構，而是多個好結構無法低成本黏成同一個全域結構。}
}
$$

更進一步：

$$
\boxed{
\text{下一個戰場不再是 SAT 有沒有 Blossom，而是很多局部 Blossom 能不能 polynomially 黏成一朵更大的花。}
}
$$