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

## 對角切片壓縮與稀疏性上推陷阱：Self-Reference 不會免費壓縮 Proof

**Diagonal-Slice Compression, Sparsity Upward Separation, and the Failure of Free Self-Reference Compression**

- **主導研究者：** Neo.K
- **協作整理：** Aletheia
- **日期：** 2026-08-01
- **版本：** v1.0
- **前置：** `17_第十七輪_統一計算證書壓縮與普遍化跳躍.md`
- **研究狀態：** 雙假設預演；非 P/NP 正式證明

---

## 摘要

第十七輪把 universal certificate compression 拆成三層：fixed-machine、universal-indexed、diagonal-slice。Universal indexed 版本太強，因為 Universal Clocked Polynomial Evaluation（UCPE）會跳到 EXPTIME-complete；真正還可能留下縫隙的是 diagonal slice：只針對第 $i$ 台 clocked polynomial machine $C_i$ 與它被指定的 diagonal input $x_i$，尋找固定次數的短 rejection certificate。

本輪真正把這條路走到底後，發現一個新的「反向加難」現象。

若我們為了讓 diagonalization 乾淨，對每台 $C_i$ 只配置少量甚至單一 designated input，並將這些輸入安排在稀疏長度上，那麼 diagonal language

$$
D
=
\{x_i:C_i(x_i)=0\}
$$

天然會成為 sparse／tally-like language。若此時又能藉由 Uniform Diagonal Rejection Certificate（UDRC）證明：

$$
D\in NP,
$$

而 diagonal construction 同時保證：

$$
D\notin P,
$$

那麼我們得到的不是普通的 $NP\setminus P$ witness，而是：

$$
\boxed{
\text{sparse }D\in NP\setminus P.
}
$$

這看似更簡單，實際上卻更強。Hartmanis–Immerman–Sewelson 的 upward-separation 結果表明：存在 sparse set in $NP-P$，當且僅當其論文中稱為 EXPTIME 與 NEXPTIME 的單指數時間類不相等。該論文明確定義：

$$
EXPTIME=\bigcup_{c>0}TIME(2^{cn}),
$$

$$
NEXPTIME=\bigcup_{c>0}NTIME(2^{cn}),
$$

這在現代常見記號下更接近 $E$ 與 $NE$。因此，若 diagonal slice 真被我們做成 sparse $NP\setminus P$，就不只是得到 $P\neq NP$，還會同時得到更高階的 deterministic/nondeterministic exponential-time separation。

本輪將此命名為：

$$
\boxed{
\mathrm{SUST}
=
\text{Sparsity Upward-Separation Trap}
}
$$

——**把 diagonalization 做得太稀疏，並沒有把問題變簡單，反而可能把需要證明的東西升級。**

這也直接回答第十七輪留下的 self-reference 問題。Kleene recursion theorem／self-reference techniques 可以讓程式取得或作用於自己的描述，從而製造 fixed point；但 fixed-point existence 並不自動提供：

$$
\text{short proof},
\qquad
\text{short computation},
\qquad
\text{fixed-degree certificate}.
$$

因此：

$$
\boxed{
\text{self-reference is an addressing mechanism, not a compression theorem.}
}
$$

本輪把錯誤直覺命名為 **Self-Reference Compression Fallacy（SRCF）**。

接著又出現第二個夾擊。如果為了避開 sparse-set 上推障礙，把 diagonal set「做密」：每台機器不只配置一個點，而配置大區塊、或讓 machine index 成為一般輸入的一部分，那麼我們又逐漸回到第十七輪的 Universalization Complexity Jump：machine index、clock exponent、input 全部可變後，統一 evaluation 會重新攜帶無界 exponent，並向 EXPTIME 類 universal bounded-computation 問題靠近。

因此得到本輪最重要的新結構：

$$
\boxed{
\mathrm{DUS}
=
\text{Density--Uniformity Squeeze}
}
$$

其兩端是：

$$
\text{非常稀疏}
\Longrightarrow
\text{upward-separation barrier},
$$

$$
\text{足夠稠密／universal}
\Longrightarrow
\text{uniform-exponent / universalization barrier}.
$$

