计算宇宙中的几何复杂性分层与复杂度类

统一时间刻度下的体积增长、曲率与可计算性边界

摘要

在此前对“计算宇宙“ $U_{\mathrm{comp}}=(X,\mathsf{T},\mathsf{C},\mathsf{I})$ 的系统研究中,我们先后构造了离散复杂性几何、离散信息几何、统一时间刻度诱导的控制流形 $(\mathcal{M},G)$、任务信息流形 $({\mathcal{S}}_Q,g_Q)$ 与时间–信息–复杂性联合变分原理,并在可逆量子元胞自动机(QCA)子类上建立了物理宇宙范畴与计算宇宙范畴之间的等价关系。另一方面,经典复杂性理论中的复杂度类(如 P、NP、BQP)主要通过“随输入规模 $n$ 的步数/门数上界“来定义,缺乏与几何结构的系统对应。

本文在计算宇宙的几何框架内提出一套几何复杂性分层理论:通过复杂性距离 $d_{\mathrm{comp}}$、复杂性球体积增长 $V_{x_0}(T)$、离散 Ricci 曲率与控制流形 $(\mathcal{M},G)$ 的测地结构,对一族自然的复杂度类给出几何刻画,并证明若干“复杂度类 ↔ 几何不变量“的约束定理。

具体而言,我们首先在计算宇宙上引入输入编码族 $\{{\iota }_n:{\Sigma }^n\to X\}$,将语言 $L\subset {\Sigma }^{\ast }$ 的判定视为从输入配置到“接受区域“ $A\subset X$ 的可达性问题。对每个输入长度 $n$,用复杂性距离定义最小计算半径 $T_L(n)$,并据此引入几何复杂度类

$$\mathbf{GC}(\mathrm{poly})=\{L:T_L(n)\le C{n}^k\},\mathbf{GC}(\exp )=\{L:T_L(n)\le 2^{\mathcal{O}(n)}\},$$

等。我们证明:在一个自然的“图灵–QCA–计算宇宙等价“假设下,$\mathbf{GC}(\mathrm{poly})$ 与传统的 P 类等价(相差至多多项式重标度),而 $\mathbf{GC}(\exp )$ 覆盖 EXP 类。

其次,我们将体积增长与复杂性维数引入复杂度类的几何刻度:对给定起点 $x_0$ 与复杂性球 $B_T(x_0)$,体积增长指数

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

被用来刻画局域计算空间的“维数“。我们证明一个多项式维数约束定理:若在某一区域内 ${\dim }_{\mathrm{comp}}(x_0)\le d$,且所有相关语言的判定轨道都局限于该区域,则所有这些语言的几何复杂度函数 $T_L(n)$ 至多为多项式,且指数 $k$ 被 $d$ 所控制。反之,在负曲率导致体积指数增长的区域中,可以构造一族问题,其几何复杂度函数必然达到或接近指数级,体现了“负曲率 ↔ 指数复杂度“的几何–复杂性联系。

再次,我们引入几何复杂度视界:对给定基点与增长阶 $f(n)$,定义可在半径 $f(n)$ 内判定的语言族,并用离散 Ricci 曲率下界与体积比较定理证明:在非负曲率区域,如果体积增长受到多项式上界,则不存在“几何上本质指数难“的语言;而在局部强负曲率区域,则存在自然的语言族,其复杂度视界必然超出任何给定多项式半径。

最后,我们讨论量子情形:在 QCA 宇宙中,通过对控制–散射流形 $(\mathcal{M},G)$ 与相位干涉结构的分析,给出 BQP 类的几何上界:在满足统一时间刻度与适当干涉正则性的前提下,BQP 中的语言在控制流形上的最小测地长度仍受多项式上界,而体积爆炸与负曲率更多影响的是“非干涉可利用“的经典复杂度部分。

本文将传统复杂度类与计算宇宙中的几何不变量(体积增长、曲率、视界)系统连接起来,为后续将“复杂性相变““能力–风险前沿“等更高层概念几何化提供了基础。

1 引言

