计算宇宙的离散复杂性几何

配置图上的度量、体积增长与局部曲率

摘要

在前一篇工作中，我们将“计算宇宙“公理化为带有配置空间、一步更新关系、单步代价与信息质量函数的四元组 $U_{\mathrm{comp}}=(X,\mathsf{T},\mathsf{C},\mathsf{I})$。本文在此基础上发展一套“离散复杂性几何“（discrete complexity geometry），其目标是用纯离散的图论与度量结构，刻画计算过程的时间复杂度、问题的“几何难度“以及有限资源下的可达域与视界结构。

首先，我们将每个计算宇宙关联到一个加权有向图 $G_{\mathrm{comp}}=(X,E,w)$，其中边集 $E=\mathsf{T}$、边权 $w(x,y)=\mathsf{C}(x,y)$。在适当有限性与广义可逆性假设下，这一结构诱导出一个广义度量 $d:X\times X\to [0,\infty ]$，其最短路径值等价于离散时间复杂度的物理化版本。我们定义复杂性球 $B_T(x_0)=\{x:d(x_0,x)\le T\}$ 与复杂性体积增长函数 $V_{x_0}(T)=|B_T(x_0)|$，并以此引入一个“复杂性维数“ ${\dim }_{\mathrm{comp}}(x_0)$，衡量在给定起点附近复杂度的增长阶。

其次，我们在加权图上引入一种以转移概率与一阶 Wasserstein 距离为基础的离散 Ricci 曲率 $\kappa (x,y)$，定性刻画局部区域内复杂路径的“发散“或“收缩“趋势。我们证明：在某些自然假设下，负曲率区间对应复杂性球的指数型体积增长，而非负曲率区域对应多项式或次指数增长，从而建立“曲率–问题难度“的定性联系。

再次，我们将可达域族 $\{B_T(x_0){\}}_{T>0}$ 视为一类随资源预算 $T$ 演化的“复杂性视界“，并通过简单的同调与连通性指标，刻画复杂性相变：当 $T$ 穿越某些临界值时，可达域的连通分支数、基本群或一阶同调群发生突变，对应算法在复杂性几何上的“突然开通新路线“。

最后，在假设计算宇宙来自某个统一时间刻度 $\kappa (\omega )$ 所控制的物理实现下，我们讨论一族复杂性图在网格细化极限下如何收敛到一个 Riemann 流形 $(\mathcal{M},G)$，使得离散复杂性距离 $d$ 在大尺度上逼近由 $G$ 诱导的测地距离，并给出若干低维情形的严格收敛定理。

本文作为“计算宇宙理论“系列的第二篇，提供了从完全离散的计算结构到几何化复杂性的第一层桥梁，为后续统一信息几何、时间刻度与物理宇宙范畴等价的工作奠定基础。

关键词

计算宇宙；复杂性几何；加权图；Ricci 曲率；体积增长；复杂性视界；统一时间刻度

1 引言

在计算理论与物理学的交汇处，将“宇宙视为计算“已成为一条重要思路。若我们接受上一篇工作中的设定：整个宇宙可以被抽象为一个带有限信息密度、局域更新与统一时间刻度的离散动力系统 $U_{\mathrm{comp}}=(X,\mathsf{T},\mathsf{C},\mathsf{I})$，那么自然的问题是：这一离散结构是否可以拥有类似 Riemann 几何的“曲率““体积增长”“视界“等几何概念，从而以几何方式理解计算复杂性与问题难度。

传统复杂性理论多以步数或门数作为复杂度标尺，而不关心不同计算路径之间的几何关系。另一方面，图几何与离散 Ricci 曲率的发展表明，在加权图上构建类似连续几何的结构是可行的。本文正是在“计算宇宙“的公理框架下，系统地把这两条线索合并为一个统一的“离散复杂性几何“理论。

本文的主要贡献可概括如下：

1. 给出从计算宇宙 $U_{\mathrm{comp}}$ 到复杂性图 $G_{\mathrm{comp}}$ 与复杂性距离 $d$ 的统一构造，证明其在自然条件下是一个广义度量，并定义复杂性球、复杂性体积与复杂性维数。
2. 在复杂性图上引入基于离散转移分布与 Wasserstein 距离的 Ricci 曲率 $\kappa (x,y)$，并证明其符号与复杂性体积增长类型之间的定性联系。
3. 以可达域族 $B_T(x_0)$ 为对象，引入复杂性视界与复杂性相变的概念，用简单的代数拓扑不变量描述可达域随资源预算 $T$ 变化的“拓扑跃迁“。
4. 在假设存在统一时间刻度的情况下，给出一族复杂性图在网格细化极限下收敛到流形 $(\mathcal{M},G)$ 的条件，证明在低维情形下，离散复杂性距离与连续测地距离一致。

