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

## 複雜度勢能遊戲：攤銷可解證書、勢函數逃逸與證書完備性陷阱

**Complexity Potential Game: Amortized Tractability Certificates, Potential Escape, and the Certificate-Completeness Trap**

- **主導研究者：** Neo.K（許筌崴）
- **協作整理：** Aletheia
- **機構：** EveMissLab（一言諾科技有限公司）
- **日期：** 2026 年 8 月 1 日
- **版本：** v1.0
- **研究狀態：** 第十四輪雙假設預演
- **前置文件：** `13_第十三輪_可解閉包穩定性與多項式鏈爆炸.md`
- **遊戲態度：** 等號隊與不等號隊繼續互相拆台
- **文件標準：** 正式命題、候選猜想、思想實驗、外部參照與遊戲比分分開記錄

---

## 摘要

第十三輪證明：即使動態表示轉換的每一步都相對於當前表示大小為多項式時間，若轉換深度隨輸入增長、或中間表示持續膨脹，整條 trajectory 仍可能超出任何固定多項式界。因此，等號隊提出 **Amortized Tractability Certificate（ATC）**：不再逐步宣稱「這一步容易」，而是尋找一個全域勢函數（potential function），以攤銷方式控制整條表示／bridge／quotient 路徑的總成本。

本輪首先把這個想法接到標準 amortized analysis。若第 $t$ 步實際成本為 $c_t$，狀態勢能為 $\Phi_t\ge 0$，定義攤銷成本

$$
\widehat c_t
=
c_t+\Phi_{t+1}-\Phi_t.
$$

則由望遠鏡求和：

$$
\sum_{t=0}^{m-1}c_t
=
\sum_{t=0}^{m-1}\widehat c_t
+
\Phi_0-\Phi_m.
$$

因此，只要初始勢能與總攤銷成本皆受原始輸入大小的固定多項式控制，且 $\Phi_m\ge0$，整條實際計算成本便為多項式。這給出一個真正嚴格的「動態切換全程成本證書」模板。

然而，本輪隨即發現一個重要不對稱。對 $P=NP$ 方而言，只需存在**一個** SAT 多項式演算法及其演算法專屬勢函數即可；所以先前要求 potential 必須 solver-independent，對等號隊而言過強。相反地，若 $P\neq NP$ 方想以「找不到某種勢函數」作為下界，就必須先證明該勢函數語言對所有多項式時間演算法具有完備性。否則，沒有證書只代表證書系統太弱，不代表演算法不存在。

這形成本輪核心的 **Potential Certificate Completeness Trap（勢函數證書完備性陷阱）**：

$$
\text{證書系統太弱}
\Rightarrow
\text{漏掉真正的 }P\text{ 演算法},
$$

$$
\text{證書系統太強}
\Rightarrow
\text{容易把「最佳剩餘求解時間」等原問題本身偷藏進 potential}.
$$

外部程式分析研究提供了很好的參照：potential-based automatic amortized resource analysis 確實可以在受限程式語言中推導 polynomial runtime bounds，某些受限 typability 結果甚至與 PTIME 對應；但對一般 Turing machine，「是否在 polynomial time 內運行」本身不可由單一演算法普遍判定。因此，勢函數非常適合做**構造性上界證書**，卻不能在未建立證書系統完備性前被直接反轉成一般下界。

本輪最後將 ATC 升級為雙層證書：

1. **Progress / Ranking Layer**：控制 trajectory 深度與終止；
2. **Amortized Potential Layer**：控制總資源支出。

並將第十五輪推進到「Tractability Proof System」：是否能建立一個非循環、可檢查、對足夠廣泛演算法具有完備性的多項式可解性證明語言？

---

# 一、上一輪留下的問題

第十三輪得到：

$$
\boxed{
\text{Stepwise Polynomiality}
\not\Rightarrow
\text{Pathwise Polynomiality}
}
$$

例如：

$$
s_{t+1}=s_t^2
$$

每一步皆為多項式變換，但經過 $m$ 步：

$$
s_m=n^{2^m}.
$$