经典复杂性理论通常基于抽象模型(图灵机、布尔电路、量子电路等)来定义复杂度类。例如,P 类由存在多项式步数的确定性图灵机判定的语言构成,NP 类由存在多项式长度证据可被多项式时间验证的语言构成,BQP 类则由存在多项式大小量子电路在有界误差下判定的语言构成。

这些定义高度依赖具体模型,尽管此类模型在多项式时间下彼此等价,但复杂度类本身缺乏一个统一的几何–结构化刻画:

• P 类内部的问题在“计算空间“中是否具有某种共同的几何特征(例如局部体积增长受限、曲率非负)?
• 非 P 类(例如典型 NP 困难问题)是否必然在某些区域呈现“负曲率 + 体积指数爆炸“的几何特征?
• BQP 类相对 P 类的优势是否可以理解为“在相同几何背景下利用了额外的干涉结构“?

在此前的“计算宇宙“框架中,我们已经引入了适合承载这些问题的几何对象:

1. 复杂性图 $G_{\mathrm{comp}}=(X,E,\mathsf{C})$ 上的距离 $d_{\mathrm{comp}}$、体积增长 $V_{x_0}(T)$、复杂性维数 ${\dim }_{\mathrm{comp}}(x_0)$ 与离散 Ricci 曲率 $\kappa (x,y)$;
2. 统一时间刻度下的控制流形 $(\mathcal{M},G)$,其测地距离 $d_G$ 逼近离散复杂性距离;
3. 配置–信息映射 ${\Phi }_Q:X\to {\mathcal{S}}_Q$ 与任务信息流形 $({\mathcal{S}}_Q,g_Q)$,为“输入–输出语义“提供几何背景。

本文旨在用这些工具对复杂度类进行几何分层:

• 用复杂性距离定义语言的几何复杂度函数 $T_L(n)$;
• 用体积增长与维数刻画“一个区域内可容纳多少不同的计算路径与输出“;
• 用曲率描述“局部路径发散/收缩结构“,从而反映“局部硬度“;
• 用复杂性视界刻画“多大半径内可完成某类判定“。

我们先在完全一般的计算宇宙设定下给出几何复杂度类的定义,然后在“图灵–QCA–计算宇宙等价“假设下,将这些几何类与传统复杂度类联系起来。

2 预备:计算宇宙、复杂性几何与输入编码

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$,否则 $\mathsf{C}(x,y)\in (0,\infty )$,对路径加性;
4. $\mathsf{I}:X\to \mathbb{R}$ 为信息质量或任务相关评分。

复杂性距离定义为

$$d_{\mathrm{comp}}(x,y)=\underset{\gamma :x\to y}{\inf }\sum _{(u,v)\in \gamma }\mathsf{C}(u,v),$$

复杂性球与体积为

$$B_T(x_0)=\{x\in X:d_{\mathrm{comp}}(x_0,x)\le T\},V_{x_0}(T)=|B_T(x_0)|.$$

复杂性维数定义为

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

若该上极限有限则视为局部维数。

离散 Ricci 曲率 $\kappa (x,y)$ 通过局部转移分布 $m_x,m_y$ 与 Wasserstein 距离给出,在本篇只用其符号与粗略性质:非负曲率倾向于体积多项式增长,负曲率倾向于体积指数增长。

2.2 输入编码与语言的几何视角

设 $\Sigma$ 为有限字母表,${\Sigma }^{\ast }={\bigcup }_{n\ge 0}{\Sigma }^n$ 为字串集合。语言 $L\subset {\Sigma }^{\ast }$ 是一个判定问题。要在计算宇宙中讨论 $L$ 的复杂度,需要一个编码族。

定义 2.1(输入编码族)

一个输入编码族是映射

$${\iota }_n:{\Sigma }^n\to X,n\in \mathbb{N},$$

使得对每个 $w\in {\Sigma }^n$,${\iota }_n(w)$ 为计算宇宙中表示“输入为 $w$“的初始配置。

我们假设编码族满足以下自然条件:

1. 多项式可逆性:存在常数 $c,k>0$,使得从 ${\iota }_n(w)$ 解码回 $w$ 的计算复杂度至多为 $c{n}^k$;
2. 局域性:编码对局部修改 $w\mapsto w^{\prime }$ 对应于有限局部修改配置。

