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

## 演算法軌跡切割與因果瓶頸：任何精確求解器都必須暴露可分辨瓶頸嗎？

**Round 03: Algorithm-Trajectory Cuts and Causal Bottlenecks**

- **主導研究者：** Neo.K（許筌崴）
- **協作整理：** Aletheia
- **機構：** EveMissLab（一言諾科技有限公司）
- **日期：** 2026 年 8 月 1 日
- **版本：** v1.0
- **研究狀態：** 第三輪雙假設預演
- **前置文件：** `00`、`01`、`02`
- **遊戲態度：** 等號隊與不等號隊繼續互相拆台；失敗路線照樣存檔
- **文件標準：** 不把局部下界冒充 $P\neq NP$ 證明

---

## 摘要

第二輪的「殘餘可分辨負載」在固定切割、固定資訊流的狀態機中形成了真正的語義下界，但等號隊可以透過變數重排、重新讀取輸入、全域摘要、擴維與改換表示逃逸。第三輪因此取消外部指定的變數切割，直接研究演算法自己的計算歷史：

$$
C_0(x)\to C_1(x)\to\cdots\to C_T(x).
$$

不等號隊提出「軌跡切割」：若任意精確求解器都必須在某個時間點把大量彼此語義不同的歷史壓入有限配置，那麼配置容量不足時，未保存的差異只能透過未來重新讀取、重算或其他轉換重新取得。因此可能存在一個「狀態—重建」權衡，而非單純的空間下界。

等號隊則指出，普通圖靈機或 RAM 的未來仍能重新存取輸入；兩個輸入即使在某一時刻具有相同工作狀態，也不必具有相同未來，因為它們仍攜帶不同的唯讀輸入。於是單一時間切割並不是真正的因果斷面。若把整個輸入也算入切割狀態，則最多只有 $n$ 位輸入資訊，資訊量計數本身不足以推出超多項式時間。

本輪因此得到一個重要負結果：**Shannon 型資訊量或配置數量不足以直接支撐 $P\neq NP$；真正需要下界化的可能是「從壓縮表示與可再次存取的輸入中重建正確全域判定所需的結構轉換成本」。**

本輪把候選核心從「可分辨資訊量」升級為「因果重建複雜度」（Causal Reconstruction Complexity, CRC），但同時確認：若直接把 CRC 定義成最小求解時間，它會循環。第四輪因此轉向尋找可獨立刻畫 CRC 的局部—全域障礙。

---

# 一、第三輪開場：把切割交還給演算法自己

第二輪定義了部分賦值後的殘餘函數數量：

$$
N_{\mathrm{res}}(\varphi,S),
$$

並證明在「讀過 $S$ 後不再回頭」的狀態機模型中：

$$
|Q_S|\ge N_{\mathrm{res}}(\varphi,S).
$$

問題是一般演算法不必遵守研究者指定的 $S$。

所以第三輪改為：

> 不替演算法指定路線；直接觀察它實際採取的路線。

令 $A$ 是任意確定性精確演算法。對長度為 $n$ 的輸入 $x$，其運行軌跡寫成：

$$
\tau_A(x)
=
(C_0(x),C_1(x),\ldots,C_{T_A(x)}(x)).
$$

$C_t(x)$ 是時間 $t$ 的完整機器配置，例如：

- 有限控制狀態；
- 工作記憶；
- 工作帶內容；
- 各讀寫頭位置；
- 已建立的中間資料結構；
- 目前程序位置。

唯讀輸入本身暫不視為工作配置的一部分，因為這正是後面攻防的關鍵。

---

# 二、不等號隊第一招：配置合併必須付代價

對固定時間 $t$，定義配置映射：

$$
\kappa_t:x\mapsto C_t(x).
$$

若不同輸入 $x,y$ 滿足：

$$
C_t(x)=C_t(y),
$$

我們說它們在時間 $t$ 被「配置合併」。

不等號隊直覺如下：

若 $x,y$ 對後續正確判定而言仍有本質差異，但機器當下沒有保存差異，那麼差異沒有真的消失；它只能：