所以第十九輪將不再期待「一點一點對角化」直接掉進 NP，而改玩 **Block Diagonalization / Delayed Diagonalization**：能不能給每台 polynomial machine 一個可控輸入區塊，用延遲、分段與密度管理同時避開 sparse barrier 與 universal exponent barrier？這正好會與 Ladner 型 delayed diagonalization、density control 與 padding 技術交會。

---

# 一、第十七輪留下的最窄縫隙

第十七輪已排除過強願望：

$$
\forall M,x,k,
$$

都存在固定 $n^K$ 大小的 clocked-computation certificate。

那會讓 UCPE 進入 NP，從而經由 EXPTIME-completeness 產生極強後果。

因此只留下：

$$
\boxed{
(C_i,x_i)
}
$$

這條特殊 diagonal slice。

令：

$$
C_1,C_2,C_3,\ldots
$$

為所有 clocked polynomial-time deterministic machines 的有效列舉。

對每個 $i$ 指派一個 designated input：

$$
x_i.
$$

定義：

$$
\boxed{
D(x_i)=1-C_i(x_i).
}
$$

只要 indexing／duplicate handling 做得正確，就能確保：

$$
\forall i,
\qquad
D\neq L(C_i),
$$

故：

$$
D\notin P.
$$

問題只剩：

$$
\boxed{
D\stackrel{?}{\in}NP.
}
$$

---

# 二、UDRC：我們真正需要的是拒絕證書

由定義：

$$
x_i\in D
\iff
C_i(x_i)=0.
$$

所以 NP witness 必須證明：

$$
\boxed{
\text{deterministic }C_i\text{ 在 }x_i\text{ 上拒絕。}
}
$$

第十七輪將此命名為：

$$
\mathrm{UDRC}
=
\text{Uniform Diagonal Rejection Certificate}.
$$

理想版本要求存在固定 verifier $V$ 與固定常數 $K$：

$$
x_i\in D
\iff
\exists \pi,
\quad
|\pi|\le |x_i|^K,
$$

且：

$$
V(x_i,\pi)=1
$$

可在：

$$
|x_i|^K
$$

或其他固定 polynomial bound 內完成。

如果這存在，就有：

$$
D\in NP.
$$

配合 diagonalization：

$$
D\notin P,
$$

即得：

$$
P\neq NP.
$$

所以 UDRC 看起來像一條極窄但合法的攻擊線。

---

# 三、第一個新發現：Diagonal Slice 很容易天然變 sparse

最乾淨的 diagonal construction 通常會刻意避免 designated inputs 互相干擾。

例如選：

$$
|x_1|<|x_2|<|x_3|<\cdots
$$

甚至讓：

$$
|x_{i+1}|
$$

遠大於先前所有長度。

若每個 $i$ 只對應一個 $x_i$，那在長度 $n$ 以前，$D$ 的 YES candidates 數量至多等於已被指派的 diagonal indices 數量。

若安排使：

$$
|D\cap\{0,1\}^{\le n}|\le n^c
$$

對某固定 $c$ 成立，則：

$$
\boxed{D\text{ 是 sparse language}.}
$$

更激進地，若只使用：

$$
x_i=1^{m_i},
$$

甚至得到 tally-like diagonal set。

直覺上這似乎很好：

> instance 少，應該比較容易證明 membership 吧？

但複雜度理論在這裡給了一個很反直覺的答案。

---

# 四、Hartmanis–Immerman–Sewelson：Sparse NP-P 會向上分離

Hartmanis、Immerman、Sewelson 研究 sparse sets in $NP-P$，得到 upward-separation 結果。

其核心定理寫成：

$$
\boxed{
\exists\text{ sparse }S\in NP-P
\iff
EXPTIME\neq NEXPTIME
}
$$

但這裡必須非常小心記號。

該論文明確定義：

$$
EXPTIME
=
\bigcup_{c>0}TIME(2^{cn}),
$$

$$
NEXPTIME
=
\bigcup_{c>0}NTIME(2^{cn}).
$$

這與今天常把：

$$
E=DTIME(2^{O(n)}),
$$