全文结构如下：第 2 节回顾计算宇宙的公理，并构造复杂性图与距离。第 3 节研究体积增长与复杂性维数。第 4 节引入离散 Ricci 曲率并讨论其与复杂性增长的关系。第 5 节讨论复杂性视界与相变结构。第 6 节讨论流形极限与统一时间刻度的一致性。附录中给出主要命题与定理的详细证明。

2 从计算宇宙到复杂性图与度量

本节在上一篇的定义基础上，对复杂性图与复杂性距离作出更精细的构造与分析。

2.1 计算宇宙的基本回顾

回顾计算宇宙的定义。

定义 2.1（计算宇宙回顾）

一个计算宇宙对象是四元组 $U_{\mathrm{comp}}=(X,\mathsf{T},\mathsf{C},\mathsf{I})$，其中：

1. $X$ 为可数配置集；
2. $\mathsf{T}\subset X\times X$ 为一步更新关系；
3. $\mathsf{C}:X\times X\to [0,\infty ]$ 为单步代价，满足：若 $(x,y)\notin \mathsf{T}$，则 $\mathsf{C}(x,y)=\infty$，若 $(x,y)\in \mathsf{T}$，则 $\mathsf{C}(x,y)\in (0,\infty )$；
4. $\mathsf{I}:X\to \mathbb{R}$ 为信息质量函数。

并满足有限信息密度、局域更新、广义可逆性与代价加性等公理。

对任意有限路径 $\gamma =(x_0,\dots ,x_n)$ 满足 $(x_k,x_{k+1})\in \mathsf{T}$，定义路径代价

$$\mathsf{C}(\gamma )=\sum _{k=0}^{n-1}\mathsf{C}(x_k,x_{k+1})$$

并定义复杂性距离

$$d(x,y)=\underset{\gamma :x\to y}{\inf }\mathsf{C}(\gamma )$$

其中 $\gamma$ 遍历所有从 $x$ 到 $y$ 的有限路径。

上一篇已证明，在适当的可达性与对称性条件下，$d$ 是一个广义度量。本节以此为基础定义复杂性图。

2.2 复杂性图的定义

定义 2.2（复杂性图）

给定计算宇宙 $U_{\mathrm{comp}}=(X,\mathsf{T},\mathsf{C},\mathsf{I})$，其复杂性图是加权有向图 $G_{\mathrm{comp}}=(X,E,w)$，其中：

1. 顶点集为 $X$；
2. 有向边集为 $E=\mathsf{T}$；
3. 边权 $w:E\to (0,\infty ]$ 定义为 $w(x,y)=\mathsf{C}(x,y)$。

若需要无向图结构，可定义对称边集

$$E_{\mathrm{sym}}=\{\{x,y\}:(x,y)\in E\text{ 或 }(y,x)\in E\}$$

边权

$$w_{\mathrm{sym}}(\{x,y\})=\min \{\mathsf{C}(x,y),\mathsf{C}(y,x)\}$$

定义 2.3（复杂性距离的有限性区域）

定义可达子集

$$X_{\mathrm{fin}}=\{x\in X:d(x_0,x)<\infty \}$$

其中 $x_0\in X$ 为选定的参考配置。本文中，如不引起混淆，我们常在 $X_{\mathrm{fin}}$ 上限制讨论。

上一篇的结果立即给出以下命题。

命题 2.4（复杂性距离的度量性质）

在 $X_{\mathrm{fin}}$ 上，复杂性距离 $d$ 满足：

1. $d(x,x)=0$；
2. $d(x,y)\ge 0$，且 $d(x,y)=0$ 蕴含 $x=y$；
3. $d(x,z)\le d(x,y)+d(y,z)$。

若 $\mathsf{T}$ 在 $X_{\mathrm{fin}}$ 上可逆且代价在边反向时对称，则 $d(x,y)=d(y,x)$，从而 $(X_{\mathrm{fin}},d)$ 为度量空间。

证明参见附录 A.1。

2.3 复杂性球与体积函数

定义 2.5（复杂性球与体积）

对 $x_0\in X_{\mathrm{fin}}$、$T>0$，定义复杂性球

$$B_T(x_0)=\{x\in X_{\mathrm{fin}}:d(x_0,x)\le T\}$$

其体积（以点计数）为

$$V_{x_0}(T)=|B_T(x_0)|\in \mathbb{N}\cup \{\infty \}$$

命题 2.6（单调性与子加性）