定义 2.2(接受区域与判定演化)

对语言 $L\subset {\Sigma }^{\ast }$,定义接受区域 $A_L\subset X$ 为一子集,使得存在更新策略(由 $\mathsf{T}$ 与可能的控制变量决定)满足:

• 若 $w\in L$,则从 $x_{\mathrm{in}}={\iota }_n(w)$ 出发,存在终止配置 $x_{\mathrm{acc}}\in A_L$ 在有限复杂性距离内可达;
• 若 $w\notin L$,则从 $x_{\mathrm{in}}$ 出发不可达任何接受态,或可达拒绝态集合 $R_L\subset X\setminus A_L$。

不区分显式拒绝时,可简单要求从非成员输入到接受区域的最短距离为 $+\infty$。

3 几何复杂度函数与几何复杂度类

3.1 几何复杂度函数

定义 3.1(几何复杂度函数)

对计算宇宙 $U_{\mathrm{comp}}$、编码族 $\{{\iota }_n\}$ 与语言 $L\subset {\Sigma }^{\ast }$,定义几何复杂度函数

$$T_L(n)=\underset{w\in {\Sigma }^n}{\sup }\underset{x\in A_L}{\inf }{d}_{\mathrm{comp}}({\iota }_n(w),x),$$

如果对某些 $w$ 无接受路径则 $T_L(n)=+\infty$。

$T_L(n)$ 表示在最优策略下,对所有长度为 $n$ 的输入,走到某个接受态所需的最大复杂性距离。

在统一时间刻度解释下,$T_L(n)$ 即为在任务 $L$ 下“最坏输入的最小物理时间“上界。

3.2 几何复杂度类

定义 3.2(几何复杂度类)

在固定计算宇宙与编码族下,定义:

• 多项式几何复杂度类

  $$\mathbf{GC}(\mathrm{poly})=\{L\subset {\Sigma }^{\ast }:\exists C,k>0,\forall n,T_L(n)\le C{n}^k\};$$

• 次指数几何复杂度类

  $$\mathbf{GC}(\mathrm{subexp})=\{L:\forall \epsilon >0,\exists C_{\epsilon }>0,\forall n,T_L(n)\le C_{\epsilon }{2}^{\epsilon n}\};$$

• 指数几何复杂度类

  $$\mathbf{GC}(\exp )=\{L:\exists C,c>0,\forall n,T_L(n)\le C{2}^{cn}\}.$$

可以进一步定义对数空间几何类、概率几何类等,此处聚焦时间复杂度对应的几何半径。

3.3 与传统复杂度类的等价

在“图灵–QCA–计算宇宙多项式等价“的前提下,可以证明:

命题 3.3(几何 P 类与传统 P 类的等价,纲要)

设 $U_{\mathrm{comp}}$ 是由通用确定性图灵机或可逆 CA/QCA 实现的计算宇宙,并选择自然的编码族 $\{{\iota }_n\}$。则存在常数 $c_1,c_2>0$,使得:

1. 若 $L\in \mathbf{P}$,则 $L\in \mathbf{GC}(\mathrm{poly})$,且 $$T_L(n)\le c_1{n}^{k_1}$$ 对某个 $k_1$ 成立;
2. 若 $L\in \mathbf{GC}(\mathrm{poly})$,则存在常数 $k_2$,使得 $L\in \mathbf{TIME}(n^{k_2})$。

因此,$\mathbf{GC}(\mathrm{poly})$ 与 P 在多项式尺度下等价。

类似地,可对 EXP、E、BQP 等复杂度类给出相应的几何版本。由于这部分与经典多模型等价性高度相似,详尽证明留至附录 C,仅在此给出结构。

4 体积增长、复杂性维数与多项式复杂度约束

本节讨论复杂性球体积增长如何约束几何复杂度函数 $T_L(n)$,从而提供“几何条件 ⇒ 多项式复杂度“的充分条件。

4.1 体积增长与信息编码能力

直观地,复杂性球 $B_T(x_0)$ 中可容纳的不同计算轨道与输出状态数量受 $V_{x_0}(T)$ 上界控制:如果在半径 $T$ 内只有多项式个不同状态,则不可能在该半径内实现指数多的不同输出模式,否则 pigeonhole 原理会被违反。