因此 Dynamic Tractable Closure Scheme 不能只證明每一個：

$$
R_t\rightarrow R_{t+1}
$$

容易，而必須控制整條：

$$
R_0\rightarrow R_1\rightarrow\cdots\rightarrow R_m
$$

的峰值大小、累積成本與深度。

等號隊因此提出：

$$
\boxed{\mathrm{ATC}
=
\text{Amortized Tractability Certificate}}
$$

本輪要問：

> 能不能像 amortized data structures 一樣，用一個全域勢能帳本證明 SAT 的動態 quotient／bridge portfolio 雖然某些步驟很昂貴，但總成本仍為 polynomial？

---

# 二、標準 potential method：真正可用的數學模板

令第 $t$ 步的演算法狀態為：

$$
Z_t,
$$

其中可同時包含：

$$
Z_t
=
(R_t,\mathcal B_t,\mathcal M_t,\mathcal D_t,\ldots),
$$

例如：

- 當前表示 $R_t$；
- 當前 bridge language $\mathcal B_t$；
- 記憶／learned information $\mathcal M_t$；
- 尚未結清的 quotient／bridge debt $\mathcal D_t$。

令實際第 $t$ 步成本為：

$$
c_t\ge0.
$$

選擇非負勢函數：

$$
\Phi:Z\rightarrow\mathbb R_{\ge0}.
$$

記：

$$
\Phi_t=\Phi(Z_t).
$$

定義攤銷成本：

$$
\boxed{
\widehat c_t
=
c_t+\Phi_{t+1}-\Phi_t
}
$$

則：

$$
c_t
=
\widehat c_t+\Phi_t-\Phi_{t+1}.
$$

對全部步驟求和：

$$
\boxed{
\sum_{t=0}^{m-1}c_t
=
\sum_{t=0}^{m-1}\widehat c_t
+
\Phi_0-\Phi_m
}.
$$

這就是標準 potential method 的望遠鏡結構。

---

# 三、ATC 上界命題

## 命題 3.1：多項式攤銷證書

假設對長度為 $n$ 的輸入，候選演算法 $A$ 的計算軌跡：

$$
Z_0,Z_1,\ldots,Z_m
$$

滿足：

$$
m\le q(n),
$$

其中 $q$ 為固定多項式；

且存在非負勢函數 $\Phi_A$，使：

$$
\Phi_A(Z_0)\le r(n),
$$

其中 $r$ 為固定多項式；

並且每一步攤銷成本滿足：

$$
\widehat c_t
=
c_t+\Phi_A(Z_{t+1})-\Phi_A(Z_t)
\le p(n),
$$

其中 $p$ 為固定多項式。

則：

$$
\sum_{t=0}^{m-1}c_t
\le
q(n)p(n)+r(n),
$$

故總運行成本為多項式。

### 證明

由望遠鏡公式與 $\Phi_m\ge0$：

$$
\sum c_t
=
\sum\widehat c_t+\Phi_0-\Phi_m
\le
\sum\widehat c_t+\Phi_0.
$$

又因：

$$
m\le q(n),
\qquad
\widehat c_t\le p(n),
$$

所以：

$$
\sum\widehat c_t
\le
q(n)p(n).
$$

因此：

$$
\sum c_t
\le
q(n)p(n)+r(n),
$$

為固定多項式。□

---

# 四、第一個重要校正：勢函數不是演算法

若某個 SAT 求解器根本沒有一條多項式時間的實際 computation trace，寫出再漂亮的 potential 也不能使它突然變成 polynomial。

勢函數做的是：

$$
\boxed{
\text{證明／分析既有 computation 的總成本}
}
$$

而不是：

$$
\boxed{
\text{替 computation 執行尚未完成的工作}
}
$$

因此：

$$
\text{Potential Method}
\neq
\text{新的計算模型}.
$$

它是 meta-level cost certificate。

這與最初影片的「數學構造可成為演算法」不同：

- 影片中的函數本身進入狀態轉移，屬於物件層計算；
- 本輪 potential 若只用來分析總成本，屬於元層證明。