$$
NE=NTIME(2^{O(n)})
$$

使用為單指數類的記號相近；現代常見的 EXP/NEXP 通常容許 $2^{n^{O(1)}}$。

所以為避免符號污染，本系列暫記該論文中的單指數 separation 為：

$$
\boxed{
E_{\mathrm{linexp}}
\neq
NE_{\mathrm{linexp}}.
}
$$

重點不是名稱，而是結構：

$$
\boxed{
\text{sparse }NP\setminus P
\Longleftrightarrow
\text{更高階 deterministic/nondeterministic time separation}.
}
$$

原作者甚至直接指出：

> 如果我們用一個 sparse set 分離 P 與 NP，那同時也分離了更高的 exponential classes；這可能比只證明 $P\neq NP$ 更難。

這和我們現在的 diagonal slice 幾乎正面撞上。

---

# 五、Sparsity Upward-Separation Trap（SUST）

因此本輪定義：

$$
\boxed{
\mathrm{SUST}
=
\text{Sparsity Upward-Separation Trap}.
}
$$

若 diagonal construction 滿足：

1. 每台 $C_i$ 僅配置 $O(1)$ 個 designated inputs；
2. designated lengths 稀疏增長；
3. 因而 $D$ 為 sparse；
4. UDRC 又證明 $D\in NP$；
5. diagonalization 證明 $D\notin P$；

那麼我們實際得到：

$$
\boxed{
\text{sparse }D\in NP-P.
}
$$

由 upward separation：

$$
\boxed{
E_{\mathrm{linexp}}\neq NE_{\mathrm{linexp}}.
}
$$

而這當然又會推出：

$$
P\neq NP.
$$

所以：

$$
\boxed{
\text{Diagonal slice 太薄，不是降低證明門檻，而是可能提高門檻。}
}
$$

這是第十八輪最重要的新結果。

---

# 六、第二個警報：Mahaney Sparse Completeness Trap

另一個相關經典結果是 Mahaney theorem。

若存在 sparse language $S$，它在 polynomial-time many-one reductions 下 NP-complete，則：

$$
\boxed{P=NP.}
$$

因此如果我們造了一個 sparse diagonal set $D$，不能再天真地要求：

$$
D\text{ 同時是 NP-complete}
$$

作為不等號隊的標準 hard witness。

因為：

$$
\text{sparse}+\text{NP-complete}
$$

反而會把遊戲推向：

$$
P=NP.
$$

但這裡要保持精確：

要證明 $P\neq NP$，我們只需要：

$$
D\in NP-P,
$$

**不需要** $D$ 是 NP-hard 或 NP-complete。

所以 Mahaney theorem 並沒有殺死 diagonal-slice route；它只是告訴我們：

$$
\boxed{
\text{稀疏 separation witness 與標準 NP-complete hard core 是不同戰略。}
}
$$

---

# 七、Self-reference 真正能做什麼？

第十七輪留下另一個誘惑：

> 如果 $x_i$、$C_i$、proof 都透過 self-reference 綁在一起，是否可以不用完整模擬，就靠「它在說自己」壓縮拒絕證明？

Kleene recursion theorem 類結果確實提供：

$$
\boxed{
\text{program 可以有效取得自我描述／形成 computable fixed point}.
}
$$

也就是給定適當 computable transformation：

$$
F,
$$

可構造某個 program index $e$，使其行為與：

$$
F(e)
$$

形成 fixed-point 關係。

但這個 theorem 的結論是：

$$
\boxed{
\text{extensional fixed-point existence}.
}
$$

它沒有說：

$$
T_e(n)=O(n^K),
$$

沒有說：

$$
\text{拒絕有 }n^K\text{ 短 proof},
$$

也沒有說：

$$
\text{fixed point 可被 NP verifier 快速驗證}.
$$

所以：

$$
\boxed{
\text{self-reference 提供「指到自己」的能力，}
}
$$

並不自動提供：

$$
\boxed{
\text{「快速知道自己最後做了什麼」的能力。}
}
$$

---

# 八、Self-Reference Compression Fallacy（SRCF）

本輪因此正式建立防假證明規則：