1. 仍存在於可再次讀取的輸入；
2. 被編碼在某個未計量的外部結構；
3. 未來重新計算；
4. 或演算法其實找到了不需要該差異的更高階摘要。

因此提出暫定守恆式：

$$
\text{未保存區分}
\Rightarrow
\text{未來重建義務}.
$$

這把第二輪的「複雜度轉移」改寫成時間方向上的版本。

---

# 三、等號隊第一記重拳：同配置不代表同未來

對一般圖靈機而言，即使：

$$
C_t(x)=C_t(y),
$$

如果未來仍可重新讀取輸入，那麼機器遇到 $x$ 和 $y$ 時仍能走出不同路徑。

因此：

$$
C_t(x)=C_t(y)
\not\Rightarrow
\text{future}_A(x)=\text{future}_A(y).
$$

這與有限自動機不同。有限自動機讀過的字元通常已離開可見範圍；一般圖靈機可以回頭。

所以第二輪 Myhill–Nerode 型思路不能直接搬到任意多帶圖靈機。

**本輪第一個失敗結果：**

> 「某時刻工作配置只有多項式位元，因此只能區分多項式個歷史」是錯的。多項式位元可以形成指數多個配置；而且即使配置相同，唯讀輸入仍可在未來重新提供區分資訊。

---

# 四、不等號隊升級：狀態不足，就計入重新讀取與重算

既然未保存資訊可以從輸入重新取得，就把它列入成本帳本。

對時間切割 $t$，令：

$$
S_t=|C_t|
$$

為工作狀態位數，並令：

$$
R_t
$$

為從 $t$ 到終止期間，為了重新獲得切割前未保存差異所需的輸入訪問、重算與中間結構重建成本。

不等號隊提出「狀態—重建權衡」候選：

$$
\boxed{
\text{State}(t)+\text{Reconstruct}(t)
\ge
\text{RequiredDependency}(t)
}
$$

更抽象地：

$$
\mathsf{SR}_A(x,t)
=
S_t+R_t.
$$

若可以找到 SAT 實例族，使任意精確演算法都存在某個 $t$ 滿足：

$$
\mathsf{SR}_A(x,t)
\notin\operatorname{poly}(n),
$$

則可能導向一般下界。

這與經典 time–space tradeoff 的精神相近：空間不足時，計算往往需要用更多時間重算；反之亦然。但目前只是研究方向，尚未得到適用 SAT 與一般多項式時間模型的定理。

---

# 五、通信複雜度版本：把時間切割真的切開

為了避免「未來重新讀取過去輸入」破壞切割，可以人工把輸入拆成兩部分：

$$
x=(a,b).
$$

Alice 持有 $a$，Bob 持有 $b$。若一個演算法的某段計算主要依賴 $a$，另一段依賴 $b$，則可嘗試把它模擬成通信協議。

若正確計算某函數 $f(a,b)$ 需要大量通信，便可得到某些計算模型的下界。

確定性通信複雜度中的矩形、協議樹與可分辨輸入對正好提供這種工具。

但等號隊馬上指出：

1. SAT 輸入沒有天然唯一的 Alice/Bob 切法；
2. 演算法可在整個運行期間交錯訪問 $a,b$；
3. 對某種通信分解很難，不代表一般中央化演算法也難；
4. 從通信下界提升成一般圖靈機超多項式時間下界，本身就是巨大跳躍。

**裁定：** 通信複雜度提供成熟的「切割下界語言」，但目前仍是一個投影模型。

---

# 六、分支程式版本：時間—空間權衡確實存在，但仍不足

分支程式可將計算表示為一個有向圖：

- 節點表示狀態；
- 邊表示根據輸入測試後的轉移；
- 寬度反映空間；
- 長度／大小反映時間或狀態總量。

已知研究能對某些函數與某些時間限制證明非平凡甚至指數級的分支程式大小下界，也能得到 time–space tradeoff。

這對不等號隊很重要，因為它證明「狀態不足就必須付出更多路徑／時間」不是純哲學直覺。

但等號隊仍有一張牌：