如果要讓 $\Phi$ 真正成為演算法的一部分，它就必須能被有效計算並參與決策，此時其計算成本也必須重新記入：

$$
T_{\mathrm{total}}.
$$

---

# 五、第二個重要校正：solver-independent 對等號隊太強

第十三輪曾把理想 potential 描述為 solver-independent、answer-blind、cross-representation、non-circular。

本輪發現第一項需要拆成兩種用途。

## 5.1 對 $P=NP$ 方

要證明：

$$
P=NP,
$$

只需要存在**一個** deterministic polynomial-time SAT algorithm：

$$
A^\star.
$$

因此完全允許使用：

$$
\Phi_{A^\star}.
$$

也就是 algorithm-specific potential。

這與一般 amortized analysis 完全一致：一個 data structure 的勢函數不需要同時分析所有 data structures。

所以：

$$
\boxed{
P=NP\text{ 方不需要 universal potential。}
}
$$

## 5.2 對 $P\neq NP$ 方

若想證明：

$$
P\neq NP,
$$

就必須排除所有候選算法。

若不等號隊想說：

> 「我證明 SAT 沒有這種 potential，所以它不在 P。」

它必須先建立：

$$
A\in P
\Longrightarrow
A\text{ 必然具有該類 potential certificate}.
$$

也就是證書系統的**完備性**。

否則某個 polynomial algorithm 可能只是沒有落入這個 proof template。

因此：

$$
\boxed{
\text{Potential 很適合證明上界，}
}
$$

$$
\boxed{
\text{但「沒有 potential」通常不能直接證明下界。}
}
$$

---

# 六、Potential Certificate Completeness Trap

令：

$$
\mathfrak P
$$

是一個勢函數證書語言，例如：

- 線性 potential；
- 多項式 potential；
- 固定維度 feature potential；
- lexicographic ranking；
- treewidth/backdoor/width 的加權組合；
- automatic amortized resource analysis type。

若：

$$
A\text{ 沒有 }\mathfrak P\text{-certificate},
$$

只能推出：

$$
A\notin\operatorname{Cert}(\mathfrak P).
$$

除非另外證明：

$$
P
\subseteq
\operatorname{Cert}(\mathfrak P).
$$

這就是：

$$
\boxed{
\text{Potential Certificate Completeness Trap}
}
$$

### 弱證書系統

若：

$$
\operatorname{Cert}(\mathfrak P)
\subsetneq P,
$$

那麼證書缺失不能作為 $P$ 下界。

### 過強證書系統

若允許：

$$
\Phi_A(Z)
=
\text{從 }Z\text{ 出發的最佳剩餘運行時間},
$$

它當然精確描述成本，但「刻畫 $\Phi_A$」已經把原問題全部塞回 potential。

或者定義：

$$
\Phi(F)
=
\min_A T_A(F),
$$

則「$\Phi$ 是否 polynomial」幾乎就是原問題本身。

因此：

$$
\boxed{
\text{過強 potential}
\Rightarrow
\text{循環／同義反覆}.
}
$$

---

# 七、外部參照：AARA、ranking function 與一般 runtime verification

Potential-based resource analysis 在程式分析中已有成熟形式。Automatic Amortized Resource Analysis（AARA）使用 type system／potential annotations 推導 resource bounds；已有工作建立 polynomial potential type systems，並在受限 fragments 中研究 typability 與 PTIME 的關係。

這對本輪有兩個相反啟示：

1. 夠好的 potential proof language 的確可以涵蓋很大的 polynomial-time program family；
2. 這種 completeness 必須在明確限制下被嚴格證明，不能從「potential 很自然」直接跳出。

另一方面，對一般 Turing machine，已有結果證明：不存在一個演算法能對所有機器普遍判定「是否以某個 polynomial time bound 運行」。因此不能期待一個萬能、全自動、sound+complete 的 polynomial-runtime analyzer。

Ranking function 則主要用於證明終止。已有研究也顯示，某些終止系統雖有 ranking function，但 ranking expression 本身可能需要非常大的表示。因此：

$$
\text{存在 certificate}
\neq
\text{存在小 certificate}.
$$