1. 对任意 $T_1<T_2$，有 $B_{T_1}(x_0)\subseteq B_{T_2}(x_0)$，从而 $V_{x_0}(T_1)\le V_{x_0}(T_2)$；
2. 若存在常数 $C>0$ 使得对所有 $T_1,T_2>0$ 有 $$V_{x_0}(T_1+T_2)\le C{V}_{x_0}(T_1)V_{x_0}(T_2)$$ 则 $\log V_{x_0}(T)$ 为次可加函数。

证明见附录 A.2。第二条在许多局域图中自然成立，并为复杂性增长指数的定义提供基础。

3 体积增长与复杂性维数

复杂性球体积的增长速度是刻画“计算宇宙局部复杂性维数“的自然对象。本节给出基本定义与性质。

3.1 复杂性维数的定义

定义 3.1（上复杂性维数与下复杂性维数）

对给定起点 $x_0\in X_{\mathrm{fin}}$，定义上复杂性维数为

$${\overline{\dim }}_{\mathrm{comp}}(x_0)=\underset{T\to \infty }{\mathrm{limsup}}\frac{\log V_{x_0}(T)}{\log T}$$

下复杂性维数为

$${\underline{\dim }}_{\mathrm{comp}}(x_0)=\underset{T\to \infty }{\mathrm{liminf}}\frac{\log V_{x_0}(T)}{\log T}$$

若二者相等，则称其共同值为复杂性维数，记为 ${\dim }_{\mathrm{comp}}(x_0)$。

直观地，${\dim }_{\mathrm{comp}}(x_0)$ 描述了从 $x_0$ 出发，可达配置数随复杂性预算 $T$ 增长的多项式阶数。若 ${\dim }_{\mathrm{comp}}(x_0)=\infty$，则可达域体积至少以超多项式速度增长。

3.2 与图结构的关系

对无向局域图，体积增长阶与其“图维数“密切相关。在复杂性图中，我们可以得到一个类似的结果。

命题 3.2（有界度情形的多项式增长）

假设复杂性图的无向对称版 $(X_{\mathrm{fin}},E_{\mathrm{sym}})$ 度有界，即存在 $D>0$ 使对所有 $x\in X_{\mathrm{fin}}$ 有 $\mathrm{deg}(x)\le D$。若此外单步代价在某个区间内有界，即存在常数 $0<c_{\min }\le c_{\max }<\infty$ 使得对所有边 $\{x,y\}\in E_{\mathrm{sym}}$ 有

$$c_{\min }\le w_{\mathrm{sym}}(\{x,y\})\le c_{\max }$$

则存在常数 $C_1,C_2>0$ 与整数 $d_{\ast }\ge 0$，使得对足够大的 $T$ 有

$$C_1{T}^{d_{\ast }}\le V_{x_0}(T)\le C_2{T}^{d_{\ast }}$$

特别地，${\dim }_{\mathrm{comp}}(x_0)=d_{\ast }$。

证明见附录 A.3，思路是用边数与步数之间的线性关系，将复杂性球约简为步数球，并利用有界度图的体积增长估计。

命题 3.3（指数增长与超多项式复杂性）

若存在常数 $\lambda >1$ 与 $T_0>0$，使得对所有 $n\in \mathbb{N}$ 有

$$V_{x_0}(n{T}_0)\ge {\lambda }^n$$

则 ${\overline{\dim }}_{\mathrm{comp}}(x_0)=\infty$。

换言之，复杂性球体积指数增长则复杂性维数无限大。

证明见附录 A.4。

这些结果表明：复杂性维数为有限值时，复杂度随预算 $T$ 的增长具有某种“维数可控性“；而指数级增长意味着复杂性几何局部“爆炸“，对应高度难解的搜索空间。

4 离散 Ricci 曲率与问题难度

在度量空间中，Ricci 曲率的符号与体积增长及测地线偏离密切相关。本节在复杂性图上引入一种离散 Ricci 曲率，刻画局部区域内复杂路径的发散或收缩，并讨论其与复杂性体积增长之间的定性联系。

4.1 基于转移分布的离散 Ricci 曲率

我们采用以一阶 Wasserstein 距离为基础的粗 Ricci 曲率，适配有向加权图情形。

定义 4.1（局部一步转移分布）

在复杂性图 $G_{\mathrm{comp}}=(X,E,w)$ 上，定义从 $x$ 出发的局部一步转移分布为

$$m_x(y)=\frac{a(x,y)}{{\sum }_{z}a(x,z)}$$

其中