在语言判定问题中,我们关心的是区分不同输入的能力:如果所有长度 $n$ 的输入都映射到 $B_{T_L(n)}(x_0)$ 内的终态集合,则 $|B_{T_L(n)}(x_0)|$ 至少要与 $|{\Sigma }^n|=|\Sigma {|}^n$ 在信息上兼容,否则某些输入对将被混淆。

命题 4.1(体积–输入数目下界)

设编码 ${\iota }_n$ 单射,且接受态集合 $A_L\subset X$ 对不同输入不混淆(即 $w_1\ne w_2\Rightarrow$ 对应终态不同)。则对任何 $n$,

$$V_{x_0}(T_L(n))\ge |\Sigma {|}^n.$$

证明:所有 $w\in {\Sigma }^n$ 对应的终点都在 $B_{T_L(n)}(x_0)$ 内,且相互不同,因此体积至少为输入数目。

从而若 $V_{x_0}(T)$ 多项式增长,则 $T_L(n)$ 至少为 $\Omega (\log |\Sigma {|}^n)=\Omega (n)$;反之,对给定体积增长形状,可以给出 $T_L(n)$ 的上界与下界之间的约束。

4.2 多项式体积增长 ⇒ 多项式复杂度

我们关心的是:若体积增长本身多项式,是否强迫复杂度函数多项式?

定理 4.2(体积多项式增长的复杂度约束)

设存在起点 $x_0$ 与常数 $C_0,k_0>0$,使得对充分大 $T$,

$$V_{x_0}(T)\le C_0{T}^{k_0}.$$

若语言 $L$ 在编码 ${\iota }_n$ 下满足:

1. 对某个常数 $c>0$,所有输入 $w\in {\Sigma }^n$ 的终态都位于 $B_{c{T}_L(n)}(x_0)$ 的子集内;
2. 对不同输入终态互不混淆;

则存在常数 $C_1,k_1>0$,使得

$$T_L(n)\ge C_1{n}^{1/k_0}.$$

同时,由体积上界与 pigeonhole 原理可推得

$$T_L(n)\ge \Omega (|\Sigma {|}^{n/k_0})\Rightarrow \text{不可实现},$$

因此对可实现的语言,$T_L(n)$ 的增长不能超过某个多项式阶。更精确地,在自然的编码与空间局域结构下,对一大类语言都有

$$T_L(n)=\Theta \left(n^{1/k_0}\right).$$

证明思路见附录 A。

直观地,该定理说明:在一个体积增长仅为多项式的计算宇宙区域内,不可能存在“本质指数难“的语言——复杂度的指数爆炸需要体积的指数膨胀作为“承载空间“。

5 曲率、体积指数爆炸与指数复杂度

本节利用离散 Ricci 曲率与体积比较定理,说明在局部负曲率区域内必然存在指数复杂度的语言,从而得到“负曲率 ↔ 指数复杂度“的几何–复杂性联系。

5.1 负曲率与体积指数增长

前文复杂性几何中已证明:若存在 $K_0>0$ 与 $T_0>0$,使得在 $B_{T_0}(x_0)$ 内所有相邻点对的曲率满足 $\kappa (x,y)\le -K_0$,则存在常数 $c,\lambda >1$ 与整数 $n_0$,使得

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

即体积指数增长。

5.2 指数复杂度语言的构造

在这样的区域内,我们可以构造一族语言 $\{L_{\alpha }\}$,使得每个 $L_{\alpha }$ 的几何复杂度函数 $T_{L_{\alpha }}(n)$ 至少呈指数增长。构造思路如下:

1. 选择一个适当的编码,使得长度 $n$ 的输入可枚举为 $|\Sigma {|}^n$ 个前缀;
2. 在负曲率区域中选取一族“分叉树“型子图,其分支因子与层数匹配使得不同输入轨道在复杂性半径 $T$ 内离散地覆盖指数多的点;
3. 通过接受区域的设计,强迫不同输入走向不同的分叉叶子,且这些叶子相互距离至少为某个常数,保证不可混淆;
4. 利用体积下界与路径结构证明:在半径小于某个指数函数前,不可能为所有输入分配不同叶子,从而得出复杂度下界。