但 certificate 很大仍不會自動改變被分析算法本身的 complexity class。

---

# 八、ATC 升級：雙層證書

單一 $\Phi$ 同時控制 trajectory 終止、bridge depth、representation size 與 runtime 容易混淆。

本輪因此把 ATC 升級成雙層。

## 8.1 Progress / Ranking Layer

定義：

$$
\rho(Z_t)
$$

取值於良基序集合，要求：

$$
\rho(Z_{t+1})<\rho(Z_t)
$$

對真正的高層 transition 成立。

若：

$$
\rho(Z_0)\le q(n)
$$

且每一步至少下降一個離散單位，則：

$$
m\le q(n).
$$

它控制：

$$
\boxed{\text{Bridge Depth / Termination}}
$$

## 8.2 Amortized Potential Layer

使用：

$$
\Phi(Z_t)\ge0
$$

控制總資源：

$$
\widehat c_t
=
c_t+\Phi(Z_{t+1})-\Phi(Z_t).
$$

若：

$$
\widehat c_t\le p(n),
\qquad
\Phi(Z_0)\le r(n),
$$

則：

$$
T_{\mathrm{total}}
\le
q(n)p(n)+r(n).
$$

完整證書寫成：

$$
\boxed{
\mathrm{ATC}(A)
=
(\rho_A,\Phi_A,p,q,r)
}
$$

---

# 九、等號隊出牌：Adaptive Potential Portfolio

等號隊提出：

> 既然表示一直變，我為什麼一定要用一個固定 structural potential？

它提出分段勢函數：

$$
\Phi^{(1)},
\Phi^{(2)},
\ldots,
\Phi^{(k)}
$$

分別對應：

- CNF elimination；
- XOR subsystem；
- compiled component；
- bridge coordination；
- learned-clause phase。

只要 phase switch 時存在：

$$
\Phi^{(j+1)}(Z)
\le
a\Phi^{(j)}(Z)+b(n),
$$

且所有切換累積仍有 global polynomial budget，即可建立 piecewise ATC。

等號隊的新口號：

$$
\boxed{
\text{我不需要全域同一把尺，}
}
$$

$$
\boxed{
\text{只需要證明換尺本身也付得起。}
}
$$

---

# 十、不等號隊反擊：四種勢能逃逸

## 10.1 Plateau

存在長軌跡，但：

$$
\Phi(Z_{t+1})\approx\Phi(Z_t),
$$

沒有足夠 potential drop 支付實際成本。

## 10.2 Cycle

表示在：

$$
R^{(A)}
\rightarrow
R^{(B)}
\rightarrow
R^{(C)}
\rightarrow
R^{(A)}
$$

間循環。

若每套局部 potential 都在自己的座標中下降，但切換後又重新「充滿能量」，可能產生 double-counting。

## 10.3 Hidden Debt

某個 potential 下降，但：

$$
\text{precision},
\text{representation size},
\text{witness lift},
\text{bridge arrangement}
$$

中的其他成本暴增。

## 10.4 Coordinate Escape

一種表示中的 potential 很大，轉換到另一表示後突然變小，但實際語義工作並沒有被完成。

所以每次 coordinate change 都必須有：

$$
D_{\mathrm{switch}}
$$

與可證明的 bridge inequality。

---

# 十一、有限 structural feature potential 不自動完備

假設：

$$
\Phi(F)
=
a_1\operatorname{tw}(F)
+
a_2\operatorname{bd}(F)
+
a_3\operatorname{width}(F)
+
a_4\operatorname{sym}(F)
+\cdots
$$

這可以是很好的 empirical / heuristic potential，但不能自動成為 P/NP 證明工具。

理由包括：

1. 某些 P 問題也可能在其中某些指標上很大；
2. 未知演算法可能利用未列入的新結構；
3. 不同表示可改變參數；
4. fixed finite feature vector 的 completeness 沒有證明。

已有 SAT solver 實證研究也顯示，treewidth、backdoor、backbone、community structure 等單項指標與 CDCL runtime 的解釋力有限，多參數組合往往較好。