$$
\boxed{
\mathrm{SRCF}
=
\text{Self-Reference Compression Fallacy}.
}
$$

錯誤推理：

$$
\text{statement / machine can refer to itself}
$$

$$
\Downarrow
$$

$$
\text{its semantic truth therefore has a short certificate}.
$$

這不成立。

Self-reference 與 proof compression 是兩個不同維度：

### Self-reference cost

$$
C_{\mathrm{ref}}
$$

控制：

- 如何取得自身編碼；
- 如何建立 fixed point；
- 如何指定 diagonal target。

### Semantic certification cost

$$
C_{\mathrm{cert}}
$$

控制：

- 如何證明 machine 接受／拒絕；
- proof 多長；
- verifier 多快；
- soundness model 為何。

一般沒有：

$$
C_{\mathrm{ref}}\ll n^K
\Rightarrow
C_{\mathrm{cert}}\ll n^K.
$$

---

# 九、等號隊反擊：那我不要把 diagonal set 做 sparse

等號隊發現 SUST 後立刻說：

> 好，那我不做「一台機器一個點」。我給每台 $C_i$ 一整個 block！

例如：

$$
B_i
=\{\langle i,y\rangle:|y|\in I_i\}.
$$

然後定義某種 block diagonalization：

$$
D_B(\langle i,y\rangle)
$$

在 block $B_i$ 中對 $C_i$ 做反向／挑戰。

這可以提高 density。

若每個長度有大量 designated strings，可能不再 sparse。

看似可以繞過 Hartmanis–Immerman–Sewelson upward-separation trap。

但是……

---

# 十、Density 一增加，Uniformity 又回來了

一旦一般 input 形如：

$$
\langle i,y\rangle,
$$

verifier 必須處理：

$$
i
$$

所指定的任意 clocked machine：

$$
C_i,
$$

而 $C_i$ 的 polynomial exponent：

$$
k_i
$$

可能無界。

如果 block language 的 membership 定義直接依賴：

$$
C_i(\langle i,y\rangle),
$$

那麼我們重新遇到：

$$
\boxed{
\text{Uniform Exponent Barrier}.
}
$$

當：

$$
i,k_i,y
$$

全部變成統一輸入域的一部分時，問題開始從：

$$
\text{fixed slice}
$$

往：

$$
\text{universal evaluation}
$$

移動。

這就是第十七輪的：

$$
\mathrm{UCJ}
=
\text{Universalization Complexity Jump}.
$$

所以：

$$
\boxed{
\text{稀疏化能降低 uniformity，但觸發 upward separation；}
}
$$

$$
\boxed{
\text{稠密化能避開 sparsity，但重新提高 uniformity。}
}
$$

---

# 十一、Density--Uniformity Squeeze（DUS）

本輪將這個雙向夾擊正式命名：

$$
\boxed{
\mathrm{DUS}
=
\text{Density--Uniformity Squeeze}.
}
$$

粗略表示為：

$$
\begin{array}{ccc}
\text{Sparse diagonal slice}
&\longrightarrow&
\text{SUST / higher-class separation}
\\
&&
\\
\text{Dense indexed diagonal family}
&\longrightarrow&
\text{UEB / UCJ / universal evaluation}
\end{array}
$$

這不是正式的 complexity dichotomy theorem。

目前只能把它視為：

$$
\boxed{
\text{研究設計空間中的雙端壓力圖。}
}
$$

若未來能把「所有 diagonal construction」形式化成某個可分析 family，才可能升格成真正定理。

---

# 十二、為什麼 sparse set 的結果特別貼近我們？

Hartmanis–Immerman–Sewelson 的原始動機本身就很接近本系列這一輪的問題。

他們研究：

> 如果 NP-P 裡真的有難的 individual instances，能不能把它們集中成低密度集合？

結果顯示，這種「低密度但仍然困難」的存在，本身與更高 complexity classes 的 separation 有深層耦合。

我們現在的 diagonal slice 恰好也在做：

$$
\boxed{
\text{每台 polynomial machine 挑一個個別反例。}
}
$$

這天然就是：

$$
\text{individual hard instances}
$$

的集合化。