定理 5.1(负曲率区域中的指数复杂度语言)

在上文负曲率假设下,存在语言族 $\{L_{\alpha }\}$ 与编码族 $\{{\iota }_n^{\alpha }\}$,使得对每个 $\alpha$ 存在常数 $c_{\alpha }>0$,满足

$$T_{L_{\alpha }}(n)\ge 2^{c_{\alpha }n}\text{对充分大}n.$$

证明概要见附录 B。

该结果并不说明“所有负曲率区域都对应 NP–hard“,而是表明在几何上存在指数复杂度的“可嵌入“,即负曲率提供了指数多 geodesic 分支的空间。

6 量子情形:QCA 宇宙与 BQP 的几何上界

本节简要讨论量子计算情形,在 QCA 宇宙中对 BQP 类给出几何上界。

6.1 QCA 宇宙与控制流形

在可逆量子元胞自动机宇宙中,全局演化由酉算子 $U$ 给出,其局域结构与统一时间刻度密度 $\kappa (\omega ;\theta )$ 定义了一族控制参数 $\theta \in \mathcal{M}$ 与度量 $G_{ab}(\theta )$。量子电路模型可视为特殊的 QCA,实现 BQP 类语言。

对量子算法,我们可将其控制路径 $\theta (t)$ 看作在 $(\mathcal{M},G)$ 上的一条曲线,长度

$$L_G[\theta ]={\int }_0^T\sqrt{G_{ab}(\theta (t)){\dot{\theta }}^a{\dot{\theta }}^b}\mathrm{d}t$$

对应量子计算的总“物理时间“或门数等价量。

6.2 BQP 几何上界

在标准模型等价性与适当正则性下,可以证明:

命题 6.1(BQP 的几何上界)

对任一语言 $L\in \mathbf{BQP}$,存在 QCA 宇宙与控制流形 $(\mathcal{M},G)$ 以及编码族 $\{{\iota }_n\}$,使得其几何复杂度函数 $T_L(n)$ 与控制测地长度之间存在多项式等价:

$$T_L(n)\le C_1{n}^{k_1}⟺\exists {\theta }_n(t)\text{使}{L}_G[{\theta }_n]\le C_2{n}^{k_2},$$

其中 $C_1,C_2,k_1,k_2$ 为常数,且经典几何复杂度类 $\mathbf{GC}(\mathrm{poly})$ 与 BQP 在控制流形的测地长度意义下共享多项式上界。

在此意义上,量子优势主要体现在利用了 Hilbert 空间结构与相位干涉,使得在相同几何长度下可“并行探索“更多路径,而不是打破统一时间刻度诱导的几何上界。

详细证明依赖于门集通用性与 QCA 模拟量子电路的标准构造,略去不表。

7 结论

本文在计算宇宙与统一时间刻度–复杂性几何框架下,构建了一套几何复杂性分层理论:通过复杂性距离、体积增长、曲率与控制流形测地结构,对传统复杂度类给出了几何刻画。

我们引入了几何复杂度函数 $T_L(n)$ 与几何复杂度类 $\mathbf{GC}(\mathrm{poly})$、$\mathbf{GC}(\exp )$ 等,并在“图灵–QCA–计算宇宙等价“假设下证明了与 P、EXP 等传统复杂度类的多项式尺度等价。通过分析复杂性球体积增长与复杂性维数,我们证明:在体积多项式增长的区域内,不存在几何上本质指数难的问题,而在负曲率导致体积指数膨胀的区域内,可以构造指数复杂度语言族。

此外,本文简要讨论了量子情形下的 BQP 类,指出在统一时间刻度与控制流形度量下,BQP 语言的几何复杂度仍受到多项式上界约束,量子优势体现在利用了 Hilbert 空间干涉结构,而非打破几何上限。

这些结果为后续若干方向提供了基础:例如,“复杂性相变“可被视为几何结构(体积增长与曲率)发生突变时复杂度类的分层变化;“能力–风险前沿“可被描述为在复杂性几何上同时考虑任务信息收益与安全约束时的几何可达区域边界;而多观察者共识几何则可用复杂度视界与体积增长来刻画“集体可达知识空间“的限制。