這支持：

$$
\text{單一結構參數往往不足}
$$

但不支持：

$$
\text{有限參數向量已足以證明一般 SAT 下界}.
$$

---

# 十二、本輪最重要的不對稱

## $P=NP$ 方

只需：

$$
\boxed{
\exists A\;
\exists \mathrm{ATC}_A
}
$$

使 $A$ 精確判定 SAT，且 ATC 證明：

$$
T_A(n)\in\operatorname{poly}(n).
$$

## $P\neq NP$ 方

若想用「ATC 不存在」證明分離，就需要先建立：

$$
\boxed{
\forall A\;
[
A\in P
\Rightarrow
\exists \mathrm{ATC}_A
]
}
$$

再加：

$$
\forall A\text{ solving SAT},
\quad
\neg\exists\mathrm{ATC}_A.
$$

第一條本身就是：

$$
\boxed{
\text{證書系統完備性}
}
$$

因此：

$$
\boxed{
\text{勢函數方法對 }P=NP\text{ 與 }P\neq NP\text{ 不是對稱武器。}
}
$$

它天然偏向 upper-bound / constructive side。

---

# 十三、元層成本與物件層成本再次分離

本輪建立三個層次：

### Level 1：Object Runtime

$$
T_A(n).
$$

這是傳統 $P/NP$ 真正分類的對象。

### Level 2：Runtime Certificate Complexity

$$
C_{\mathrm{cert}}(A).
$$

證明 $A$ 的 runtime bound 要多複雜。

### Level 3：Discovery Complexity

$$
C_{\mathrm{discover}}(A,\mathrm{ATC}).
$$

智慧體找到演算法與證明要付出的認知成本。

三者可以耦合，但不能偷換：

$$
C_{\mathrm{cert}}\text{ 很大}
\not\Rightarrow
T_A(n)\text{ 很大}.
$$

---

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

以下論證不得再單獨用於傳統 $P\neq NP$：

1. 「我找不到漂亮勢函數，所以 SAT 不在 P。」
2. 「某個 structural potential 無法下降，所以任何演算法都慢。」
3. 「某個自動 resource analyzer 分析失敗，所以程式不是 polynomial。」
4. 「runtime certificate 很大，所以 algorithm 本身很慢。」
5. 「勢函數值下降，所以實際計算一定有進展。」——除非有 transition inequality。
6. 「不同 phase 各自有 local potential，所以全域自動可攤銷。」——仍需 bridge accounting。
7. 「定義 $\Phi$ 為最佳剩餘求解時間，再用 $\Phi$ 證明求解時間。」——循環。

---

# 十五、本輪正式成果

## 15.1 Polynomial ATC Proposition

建立：

$$
(\rho_A,\Phi_A,p,q,r)
$$

作為 pathwise polynomiality 的嚴格上界證書模板。

## 15.2 Potential Is Meta, Not Magic

勢函數本身不是求解器，只是對既有 computation 的總成本證明。

## 15.3 Solver-Independence Correction

對 $P=NP$ 方：

$$
\text{algorithm-specific potential 完全合法}.
$$

對 $P\neq NP$ 方：

$$
\text{要由 certificate failure 推下界，必須先證明 certificate completeness}.
$$

## 15.4 Potential Certificate Completeness Trap

證書語言：

$$
\text{太弱}
\Rightarrow
\text{漏掉 }P,
$$

$$
\text{太強}
\Rightarrow
\text{循環／同義反覆／不可有效判定風險}.
$$

## 15.5 Dual Certificate

將：

$$
\text{Progress / Ranking}
$$

與：

$$
\text{Amortized Resource Potential}
$$

分離。

---

# 十六、雙方戰果

## 等號隊

得到：

$$
\boxed{
\exists A,\rho_A,\Phi_A
\Rightarrow
\text{若滿足 ATC inequalities，則 pathwise polynomial}.
}
$$

它不需要找到 universal potential，只需要替自己的 SAT algorithm 建立有效 amortized proof。

## 不等號隊

成功阻止：