> 能對某些函數、某些長度、某些分支程式模型得到下界，不代表能對 SAT 的所有多項式時間算法得到超多項式下界。

因此分支程式結果是概念證據，不是終局。

---

# 七、把任意多項式時間計算展開成電路

這一輪還出現一個很關鍵的統一視角。

若語言 $L\in P$，可由多項式時間均勻布林電路族計算。反過來，適當均勻的多項式大小電路族也刻畫多項式時間計算。

因此任意假設中的 SAT 多項式時間算法，都可以被時間展開成一族多項式大小的均勻電路：

$$
A
\leadsto
\{C_n\}_{n\ge1}.
$$

於是「演算法軌跡切割」可以改寫成「計算 DAG 的因果切割」。

輸入在 DAG 左側，輸出在右側；所有對輸出的影響必須沿資料依賴邊傳遞。

不等號隊因此提出：

> 是否存在一種不依賴電路局部語法的因果依賴量，使 SAT 的任意多項式大小電路都必須違反？

等號隊回答：

> 如果你成功證明 SAT 沒有多項式大小一般電路，當然足以推出 $P\neq NP$；但這本身就是著名且極難的電路下界問題。你只是把「軌跡瓶頸」推到了真正的主戰場。

**裁定：** 這不是失敗，而是成功定位：一般軌跡切割若要完成任務，最終必須具有至少能產生一般電路下界的力量。

---

# 八、本輪最重要的反轉：資訊量不夠

不等號隊原本很自然地想說：SAT 有巨大搜索空間，因此答案依賴大量資訊。

但輸入長度只有 $n$，所以整個輸入的 Shannon 資訊上限也只是：

$$
O(n)
$$

位元量級。

輸出甚至只有：

$$
1
$$

位元。

因此不存在一條簡單的信息守恆式可以說：

$$
\text{指數候選}
\Rightarrow
\text{必須傳遞指數位元}.
$$

PARITY 已經是最簡單的反例之一：它依賴全部 $n$ 位元，但可以用一個位元的滾動狀態處理。

所以真正的困難不是：

$$
\boxed{\text{需要多少資訊？}}
$$

而更像：

$$
\boxed{\text{這些資訊必須經過何種結構轉換，才能得到正確答案？}}
$$

這是第三輪真正的新轉折。

---

# 九、不等號隊第三次升級：因果重建複雜度 CRC

定義一個暫定概念：

$$
\operatorname{CRC}(f;x,t),
$$

表示在時間切割 $t$ 後，給定：

1. 當下已保存狀態；
2. 仍允許存取的原始輸入；
3. 合法的未來計算操作；

要恢復足以精確計算 $f(x)$ 的全域依賴所需的最小「重建結構成本」。

注意這裡刻意不把 CRC 定義成單純位元量。

它可能涉及：

$$
\operatorname{CRC}
=
F(
\text{re-read},
\text{recompute},
\text{interaction},
\text{composition depth},
\text{representation growth}
).
$$

不等號隊希望最終得到某種：

$$
\forall A\text{ 精確計算 SAT},
\quad
\exists x,t,
\quad
\operatorname{CRC}_A(x,t)
\ge n^{\omega(1)}.
$$

---

# 十、等號隊抓到循環陷阱

如果 CRC 被定義成：

$$
\operatorname{CRC}(f;x,t)
=
\min\{\text{從切割狀態算出 }f(x)\text{ 的時間}\},
$$

那麼要證明 CRC 超多項式，就等同於重新證明原問題。

所以 CRC 只有在能由更基本、獨立可計算或可下界的數學對象刻畫時才有用。

例如候選來源可以是：

- 組合交互結構；
- 局部一致性與全域一致性的落差；
- 證明複雜度；
- 張量／矩陣分解秩；
- 圖寬與消去寬度；
- 通信矩陣的結構；
- 擴展複雜度；
- 其他尚未找到的跨表示量。

因此：

$$
\boxed{
\text{CRC 是研究目標名稱，不是目前已完成的不變量。}
}
$$

---

# 十一、雙方本輪正式攻防