附录 A:体积增长与几何复杂度的约束证明

A.1 命题 4.1 的证明

命题重述

设编码 ${\iota }_n:{\Sigma }^n\to X$ 单射,且存在判定机制使得不同输入的接受终态不同,即如果 $w_1\ne w_2$,则对应的终点 $x_{\mathrm{acc}}(w_1)\ne x_{\mathrm{acc}}(w_2)$。则

$$V_{x_0}(T_L(n))\ge |\Sigma {|}^n.$$

证明

对任意输入 $w\in {\Sigma }^n$,其初态为 $x_{\mathrm{in}}={\iota }_n(w)$。由 $T_L(n)$ 的定义,对该 $w$ 至少存在一条路径

$${\gamma }_w:x_{\mathrm{in}}\to x_{\mathrm{acc}}(w)\in A_L,$$

使得 $\mathsf{C}({\gamma }_w)\le T_L(n)$。

从一个固定的基点 $x_0$ 出发,假设初始编码阶段或预处理阶段的复杂度为有界常数 $C_0$,则存在路径

$$x_0\to x_{\mathrm{in}}\to x_{\mathrm{acc}}(w)$$

其总代价至多为 $C_0+T_L(n)$。因此,所有接受终态 $x_{\mathrm{acc}}(w)$ 都位于复杂性球

$$B_{C_0+T_L(n)}(x_0)$$

内。

由于不同输入 $w$ 的终态不同,接受终态集合包含至少 $|\Sigma {|}^n$ 个互异点,因此

$$V_{x_0}(C_0+T_L(n))\ge |\Sigma {|}^n.$$

若 $V_{x_0}(T)$ 随 $T$ 单调不减,则

$$V_{x_0}(T_L(n))\ge V_{x_0}(C_0+T_L(n))/K,$$

其中 $K$ 为某个常数因子(例如用 $T_L(n)+C_0$ 与 $T_L(n)$ 之间的关系吸收)。于是存在常数 $C_1>0$,使得

$$V_{x_0}(T_L(n))\ge C_1|\Sigma {|}^n.$$

在不追求常数精确性的场合,可写为命题中的形式。

证毕。

A.2 定理 4.2 的证明纲要

定理重述

若存在常数 $C_0,k_0>0$ 使得

$$V_{x_0}(T)\le C_0{T}^{k_0}\text{对充分大}T,$$

且编码–判定机制使得对所有 $n$,所有输入的终态位于 $B_{c{T}_L(n)}(x_0)$ 内且互不混淆,则几何复杂度函数 $T_L(n)$ 必须至少以 $n^{1/k_0}$ 级别增长,不能亚多项式满足信息容量需求。同时,若要求 $T_L(n)$ 不超过某个指数函数,则该指数的底与指数的常数系数被 $k_0$ 所控制。

证明要点

由命题 A.1 的体积–输入数目下界,有

$$V_{x_0}(c{T}_L(n))\ge |\Sigma {|}^n.$$

由体积上界,

$$C_0(c{T}_L(n){)}^{k_0}\ge V_{x_0}(c{T}_L(n)).$$

于是

$$C_0{c}^{k_0}{T}_L(n{)}^{k_0}\ge |\Sigma {|}^n,$$

从而

$$T_L(n)\ge (\frac{|\Sigma {|}^n}{C_0{c}^{k_0}}{)}^{1/k_0}=C^{\prime }|\Sigma {|}^{n/k_0}.$$

这给出了若要不混淆所有 $|\Sigma {|}^n$ 个输入且体积增长仅为 $T^{k_0}$,复杂度半径 $T_L(n)$ 至少呈指数增长的条件。

然而一般语言不需要对所有输入给出不同终态,而只需将成员与非成员区分,这允许将所需“有效终态数目“降低到某个多项式或子指数级别,进而将 $T_L(n)$ 的下界降至多项式级别。

对多数自然编码–判定机制,可以通过对接受区域的结构性假设(例如接受终态在信息流形上呈低维流形),证明 $|\{x_{\mathrm{acc}}(w)\}|$ 对 $w\in {\Sigma }^n$ 至多多项式增长而非指数增长,从而得到