所以 sparse-set theory 不是旁支，而是非常準確地打中了這條 diagonal route 的結構。

---

# 十三、對第十七輪 DSCC 的重新評估

第十七輪提出：

$$
\mathrm{DSCC}
=
\text{Diagonal-Slice Certificate Compression}.
$$

本輪把它拆成兩種。

## 13.1 Sparse-DSCC

只壓：

$$
(C_i,x_i)
$$

少量 designated diagonal points。

若成功且 $D\notin P$：

$$
\boxed{
\text{sparse }NP-P
}
$$

觸發 SUST。

## 13.2 Dense-DSCC

擴張為大量：

$$
(C_i,x_{i,j})
$$

或 indexed blocks。

可避 sparsity，但 machine index／exponent 更充分進入 uniform input，逐漸觸發：

$$
\boxed{
\mathrm{UEB}+\mathrm{UCJ}.
}
$$

所以 DSCC 並沒有消失，而是被分裂成兩種不同的高成本路徑。

---

# 十四、Proof Complexity 在這裡能做到什麼？

假設對每個 diagonal pair 建立一個命題公式：

$$
\Theta_i
=
\text{「}C_i(x_i)\text{ 拒絕」}.
$$

如果存在 proof system $\mathcal P$，使每個真的 $\Theta_i$ 都有：

$$
|\pi_i|\le |x_i|^K,
$$

而 proof checking 為 polynomial，便可能形成 UDRC。

但要非常小心：

Cook–Reckhow 的 polynomially bounded proof-system theorem 說的是：

$$
\boxed{
\text{所有 propositional tautologies 都有 polynomial-size proofs}
\iff
NP=coNP.
}
$$

我們現在只要求一個非常特殊 family：

$$
\{\Theta_i\}.
$$

所以：

$$
\boxed{
\text{Diagonal family 有短 proof}
\not\Rightarrow
NP=coNP.
}
$$

反過來：

$$
\boxed{
\text{某個 proof system 對 }\Theta_i\text{ 有長下界}
\not\Rightarrow
\text{所有 proof systems 都長}.
}
$$

因此 proof complexity 在這裡仍然是一個 candidate mechanism，而不是自動 separation。

---

# 十五、第三個新概念：Family-Selective Proof Compression

本輪把「只壓特殊 diagonal family」命名為：

$$
\boxed{
\mathrm{FSPC}
=
\text{Family-Selective Proof Compression}.
}
$$

它和 universal proof compression 不同。

Universal：

$$
\forall\varphi\in TAUT,
\quad
\exists\pi,
|\pi|\le poly(|\varphi|).
$$

Family-selective：

$$
\forall i,
\quad
\Theta_i\in TAUT
\Rightarrow
\exists\pi_i,
|\pi_i|\le |x_i|^K.
$$

這個要求弱很多。

但若 family 本身被 diagonal construction 連接到：

$$
D\in NP-P,
$$

那麼弱的 proof compression 也可能有非常強的 complexity consequence。

這是本輪另一個反直覺點：

$$
\boxed{
\text{proof system 的覆蓋面窄，不代表 complexity consequence 一定弱。}
}
$$

取決於那個 family 如何被選出來。

---

# 十六、對角化與稀疏性的量詞重寫

一般 $P\neq NP$ 要：

$$
\exists L\in NP
\quad
\forall C_i\in P,
\quad
L\neq L(C_i).
$$

Diagonal slice 做的是：

$$
\forall i,
\quad
\exists x_i,
\quad
L(x_i)\neq C_i(x_i).
$$

若每個 $i$ 只消耗一個 $x_i$，語義上的全稱攻擊：

$$
\forall i
$$

被壓縮成資料密度上的：

$$
O(1)\text{ witness point per machine}.
$$

這正是為什麼 sparse 結構自然出現。

換句話說：

$$
\boxed{
\text{對角化用極少量 instance 見證全稱分離，}
}
$$

而 upward-separation theory 告訴我們：

$$
\boxed{
\text{這種「低密度全稱見證」本身非常強。}
}
$$

---

# 十七、這輪對最初「數學函數壓縮搜索」命題的回應

一路回到最初影片。