$$
\text{「某個 potential family 失敗」}
\Rightarrow
P\neq NP.
$$

並把新戰場推進到：

$$
\boxed{
\text{Tractability Certificate Completeness}
}
$$

---

# 十七、本輪比分

$$
P=NP:13
$$

$$
P\neq NP:13
$$

雙方再度各得一分。

目前看來，「平手」已經不是比分，而是一種宇宙常數。歪臉笑。

比分僅為遊戲介面，不具任何證明意義。

---

# 十八、第十五輪入口：Tractability Proof System

下一輪正式研究：

$$
\boxed{
\text{多項式可解性證書語言能否同時具有 soundness、廣泛 completeness 與 non-circularity？}
}
$$

候選問題：

1. 是否存在 restricted algorithm normal form，使 polynomial runtime 可由簡短 certificate 驗證？
2. 若證書系統 sound 但 incomplete，對 $P\neq NP$ 還有什麼價值？
3. 若要求對任意 Turing machine complete，是否直接撞上 runtime-property undecidability？
4. 是否可以只要求對「SAT quotient/bridge portfolio architecture」完備，而不是對所有程式完備？
5. 能否建立：

$$
\mathcal A_0
\subset
\mathcal A_1
\subset
\cdots
$$

的 solver architecture hierarchy，逐層配套 sound+complete tractability certificates？
6. 如果：

$$
\bigcup_i\mathcal A_i
$$

足夠覆蓋所有 polynomial SAT algorithms，這個覆蓋性本身是否又接近原問題？

---

# 十九、歷史依賴

本輪直接依賴：

1. `13_第十三輪_可解閉包穩定性與多項式鏈爆炸.md`
   - Stepwise / Pathwise Polynomiality；
   - Tractable Closure Stability；
   - ATC 初始構想。

並回接：

2. `09_第九輪_尋找SAT的Blossom與商化債務.md`
   - Quotient Debt。
3. `11_第十一輪_共同保存結構崩塌與動態橋接.md`
   - Bridge Coordination Debt。
4. `12_第十二輪_介面語言格_Schaefer臨界與遞迴SAT.md`
   - Dynamic Tractable Closure Scheme。
5. 原始 P/NP 動態速率系列
   - 元層 discovery cost 與 object-level execution cost 的區分。

---

# 二十、外部理論參照

1. MIT OpenCourseWare, **6.046J Design and Analysis of Algorithms — Amortized Analysis / Potential Method**.
   - https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/

2. Martin Hofmann, Georg Moser, **Amortised Resource Analysis and Typed Polynomial Interpretations**, 2014.
   - https://arxiv.org/abs/1402.1922

3. Long Pham, Jan Hoffmann, **Typable Fragments of Polynomial Automatic Amortized Resource Analysis**, 2020.
   - https://arxiv.org/abs/2010.16353

4. David Gajser, **Verifying Time Complexity of Deterministic Turing Machines**, 2013.
   - https://arxiv.org/abs/1307.3648

5. Amir M. Ben-Amram, Chin Soon Lee, **Ranking Functions for Size-Change Termination II**, 2009.
   - https://arxiv.org/abs/0903.4382

6. Edward Zulkoski et al., **Relating Complexity-theoretic Parameters with SAT Solver Performance**, 2017.
   - https://arxiv.org/abs/1706.08611

---

## 本輪裁定

$$
\boxed{
\text{勢函數是一把很強的上界武器，但不是天然的下界武器。}
}
$$

更精確地說：

$$
\boxed{
\exists A+\exists\mathrm{ATC}_A
}
$$

可以成為 $P=NP$ 路線中的構造性證書；

但：

$$
\boxed{
\neg\exists\mathrm{ATC}
}
$$

只有在 ATC 證書語言對所有 $P$ 演算法已被證明完備時，才可能支撐 $P\neq NP$。

因此，第十四輪沒有得到 $P=NP$ 或 $P\neq NP$，卻把「複雜度勢能」從模糊比喻校正成一套嚴格的上界證明工具，並把真正的新戰場推到：

$$
\boxed{
\text{Tractability Proof-System Completeness}.
}
$$