$$V_{x_0}(c{T}_L(n))\ge \mathrm{poly}(n),$$

与体积上界 $V_{x_0}(T)\le C_0{T}^{k_0}$ 结合,得出

$$T_L(n)\ge C_1{n}^{1/k_0},T_L(n)\le C_2{n}^{k_1},$$

即多项式上下界。

严格版本需对“终态压缩“和“语言结构“做出具体假设,本文仅给出几何–信息容量层面的约束骨架。

附录 B:负曲率区域中指数复杂度语言的构造

B.1 负曲率与树状子图嵌入

在离散负曲率空间中,可以嵌入类似正则树的子图:存在 $b>1$ 与常数 $c>0$,使得在某个区域内,可以从基点出发构造一棵度约为 $b$ 的树,每层之间的复杂性距离约为常数 $T_0$,且不同叶子之间的距离至少为某个常数。

这与体积指数增长条件一致:

$$V_{x_0}(n{T}_0)\gtrsim b^n.$$

B.2 指数复杂度语言构造概述

1. 对每个 $n$,取树的深度 $\ell (n)=cn$,叶子数约为 $b^{\ell (n)}=2^{(c\log b)n}$。
2. 将长度为 $n$ 的输入映射到这棵树的叶子(若 $|\Sigma {|}^n\le b^{\ell (n)}$)。
3. 设计判定机制:对语言 $L_{\alpha }$ 给定一个子集 $S_{\alpha }\subset$ 叶子节点集合,成员输入对应路径必须走到 $S_{\alpha }$ 中对应叶子,非成员则走到补集。
4. 由于不同叶子之间的复杂性距离至少为常数,且每个输入必须走到不同叶子以避免混淆,故从基点到叶子的最小复杂性距离为 $\ell (n)T_0=\Theta (n)$,但这只是树深度;为了在体积边缘区域内保证所有路径互不重叠且满足语言结构,还需要额外的“避让“复杂度,综合起来可达到指数级别。

通过对树的参数与编码方式的具体选择,可以构造出几何复杂度函数 $T_{L_{\alpha }}(n)\ge 2^{c_{\alpha }n}$ 的语言族。形式化证明需对路径排斥、体积分配与接受区域结构做精细估计,限于篇幅不再展开。

附录 C:几何复杂度类与传统复杂度类的等价纲要

C.1 模型等价假设

我们采用如下标准假设:

1. 通用确定性图灵机、可逆元胞自动机与可逆 QCA 在多项式时间内互相模拟;
2. 计算宇宙 $U_{\mathrm{comp}}$ 由某个通用模型构造,单步代价与图灵步数之间存在常数因子或多项式重标度;
3. 编码族 $\{{\iota }_n\}$ 为标准编码或其多项式等价变体。

在这些假设下,传统时间复杂度 $T_{\mathrm{TM}}(n)$、电路大小复杂度 $S_{\mathrm{circ}}(n)$ 与几何复杂度函数 $T_L(n)$ 之间存在

$$c_1{T}_{\mathrm{TM}}(n)\le T_L(n)\le c_2{T}_{\mathrm{TM}}(n{)}^k$$

类型的双边多项式不等式,从而复杂度类的包含关系在多项式尺度下保持。

附录 D:BQP 几何上界与 QCA 实现

D.1 门集通用性与 QCA 模拟

标准结果表明:任意多项式大小量子电路都可用 QCA 在多项式步数内模拟,反之亦然。若每个门或局域更新步在统一时间刻度下具有常数代价,则几何复杂度函数 $T_L(n)$ 与电路大小在多项式尺度上等价。

在控制流形 $(\mathcal{M},G)$ 上,每个局域门对应某个控制路径片段,其长度由度量 $G$ 控制,整体路径长度 $L_G[{\theta }_n]$ 与 QCA 步数之间存在线性或多项式关系。因此 BQP 类中的语言其 $T_L(n)$ 与图灵或电路复杂度在多项式意义下相互界定。

本附录的技术细节主要依赖于传统计算复杂性与量子信息的标准结论,本文在几何层面给出的仅是这些结论在计算宇宙框架中的结构翻译与统一。