迭代窄网络：凸输入空间上宽度 4 的图灵完备性与验证的复杂性

我们研究宽度为 4 的固定 ReLU 网络 $N$ 的迭代，即在 $[0,1]^4$ 上的离散时间系统 $x_{k+1} = N(x_k)$。等价地，$x_k$ 是由 $k$ 个 $N$ 副本构成的权重共享网络的输出，或是由 $x_0$ 启动、无外部输入的循环网络的输出。我们证明每台确定性图灵机 $M$ 都对应这样一个网络 $N_M$。该网络可由 $M$ 在多项式时间内构造。每次迭代的深度为 $\mathrm{poly}(|M|)$。$N_M$ 的迭代在每条编码纸带上精确模拟 $M$。迭代次数与 $M$ 的运行时间成正比。此外，第四个坐标不可逆地标记凸立方体 $[0,1]^4$ 中模拟读取到无效数字的每个点。该标记是使硬度归约在凸输入区域（实用验证器的适用域）上成立的关键证书。由于 ReLU 网络固有的连续性障碍，凸区域此前无法触及。这一对应关系有三个推论。第一，迭代宽度为 4 的 ReLU 网络的可达性沿时间界这一单一维度覆盖完整的复杂度层级：一元界下为 NP 完全，二元界下为 NEXP 完全，无界时为 RE 完全（不可判定）。第二，额外增加两个宽度的神经元就足以将硬度扩展到所有常见光滑激活函数：在宽度为 6 时，鲁棒验证问题（具有 $\delta/2\delta$ 间隙的承诺问题）对 $\tanh$、sigmoid、GELU、Swish、ELU 以及任何多项式时间可计算、具有多项式时间可计算 Lipschitz 常数的连续非多项式激活函数均为 NP 完全。第三，整个谱系可迁移到维度为 5 的离散化 Neural ODE。

中文由 AI 翻译，仅供参考，以原文为准。