## 11.1 不等號隊

不等號隊現在不再主張「指數候選 = 指數資訊」。

改為：

> SAT 的難點可能是局部資訊可以高度壓縮，但要維持對任意約束組合的精確全域一致性，某種結構重建成本無法同時在時間、空間、表示與深度上被壓成多項式。

候選形式：

$$
\mathfrak C_A
=
\left(
S,
T,
D,
R,
W,
P
\right),
$$

其中：

- $S$：狀態／空間；
- $T$：轉移時間；
- $D$：依賴深度；
- $R$：重建／重算；
- $W$：結構寬度；
- $P$：表示精度。

希望找到不可同時壓縮關係。

## 11.2 等號隊

等號隊回答：

1. 你尚未證明這些維度完備；
2. 一個新表示可能同時降低多個現有維度；
3. SAT 的輸入只有 $n$ 位元，資訊論本身沒有指數障礙；
4. 一般電路可以高度重用中間結果；
5. 只要存在一種新數學表示把全域一致性直接算出來，所有局部瓶頸模型都可能失效。

等號隊本輪最強句：

$$
\boxed{
\text{你要證明的不是「資訊不能壓縮」，而是「正確全域關係不能被低成本計算」。}
}
$$

而這句話已非常接近 $P/NP$ 的核心，因此必須避免循環。

---

# 十二、與原始動態速率系列的重新接合

原系列把「尋找—計算—驗證」分開，並強調問題可解性會隨知識與智慧體歷史改變；同一問題在記憶者、定義者與跨底空間角色激活後，實際成本可以大幅移動。

本輪將其中「記憶者」的效果精確化成一個重要提醒：

$$
\text{不保存}
\neq
\text{資訊消失},
$$

因為演算法可以未來重新讀取或重新計算。

因此，真正的動態成本應加入：

$$
T_{\mathrm{reconstruct}}.
$$

得到擴展版本：

$$
T_{\mathrm{total}}
=
T_{\mathrm{search}}
+
T_{\mathrm{formalize}}
+
T_{\mathrm{construct}}
+
T_{\mathrm{realize}}
+
T_{\mathrm{run}}
+
T_{\mathrm{reconstruct}}
+
T_{\mathrm{verify}}.
$$

這一項對傳統 $P/NP$ 不是新增複雜度類，而是分析演算法內部複雜度轉移的觀察變量。

---

# 十三、本輪淘汰或降級的路線

以下命題不得在後續單獨作為 $P\neq NP$ 證明：

1. 某時間點只有有限／多項式工作狀態，所以無法區分所有輸入；
2. 兩個輸入在某時刻配置相同，因此之後必然相同；
3. 候選空間指數大，所以必須傳遞指數資訊；
4. SAT 依賴全部輸入，所以至少需要指數記憶；
5. 某個通信切割很難，所以中央化算法也必然很難；
6. 某種 time–space tradeoff 存在，所以 SAT 一定超多項式；
7. 直接把「重建複雜度」定義成最佳剩餘運行時間，再用它證明下界。

---

# 十四、本輪保留下來的武器

## 14.1 軌跡觀察仍有價值

任何演算法都會產生計算歷史；歷史可以展開為分支程式、計算 DAG 或均勻電路。因此「算法軌跡」不是虛構對象。

## 14.2 時間—空間—重算三者確實存在權衡

經典分支程式與 time–space tradeoff 結果提供了受限但真實的範例，證明重新計算可以補償空間，而下界有時能捕捉這種權衡。

## 14.3 資訊量與計算結構必須分離

$$
\text{Information Amount}
\neq
\text{Computational Transformation Cost}.
$$

這是本輪最重要的方法論校正。

## 14.4 一般軌跡下界會碰到一般電路下界

若軌跡切割真的能對所有多項式時間算法形成超多項式障礙，它必須至少具有足以排除多項式大小均勻電路的力量。

這讓研究方向更誠實，也更集中。

---

# 十五、障礙審查

## 15.1 相對化

純黑箱式「算法每次只能得到某些輸入資訊」論證容易相對化，因此高風險。