我們一開始問：

> 很多候選／很多步驟，是否可能透過一個精巧數學函數直接壓縮？

到了第十八輪，答案變得更成熟：

### 可以發生的壓縮

- XOR 可以線性化；
- matching 可以 blossom contraction；
- proof 可以比 trace 短；
- self-reference 可以把描述與自身連接；
- sparse encoding 可以集中 individual instances。

### 但每一種壓縮都必須問

$$
\boxed{
\text{它壓的是哪一個維度？}
}
$$

例如 self-reference 壓的是：

$$
\text{description addressing},
$$

不等於壓：

$$
\text{semantic verification complexity}.
$$

sparsity 壓的是：

$$
\text{instance density},
$$

但可能把 structural consequence 推到更高 complexity classes。

這再次支持整個系列的核心方法：

$$
\boxed{
\text{不要只問「成本有沒有變少」，而要問「哪一種成本跑去哪裡」。}
}
$$

---

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

以下推論本輪正式列入黑名單。

## 錯誤 1

$$
\text{Diagonal set 很 sparse}
\Rightarrow
\text{比較容易證明在 NP}.
$$

不成立。Sparse $NP-P$ 本身有更高階 separation consequence。

---

## 錯誤 2

$$
\text{self-reference}
\Rightarrow
\text{short rejection certificate}.
$$

不成立。Fixed point 不是 proof-compression theorem。

---

## 錯誤 3

$$
\text{把 diagonal set 做 dense}
\Rightarrow
\text{自動避開 exponent barrier}.
$$

不成立。Density 增加通常需要更 uniform 的 indexed evaluation。

---

## 錯誤 4

$$
\text{sparse }D\in NP-P
\Rightarrow
D\text{ 可以順便設成 NP-complete}.
$$

不能隨便這樣做；Mahaney theorem 說 sparse NP-complete set 會導致 $P=NP$。

---

## 錯誤 5

$$
\text{某 proof system 對 diagonal formulas 很難}
\Rightarrow
D\notin NP.
$$

仍然只是一個 proof-system lower bound。

---

# 十九、本輪正式成果

## 19.1 Sparsity Upward-Separation Trap（SUST）

若 diagonal slice 被安排成 sparse，並成功得到：

$$
D\in NP-P,
$$

則會觸發更高階 deterministic/nondeterministic time separation。

所以 sparse diagonal separation 並不是「較弱版本的 P/NP」。

---

## 19.2 Self-Reference Compression Fallacy（SRCF）

Kleene-style self-reference：

$$
\text{fixed-point / self-description}
$$

不自動導出：

$$
\text{fixed-degree proof compression}.
$$

---

## 19.3 Density--Uniformity Squeeze（DUS）

目前觀察到：

$$
\text{sparse}
\rightarrow
\text{upward-separation pressure},
$$

$$
\text{dense/universal}
\rightarrow
\text{uniformization pressure}.
$$

這目前是研究設計圖，而非已證明的一般 dichotomy。

---

## 19.4 Family-Selective Proof Compression（FSPC）

我們真正需要的不是所有 tautologies 的短 proofs，而只是特殊 diagonal rejection family 的短 proofs。

這避免直接等同 $NP=coNP$，但若該 family 對應 sparse $NP-P$ witness，其 consequence 仍可能非常強。

---

# 二十、雙方戰果

## $P\neq NP$ 隊

本輪拿到非常漂亮的外部支援：

$$
\boxed{
\text{Sparse diagonal witness 如果成功，甚至會向上分離 exponential classes。}
}
$$

因此「one machine, one counterexample」並不是簡單版 separation。

### 新武器

$$
\mathrm{SUST}
$$

$$
\mathrm{DUS}
$$

---

## $P=NP$ 隊

成功阻止不等號隊把 self-reference 當免費 proof compressor，並逼迫對方承認：

$$
\boxed{
\text{如果要避 sparse barrier，就得增加 density / block structure，}
}
$$

這又重新打開 representation、bridge 與 compression 空間。

也就是：sparse diagonal route 被卡住，不代表所有非稀疏 construction 被卡住。

### 新武器