$$a(x,y)=\{\begin{array}{ll}\exp (-\lambda w(x,y)),& (x,y)\in E,\\ 0,& \text{否则},\end{array}$$

$\lambda >0$ 为固定的尺度参数。

这是一个对“低代价边“有偏好的随机游走核。

定义 4.2（复杂性图上的 Ricci 曲率）

对 $x\ne y$，定义从 $x$ 到 $y$ 的离散 Ricci 曲率为

$$\kappa (x,y)=1-\frac{W_1(m_x,m_y)}{d(x,y)}$$

其中 $W_1$ 为相对复杂性距离 $d$ 下的一阶 Wasserstein 距离。

当 $m_x$ 与 $m_y$ 的质量在 $d$ 下的平均位移小于 $d(x,y)$ 时，$\kappa (x,y)>0$；反之若平均位移大于 $d(x,y)$，则 $\kappa (x,y)<0$。

4.2 曲率与测地线发散

在经典度量空间中，Ricci 曲率下界控制测地线之间的“平均收缩“。在我们的复杂性图中，可以证明一个离散的类似结论。

定理 4.3（曲率下界与复杂性距离收缩）

设存在常数 $K\in \mathbb{R}$，使得对所有相邻顶点 $x,y$（即 $d(x,y)$ 有界）有 $\kappa (x,y)\ge K$。则对任意两个初始分布 $\mu ,\nu$ 在一次随机游走后的分布 $\mu P,\nu P$（其中 $P$ 为转移算子）满足

$$W_1(\mu P,\nu P)\le (1-K)W_1(\mu ,\nu )$$

尤其，当 $K>0$ 时，Wasserstein 距离呈指数衰减；当 $K<0$ 时，距离呈指数膨胀。

证明见附录 B.1。证明思路是利用 $\kappa (x,y)$ 的定义及离散版 Kantorovich 对偶原理，对 Dirac 分布的行为进行估计，并扩展到一般分布。

4.3 曲率与复杂性体积增长

曲率下界与体积增长之间存在定性联系。

定理 4.4（非负曲率下的多项式增长）

假设复杂性图是局域有限的有向图，其对称版度有界，且存在 $K\ge 0$，使得对所有相邻 $x,y$ 有 $\kappa (x,y)\ge K$。则存在常数 $C,d_{\ast }$ 与 $T_0>0$，使得对所有 $T\ge T_0$ 有

$$V_{x_0}(T)\le C{T}^{d_{\ast }}$$

特别地，${\overline{\dim }}_{\mathrm{comp}}(x_0)\le d_{\ast }$。

定理 4.5（严格负曲率下的指数增长）

假设存在 $K_0>0$ 与 $\delta >0$，使得对所有满足 $d(x,y)\le \delta$ 的点对有 $\kappa (x,y)\le -K_0$。则存在常数 $c,\lambda >1$ 与 $T_0>0$，使得对所有 $n\in \mathbb{N}$，

$$V_{x_0}(n{T}_0)\ge c{\lambda }^n$$

这两个定理表明，非负曲率使复杂性体积增长被多项式控制，而局部严格负曲率导致复杂性空间的指数爆炸。证明思路分别借鉴了连续情形中的 Bishop–Gromov 比较理论与 Gromov 超曲率空间的体积增长估计，但完全在离散图上进行，详见附录 B.2 与 B.3。

5 可达域、复杂性视界与相变

本节讨论随复杂性预算 $T$ 增加，可达域族 $\{B_T(x_0)\}$ 的拓扑演化，并用简单的代数拓扑指标刻画复杂性相变。

5.1 复杂性视界的定义

定义 5.1（复杂性视界）

对固定起点 $x_0$，称序列 $\{T_c^{(k)}{\}}_{k\in K}\subset (0,\infty )$ 为复杂性视界点族，若对每个 $T_c^{(k)}$ 存在拓扑不变量 $\mathcal{I}$（例如连通分支数、第一 Betti 数、基本群阶等），使得当 $T$ 穿越 $T_c^{(k)}$ 的邻域时，$\mathcal{I}(B_T(x_0))$ 发生跳变。

在实际中，最简单的选择是连通分支数与第一 Betti 数。

定义 5.2（连通性相变）

设 $\mathrm{cc}(T)$ 表示 $B_T(x_0)$ 在对称图上的连通分支数。若存在 $T_c$ 使得

$$\underset{\epsilon \downarrow 0}{\lim }\mathrm{cc}(T_c-\epsilon )>\underset{\epsilon \downarrow 0}{\lim }\mathrm{cc}(T_c+\epsilon )$$

则称 $T_c$ 为连通性复杂性相变点。

定义 5.3（循环结构相变）

设 $b_1(T)$ 表示 $B_T(x_0)$ 的一阶 Betti 数（循环数量）。若存在 $T_c$ 使得 $b_1(T_c-\epsilon )\ne b_1(T_c+\epsilon )$ 对任意足够小的 $\epsilon >0$ 成立，则称 $T_c$ 为循环结构复杂性相变点。

5.2 相变与曲率的对比

在负曲率较强的区域，复杂性球往往快速包含大量“新的路径“，导致循环数迅速增长；而在非负曲率区域，复杂性球的扩张相对温和，循环结构增长受到抑制。

我们有如下定性命题。

命题 5.4（局部非负曲率下循环增长的约束）

假设存在 $R>0$，使得在 $B_R(x_0)$ 内所有相邻点对的曲率满足 $\kappa (x,y)\ge 0$，且图度有界。则存在常数 $C_1,C_2>0$，使得对 $T\le R$，

$$b_1(T)\le C_1{V}_{x_0}(T)+C_2$$

特别地，若 $V_{x_0}(T)$ 多项式有界，则 $b_1(T)$ 也至多多项式增长。

证明见附录 C.1。

命题 5.5（局部负曲率下循环的快速出现）

若在某个环形层 $A=B_{T_2}(x_0)\setminus B_{T_1}(x_0)$ 中，存在大量点对 $x,y$ 满足 $\kappa (x,y)\le -K_0$ 且 $d(x,y)$ 有界，则随着 $T$ 从 $T_1$ 增加到 $T_2$，存在至少一次循环结构相变点 $T_c\in (T_1,T_2)$。

证明见附录 C.2。

这些结果表明，曲率不仅控制体积增长，也在一定程度上决定复杂性视界与“结构相变“的出现。这为理解算法在增加资源时出现“突然顿悟“或“结构性跃迁“提供了几何解释。

6 流形极限与统一时间刻度

本节讨论当计算宇宙具有良好的连续极限时，复杂性图如何收敛到一个 Riemann 流形，以及离散复杂性距离如何逼近连续测地距离。我们还讨论了统一时间刻度 $\kappa (\omega )$ 与复杂性度量之间的一致性。

6.1 复杂性图的流形极限

考虑一族计算宇宙 $\{U_{\mathrm{comp}}^{(h)}{\}}_{h>0}$，其中 $h$ 表示离散尺度（例如格点间距、控制参数步长），对应复杂性图 $G_{\mathrm{comp}}^{(h)}=(X^{(h)},E^{(h)},w^{(h)})$ 与距离 $d^{(h)}$。

定义 6.1（Gromov–Hausdorff 收敛）

若存在 Riemann 流形 $(\mathcal{M},G)$ 与点 ${\theta }_0\in \mathcal{M}$，以及嵌入映射 ${\Phi }_h:X^{(h)}\to \mathcal{M}$，使得对任意有界 $R>0$：

1. ${\Phi }_h(B_R^{(h)}(x_0^{(h)}))$ 在 $\mathcal{M}$ 中 Hausdorff 收敛到 $B_R({\theta }_0)$；
2. 对所有 $x,y\in B_R^{(h)}(x_0^{(h)})$，有 $$\underset{h\to 0}{\lim }{d}_G({\Phi }_h(x),{\Phi }_h(y))=\underset{h\to 0}{\lim }{d}^{(h)}(x,y)$$

则称复杂性图族 $(X^{(h)},d^{(h)})$ 在局部 Gromov–Hausdorff 意义下收敛到 $(\mathcal{M},d_G)$。

这里 $d_G$ 为由 Riemann 度量 $G$ 诱导的测地距离。

定理 6.2（一维情形的严格收敛）

设对每个 $h>0$，复杂性图 $G_{\mathrm{comp}}^{(h)}$ 的顶点 $X^{(h)}=h\mathbb{Z}\cap [-L,L]$，有向边 $E^{(h)}=\{(x,x\pm h)\}$，边权 $w^{(h)}(x,x\pm h)=c(x)h$，其中 $c:[-L,L]\to (c_{\min },c_{\max })$ 为连续正函数。则在 $h\to 0$ 时，度量空间 $(X^{(h)},d^{(h)})$ 在 Gromov–Hausdorff 意义下收敛到区间 $[-L,L]$ 上的 Riemann 流形 $(\mathcal{M},G)$，其中 $\mathcal{M}=[-L,L]$，度量为

$$G(\theta )=c(\theta {)}^2\mathrm{d}{\theta }^2$$

测地距离为

$$d_G({\theta }_1,{\theta }_2)=\left|{\int }_{{\theta }_1}^{{\theta }_2}c(\theta )\mathrm{d}\theta \right|$$

并且对任意 ${\theta }_1,{\theta }_2\in [-L,L]$，有

$$\underset{h\to 0}{\lim }{d}^{(h)}({\theta }_1^{(h)},{\theta }_2^{(h)})=d_G({\theta }_1,{\theta }_2)$$

其中 ${\theta }^{(h)}\in X^{(h)}$ 为最近点采样。

证明见附录 D.1。这是一个一维情况下“离散代价和 → 连续路径积分“的严格版本。

更高维情形可通过类似构造得到，在适当的规律性与局域性假设下，一族复杂性图可收敛到某个流形 $(\mathcal{M},G)$，其中 $G$ 由局部代价函数族的二阶结构决定。

6.2 统一时间刻度与复杂性度量的一致性

假设存在物理统一时间刻度密度 $\kappa (\omega )$，使得每一步计算对应某个物理过程，其时间代价为

$$\tau (x,y)={\int }_{\Omega (x,y)}\kappa (\omega )\mathrm{d}{\mu }_{x,y}(\omega )$$

其中 $\Omega (x,y)$ 为激活频段，${\mu }_{x,y}$ 为谱测度。若单步代价 $\mathsf{C}(x,y)$ 被选择为 $\tau (x,y)$ 的适当缩放，则复杂性距离 $d$ 在大尺度上与物理时间距离一致。

在流形极限中，这意味着度量 $G$ 的体积元与物理时间刻度之间存在一致性关系。例如在一维情形中，若我们令

$$c(\theta )={\int }_{\Omega (\theta )}\kappa (\omega )\mathrm{d}{\mu }_{\theta }(\omega )$$

则复杂性测地距离恰为沿世界线的物理时间积累。这为后续将复杂性几何与物理边界时间几何统一提供了精确界面。

7 总结与后续方向

本文在计算宇宙的离散公理基础上，引入了复杂性图、复杂性距离、复杂性体积与复杂性维数，构建了一套“离散复杂性几何“的基本框架。通过基于 Wasserstein 距离的离散 Ricci 曲率，我们把局部“问题难度“与体积增长、视界结构联系起来；通过复杂性球的拓扑变化，我们给出了复杂性相变与视界跃迁的几何刻画；通过流形极限，我们展示了在统一时间刻度下，复杂性图如何收敛为 Riemann 流形，从而与物理时间几何对接。

这一框架为后续若干方向提供了基础：例如，将信息质量函数 $\mathsf{I}$ 的梯度结构与信息几何结合，构造“时间–信息–复杂性“的联合变分原理；在复杂性流形上引入观察者的注意力与知识图谱结构；以及在范畴论层面上，将物理宇宙范畴与计算宇宙范畴通过复杂性几何建立等价。本文的技术工具完全基于离散结构，连续几何则作为极限而出现，这确保了整个理论栈在根本上仍然是一个离散的计算宇宙叙述。

附录 A：复杂性距离与体积性质的证明细节

A.1 命题 2.4 的证明

命题重述

在 $X_{\mathrm{fin}}$ 上，复杂性距离 $d$ 满足：

1. $d(x,x)=0$；
2. $d(x,y)\ge 0$，且 $d(x,y)=0$ 蕴含 $x=y$；
3. $d(x,z)\le d(x,y)+d(y,z)$。

若 $\mathsf{T}$ 在 $X_{\mathrm{fin}}$ 上可逆且代价对称，则 $d(x,y)=d(y,x)$。

证明

由定义，对任意路径 $\gamma$，代价 $\mathsf{C}(\gamma )={\sum }_k\mathsf{C}(x_k,x_{k+1})$，其中每项非负，故 $\mathsf{C}(\gamma )\ge 0$，从而 $d(x,y)={\inf }_{\gamma :x\to y}\mathsf{C}(\gamma )\ge 0$。

1. 对 $x\in X_{\mathrm{fin}}$，考虑零长度路径 $\gamma =(x)$，约定 $\mathsf{C}(\gamma )=0$，则 $d(x,x)\le 0$。另一方面，由非负性，$d(x,x)\ge 0$，故 $d(x,x)=0$。

2. 若 $d(x,y)=0$，由定义，对任意 $\epsilon >0$，存在路径 ${\gamma }_{\epsilon }:x\to y$ 使得 $\mathsf{C}({\gamma }_{\epsilon })<\epsilon$。由于每一步代价 $\mathsf{C}(x_k,x_{k+1})\ge c_{\min }>0$（在物理子集上可假设存在统一下界），若路径长度 $n_{\epsilon }\ge 1$，则 $$\mathsf{C}({\gamma }_{\epsilon })\ge n_{\epsilon }{c}_{\min }\ge c_{\min }$$ 与 $\mathsf{C}({\gamma }_{\epsilon })<\epsilon$ 矛盾（取 $\epsilon <c_{\min }$）。因此唯一路径为零长度路径，故 $x=y$。

3. 对任意 $\epsilon >0$，存在路径 ${\gamma }_1:x\to y$、${\gamma }_2:y\to z$，使得 $$\mathsf{C}({\gamma }_1)\le d(x,y)+\epsilon /2$$ $$\mathsf{C}({\gamma }_2)\le d(y,z)+\epsilon /2$$ 串接路径 $\gamma ={\gamma }_1\cdot {\gamma }_2$ 满足 $$\mathsf{C}(\gamma )=\mathsf{C}({\gamma }_1)+\mathsf{C}({\gamma }_2)\le d(x,y)+d(y,z)+\epsilon$$ 由 $d(x,z)$ 为所有路径代价的下确界，$d(x,z)\le \mathsf{C}(\gamma )$，故 $$d(x,z)\le d(x,y)+d(y,z)+\epsilon$$ 令 $\epsilon \to 0$ 即得三角不等式。

在可逆且代价对称的情形下，对任一路径 $\gamma :x\to y$，存在逆路径 ${\gamma }^{-1}:y\to x$ 具有相同代价，从而 $d(y,x)\le d(x,y)$，反向不等式同理，故 $d(x,y)=d(y,x)$。

证毕。

A.2 命题 2.6 的证明

1. 单调性：若 $T_1<T_2$，则任何满足 $d(x_0,x)\le T_1$ 的点必然满足 $d(x_0,x)\le T_2$，故 $B_{T_1}(x_0)\subseteq B_{T_2}(x_0)$，进而 $V_{x_0}(T_1)\le V_{x_0}(T_2)$。

2. 若存在 $C>0$ 使 $V_{x_0}(T_1+T_2)\le C{V}_{x_0}(T_1)V_{x_0}(T_2)$，则对 $T=n{T}_0$ 形式的点可用标准次可加性技巧证明 $\frac{1}{T}\log V_{x_0}(T)$ 的上界存在。从而 $\log V_{x_0}(T)$ 随 $T$ 至多线性增长，详细论证略去。

A.3 命题 3.2 的证明

在有界度与边权有界的条件下，可以把复杂性球 $B_T(x_0)$ 夹在两个步数球之间。

令 $N(x_0,n)$ 为从 $x_0$ 出发 $n$ 步可达的点集合，不计代价。由于度有界 $D$，有 $|N(x_0,n)|\le D^n$。另一方面，边权下界 $c_{\min }$ 与上界 $c_{\max }$ 给出

$$B_T(x_0)\subseteq N(x_0,\lfloor T/c_{\min }\rfloor )$$

$$N(x_0,\lfloor T/c_{\max }\rfloor )\subseteq B_T(x_0)$$

在某些规则图（例如晶格或 Cayley 图）中，$|N(x_0,n)|$ 可精确估计为多项式增长 $\Theta (n^{d_{\ast }})$，则 $V_{x_0}(T)$ 也随 $T$ 多项式增长，阶数 $d_{\ast }$ 即为复杂性维数。详细构造需要对图结构作出更具体假设，此处略写，详见对应的 Cayley 图体积增长理论。

A.4 命题 3.3 的证明

由假设，对某个 $T_0>0$，有 $V_{x_0}(n{T}_0)\ge {\lambda }^n$。令 $T=n{T}_0$，则

$$\frac{\log V_{x_0}(T)}{\log T}\ge \frac{n\log \lambda }{\log (n{T}_0)}$$

令 $n\to \infty$，右侧极限为 $\infty$，从而 ${\overline{\dim }}_{\mathrm{comp}}(x_0)=\infty$。

证毕。

附录 B：离散 Ricci 曲率与体积增长的证明细节

B.1 定理 4.3 的证明

考虑任意两个概率分布 $\mu ,\nu$ 在 $X$ 上，令 $P$ 为由 $m_x$ 定义的转移算子。对 Dirac 分布 ${\delta }_x,{\delta }_y$，有

$$W_1({\delta }_{x}P,{\delta }_{y}P)=W_1(m_x,m_y)$$

由 Ricci 曲率定义

$$\kappa (x,y)=1-\frac{W_1(m_x,m_y)}{d(x,y)}\ge K$$

即

$$W_1(m_x,m_y)\le (1-K)d(x,y)$$

对一般分布 $\mu ,\nu$，利用 Kantorovich 对偶形式

$$W_1(\mu ,\nu )=\underset{\phi \in {\mathrm{Lip}}_1}{\sup }\sum _x\phi (x)(\mu (x)-\nu (x))$$

其中 ${\mathrm{Lip}}_1$ 为 1-Lipschitz 函数族。对任意 $\phi \in {\mathrm{Lip}}_1$，考虑 $\phi P$ 的 Lipschitz 常数。对任意 $x,y$，有

$$|\phi P(x)-\phi P(y)|=\left|\sum _z\phi (z)(m_x(z)-m_y(z))\right|\le W_1(m_x,m_y)\le (1-K)d(x,y)$$

因此 $\phi P$ 为 $(1-K)$-Lipschitz 函数。代回对偶式可得

$$W_1(\mu P,\nu P)\le (1-K)W_1(\mu ,\nu )$$

证毕。

B.2 定理 4.4 的证明思路

在非负曲率下，随机游走的 Wasserstein 收缩性质意味着，起点附近的随机游走不会快速向外扩散，体积增长受到限制。精确证明可以借鉴 Bishop–Gromov 比较：在离散图上构造“径向函数“，并利用曲率下界控制其离散 Laplace 的符号，进而比较复杂性球与某个标准模型（例如整数格）的体积。最终得到 $V_{x_0}(T)$ 至多多项式增长。完整证明需要一系列技术引理，此处略去细节。

B.3 定理 4.5 的证明思路

在局部负曲率区域，Wasserstein 距离每一步被放大一个因子 $1-K_0$，导致小扰动在多步后指数放大。这可被用来构造一个“树状扩张“子图，使得从 $x_0$ 出发，每增加 $T_0$ 复杂性预算，可达点数至少乘上一个常数因子。通过适当选取 $T_0$ 并控制重叠，可证明 $V_{x_0}(n{T}_0)\ge c{\lambda }^n$ 的指数下界。技术细节涉及对局部球的覆盖与树嵌入构造，限于篇幅不再详述。

附录 C：复杂性视界与拓扑相变的证明细节

C.1 命题 5.4 的证明思路

在局部非负曲率与度有界的条件下，可以证明复杂性球 $B_T(x_0)$ 的“仔细展开“不会产生过多独立环。更具体地，利用图的 Euler 特征公式

$$\chi (B_T)=|V(B_T)|-|E(B_T)|+b_1(B_T)$$

其中 $b_1$ 为一阶 Betti 数。度有界性给出 $|E(B_T)|\le D|V(B_T)|$，而非负曲率可用于控制局部“树偏差“，使得 $|E(B_T)|$ 与 $|V(B_T)|$ 之间的差异被线性控制，从而 $b_1(B_T)$ 也被 $|V(B_T)|$ 线性控制。常数 $C_1,C_2$ 则来自这些估计的具体系数。

C.2 命题 5.5 的证明思路

在局部负曲率区域中，存在大量点对 $x,y$ 满足 $\kappa (x,y)\le -K_0$，意味着随机游走在这些区域中具有“发散性“。通过构造连接这些点对的多条独立路径，可以在复杂性球的某个壳层中形成新的独立环路，从而使一阶 Betti 数在某个 $T_c$ 附近发生跳变。这一构造类似于在负曲率流形中构造闭合测地线的标准方法，但在离散图中则以组合方式实现。

附录 D：一维流形极限的严格证明

D.1 定理 6.2 的详细证明

设 $X^{(h)}=h\mathbb{Z}\cap [-L,L]$，边集 $E^{(h)}=\{(x,x\pm h):x\in X^{(h)},x\pm h\in X^{(h)}\}$，边权 $w^{(h)}(x,x\pm h)=c(x)h$，其中 $c:[-L,L]\to (c_{\min },c_{\max })$ 为连续正函数。

对任意 $x,y\in X^{(h)}$，从 $x$ 到 $y$ 的路径等价于一条沿线段 $[x,y]$ 以步长 $h$ 前进的离散路径，其最小代价为

$$d^{(h)}(x,y)=\sum _{k=0}^{n-1}c(x_k)h$$

其中 $x=x_0,x_1,\dots ,x_n=y$，且 $x_{k+1}-x_k=\pm h$。当 $h\to 0$ 且 $x,y$ 固定时，Riemann 和收敛到积分

$${\int }_x^{y}c(\theta )\mathrm{d}\theta$$

这定义了连续距离 $d_G(x,y)$。

Gromov–Hausdorff 收敛可通过构造嵌入 ${\Phi }_h:X^{(h)}\to [-L,L]$ 为自然包含映射，并证明对任意有界区间内的两点对，离散距离与连续距离之差在 $h\to 0$ 时一致趋于 0。Hausdorff 距离收敛性来自 $X^{(h)}$ 在 $[-L,L]$ 中的致密性。详细估计可通过标准的 Riemann 和误差上界完成，此处不再逐行展开。

证毕。