## 15.2 自然證明

若新的「因果不變量」是對大量函數都成立、可有效辨識且能排除小一般電路，必須檢查自然證明障礙。

## 15.3 代數化

若 CRC 最後被轉成秩、矩陣、多項式或張量量，仍須專門檢查代數化障礙。

## 15.4 模型偷換

通信、分支程式、公式、解析證明等局部結果，必須持續標明模型，不得直接升格為一般圖靈機結論。

---

# 十六、本輪裁定

不等號隊成功把「固定變數切割」升級為「算法自身軌跡」，但很快撞上兩個問題：

$$
\text{輸入可重讀}
$$

與：

$$
\text{資訊量只有 }O(n).
$$

等號隊因此成功擊破「簡單資訊瓶頸證明」。

但不等號隊得到一個新的研究物件：

$$
\boxed{\operatorname{CRC}:\text{因果重建複雜度}}
$$

並且確認下一步不能再只數狀態或位元，而要研究：

$$
\boxed{
\text{局部壓縮之後，要恢復全域正確性究竟需要什麼不可避免的結構轉換？}
}
$$

本輪比分：

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

理由：等號隊擊破簡單資訊瓶頸；不等號隊則成功把研究從資訊量推進到計算結構成本。

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

---

# 十七、第四輪入口

## 局部—全域障礙：SAT 的全域一致性是否存在不可低成本重建的核心？

下一輪將不再問「切割能保存多少資訊」，而問：

$$
\boxed{
\text{大量局部約束如何被組合成一個全域存在性判定？}
}
$$

不等號隊將嘗試建立：

$$
\text{Local Consistency}
\not\Rightarrow
\text{Global Witness}
$$

所產生的重建成本。

等號隊則會主張：也許存在某個尚未知的代數／幾何／拓撲摘要，能直接把全域一致性壓成多項式求值。

這一輪預計研究：

- 局部一致性與全域可滿足性的差距；
- 約束交互圖與消去寬度；
- 證明複雜度中的局部—全域現象；
- 是否能建立不依賴特定表示的「全域耦合負載」。

---

# 十八、資料歷史依賴

本輪繼承以下原系列觀點：

1. 《動態速率理論 2.9》：尋找、執行與驗證需解耦；知識形成後可把搜索轉成調用。
2. 《動態速率理論與 P vs. NP 問題的結構連續模型 2.0》：可解性隨智慧體與時間演化，但這不取代傳統靜態類別。
3. 《計算者之七相》：記憶者、定義者與底空間改變會移動實際成本；記憶／預計算不能無條件當作免費資源。
4. `00`：認知成果需經形式化、數學構造、基底實現與狀態轉移，才成為可重複演算法。
5. `01`：共同競技場是存在量詞壓縮器。
6. `02`：固定切割殘餘可分辨性是局部下界，但可被一般算法逃逸。

---

# 十九、外部理論參照

1. Anup Rao and Amir Yehudayoff, *Communication Complexity and Applications*, Cambridge University Press, 2020.
   - 確定性通信協議、矩形與通信下界提供真正的切割式語言。
2. Paul Beame, T. S. Jayram, Michael Saks, “Time–Space Tradeoffs for Branching Programs,” *Journal of Computer and System Sciences*, 2001.
   - 展示一般分支程式中非平凡 time–space tradeoff 與特定長度下的指數大小下界。
3. Andrew C.-C. Yao, “Near-Optimal Time-Space Tradeoff for Element Distinctness,” *SIAM Journal on Computing*, 1994.
   - 提供 time–space tradeoff 的經典實例。
4. Walter L. Ruzzo, “On Uniform Circuit Complexity,” *Journal of Computer and System Sciences*, 1981.
   - 均勻電路與機器模型關係的背景參照。

---

## 第三輪一句話紀錄

> **我們原本想證明「資訊過不去」；結果發現資訊其實可以回頭拿。真正需要證明的可能是：即使資訊一直都在，將它重組成精確的全域答案仍然必須付出某種不可壓縮的結構成本。**