$$
\text{Block / Dense Escape}
$$

---

# 二十一、本輪比分

$$
P=NP:17
$$

$$
P\neq NP:17
$$

……

現在已經很難用「巧合」解釋了。

可能這個研究區真的偷偷實作了：

$$
\boxed{
\Delta \text{score}=0
}
$$

的 conservation constraint。（歪臉笑）

比分仍然只是一個研究遊戲介面，不具有任何證明意義。

---

# 二十二、第十九輪入口：Block / Delayed Diagonalization

下一輪不再採用：

$$
\text{one machine}\leftrightarrow\text{one diagonal point}.
$$

而考慮：

$$
\boxed{
\text{one machine}\leftrightarrow\text{one controlled block / stage}.
}
$$

研究：

$$
B_1,B_2,B_3,\ldots
$$

每個 block 對應一台或一組 polynomial machines。

核心問題：

1. 能否用 block density 避開 sparse-set upward separation？
2. 能否用 delayed diagonalization 避免同一時刻支付無界 $k_i$？
3. 能否讓 membership verifier 只需查看「當前 stage」的固定次數資訊？
4. 為什麼 Ladner delayed diagonalization 能在假設 $P\neq NP$ 下造 NP-intermediate language，卻不能反過來無條件證明 $P\neq NP$？
5. Density schedule：

$$
d(n)
$$

是否能成為 exponent schedule：

$$
k_i
$$

與 NP witness bound：

$$
n^K
$$

之間的緩衝層？
6. Hartmanis–Immerman–Sewelson 已指出：Ladner 型 delayed diagonalization 若想產生 sparse $NP-P$，仍會要求更高 exponential separation。那麼非 sparse block construction 是否存在另一種可利用的窗口？

下一輪暫定名：

$$
\boxed{
\text{Block Diagonalization and Delayed-Density Game}
}
$$

---

# 二十三、外部理論參照

1. J. Hartmanis, N. Immerman, V. Sewelson, **Sparse Sets in NP-P: EXPTIME versus NEXPTIME**, *Information and Control* 65 (1985), 158–181.
   - 核心：存在 sparse set in $NP-P$ iff 文中定義的 EXPTIME $\neq$ NEXPTIME；文中亦指出若由 sparse set 分離 P/NP，將同時得到更高階 separation。
   - 注意：文中 EXPTIME 定義為 $\bigcup_{c>0}TIME(2^{cn})$，與現代常用 EXP 記號不同。

2. Stephen R. Mahaney, **Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis**, *Journal of Computer and System Sciences* 25 (1982), 130–143.
   - 核心：若存在 sparse NP-complete set（polynomial-time many-one），則 $P=NP$。

3. Stephen A. Cook, Robert A. Reckhow, propositional proof systems.
   - polynomially bounded propositional proof system iff $NP=coNP$；本輪只使用它來區分 universal proof compression 與 family-selective proof compression。

4. Kleene recursion theorem／computability fixed-point literature.
   - self-reference 可以建立 computable fixed points，但 theorem 本身不給 runtime／proof-length compression。

5. Ladner delayed diagonalization.
   - 作為第十九輪 block/stage diagonalization 的主要比較對象。

---

## 本輪裁定

第十七輪留下的 diagonal-slice certificate compression 並沒有形成免費漏洞。

若把 slice 做得極稀疏：

$$
\boxed{
\text{UDRC}+\text{diagonalization}
\Rightarrow
\text{sparse }NP-P,
}
$$

而 sparse $NP-P$ 本身連接到更高階 exponential-time separation。

若把 slice 做得更密以逃離 sparsity：

$$
\boxed{
\text{machine index / exponent 的 uniformity 又重新進場。}
}
$$

而 self-reference：

$$
\boxed{
\text{可以幫我們「指到自己」，不能免費幫我們「證明自己」。}
}
$$

所以第十八輪真正得到的不是答案，而是一個比前一輪更尖銳的設計約束：

$$
\boxed{
\text{P/NP diagonal route 似乎被夾在 density 與 uniformity 之間。}
}
$$

第十九輪將正式嘗試用 block／delayed diagonalization 從這個夾縫穿出去。