技术摘要：迈向双重高效的 IP = PSPACE

1. 问题陈述

本文旨在为 PSPACE 中的语言构建双重高效交互式证明（IP）系统。在这些系统中，证明者（拥有解决问题的计算能力）和验证者（计算资源有限）通过交互来使验证者相信某个计算过程的正确性。

其核心挑战在于实现针对运行时间为 $T(n)$ 且空间复杂度为 $S(n)$ 的计算，使得：

• 证明者的运行时间是计算时间的多项式，即 $\text{poly}(T(n))$。
• 验证者的运行时间显著低于 $T(n)$，理想情况下是输入规模 $n$ 的多项式（或者是 $S$ 的多项式与 $T$ 的亚线性函数的乘积）。

在此项工作之前，已知的双重高效 IP 最优区间覆盖了时间复杂度为 $T(n) = n^{O(\sqrt{\log n / \log \log n})}$ 的情况（由 Berger, Goyal, Hong, 和 Kalai, 2025 建立）。本研究的目标是将这一区间扩展到 $T(n) = n^{O(\log n)}$，从而覆盖更广泛的 PSPACE 计算类。

2. 方法论

作者提出了一种双重高效 IP 的直接构造方法，这与以往工作（RRR16, BGHK25）中使用的间接“黑盒”方法不同。以往的方法首先为*无歧义（unambiguous）*交互式证明构建批处理（batch）交互式证明，然后将其作为子程序使用。作者认为这种间接路径面临障碍（特别是需要一个“速率-1”的批处理 IP），且在概念上过于复杂。

相反，本文构建了一个能够直接对确定性时间-空间受限（TISP）计算进行批处理的协议。其核心方法论是一个名为 Batch($t, k$) 的递归协议，用于验证 $k$ 个时间为 $t$ 的陈述。

关键技术组件

1. 中点扩展与矩阵表示（Midpoint Expansion and Matrix Representation）：
   为了降低验证时间 $t$，证明者为 $k$ 条计算路径中的每一条发送 $\lambda$ 个中间配置（中点）。这些配置被排列成一个 $k \times \lambda$ 的矩阵 $M$，其中每一行代表一条计算路径的配置序列。这通过将 $k$ 个时间为 $t$ 的陈述转化为 $k \cdot \lambda$ 个时间为 $t/\lambda$ 的陈述，实现了维度的转换。

2. 唯一解码校验和（Unique-Decoding Checksums）：
   为了防止证明者在不被察觉的情况下发送不一致或恶意的中间配置，证明者会发送矩阵 $M$ 列的校验和（$\chi$）。这些校验和源自具有唯一解码半径 $d$ 的线性纠错码（具体为 Reed-Solomon 码）。这确保了如果证明者偏离“真实”见证的行数超过 $d$，校验和将无法匹配。

3. 带有行缩减的交互式邻近证明（Interactive Proof of Proximity with Row Reduction, Row-IPP）：
   该协议利用了一种作用于矩阵的广义交互式邻近证明（IPP）。验证者并不验证整个矩阵 $M$，而是使用 Row-IPP 来检查 $M$ 是否在“行距离”上接近于满足特定低深度谓词 $\Phi_{reduce}$。

   • 谓词 $\Phi_{reduce}$ 检查三个条件：
     1. 矩阵 $M$ 与校验和 $\chi$ 一致。
     2. 由 $M$ 衍生的扩展批处理陈述满足递归主张 $\Psi_{\uparrow}$（来自子协议）。
     3. 矩阵满足辅助谓词 $\Phi$。
   • 如果矩阵远离满足这些条件，Row-IPP 允许验证者采样一个小的行子集 $Q$（大小约为 $k/d$）以及一个低深度谓词 $\Psi_{IPP}$，使得验证者仅需检查子矩阵 $M[Q, :]$。

4. 递归缩减（“双赢”论证）：
   协议在两个维度上递归地缩减问题规模：

   • 缩减时间 ($t$)： 通过扩展中点，每个陈述的时间从 $t$ 降至 $t/\lambda$，但陈述的数量增加到 $k \cdot \lambda$。
   • 缩减批次大小 ($k$)： 通过应用 Row-IPP，陈述的数量从 $k$ 减少到 $k/d$（其中 $d$ 是距离参数），同时时间 $t$ 保持不变。

   递归持续进行，直到时间 $t$ 变得足够小，可以直接使用 GKR 协议（Goldwasser, Kalai, Rothblum, 2015）进行验证，或者批次大小 $k$ 足够小以便进行显式处理。

协议流程 (Batch($t, k$))

1. 校验和： 证明者发送中点矩阵 $M$ 的列校验和。
2. 时间缩减（递归调用 1）： 双方在由 $M$ 衍生的扩展批处理上运行 Batch($t/\lambda, k \cdot \lambda$)。这产生了一个必须对扩展后的陈述成立的谓词 $\Psi_{\uparrow}$。
3. Row-IPP： 双方运行 Row-IPP，以验证 $M$ 接近于以下条件的合取：(a) 与校验和一致，(b) 满足 $\Psi_{\uparrow}$，以及 (c) 满足当前的辅助谓词 $\Phi$。此过程输出一个行子集 $Q$ 和一个谓词 $\Psi_{IPP}$。
4. 批次缩减（递归调用 2）： 双方在与行 $Q$ 对应的缩减陈语句集上运行 Batch($t, k/d$)，验证它们是否满足 $\Psi_{IPP}$。

3. 主要贡献

1. 扩展了双重高效 IP 的区间：
   本文为任何可在多项式空间和时间 $T(n) = n^{O(\log n)}$ 内计算的语言构建了双重高效 IP。

   • 证明者运行时间： $\text{poly}(T)$。
   • 验证者运行时间： $\text{poly}(S, 2^{\sqrt{\log T}})$。
   • 特别地，对于 $T = n^{O(\log n)}$，验证者运行时间为 $\text{poly}(n)$。

2. 直接构造：
   作者提供了对 TISP 计算进行批处理的直接构造，避免了对无歧义交互式证明进行批处理的中间步骤。这简化了证明结构，并消除了对“黑盒”批处理无歧义 IP 的依赖，作者认为这类黑盒方法受到理论障碍的限制（特别是实现速率-1 批处理 IP 的困难）。

3. 简化的分析：
   协议的递归结构使用基于卡特兰数（Catalan numbers）的递归树进行分析。作者证明了通过设置分裂参数 $\lambda = 2^{\sqrt{\log T}}$，可以将验证者的复杂度优化为 $2^{O(\sqrt{\log T})} \cdot \text{poly}(S)$。

4. 结果

主要形式化结果在定理 2（以及针对 $T = n^{O(\log n)}$ 特殊情况的推论 1）中给出：

• 定理： 对于每一个属于 $\text{TISP}(T, S)$ 的语言，存在一个交互式证明，其中：

  • 证明者运行时间为 $\text{poly}(T, S)$。
  • 验证者运行时间为 $2^{O(\sqrt{\log T})} \cdot S^2 \cdot \text{poly}(\sigma, \log S)$，其中 $\sigma$ 是可靠性参数。
  • 通信复杂度为 $2^{O(\sqrt{\log T})} \cdot S \cdot \text{poly}(\sigma, \log S)$。

• 含义： 对于在时间 $T(n) = n^{O(\log n)}$ 内可判定的语言（包括 PSPACE 的很大一部分），验证者运行时间为 $\text{poly}(n)$。

5. 意义与主张

本文声称这项工作相比现有技术水平有了实质性的改进：

• 范围提升： 它将时间复杂度区间从 $T(n) = n^{O(\sqrt{\log n / \log \log n})}$ 扩展到了 $T(n) = n^{O(\log n)}$。
• 概念简化： 直接构造被描述为“显著地更简单”于以往的间接方法。作者认为，以往依赖于黑盒批处理无歧义 IP 的方法遇到了需要“速率-1”批处理 IP（即 $k$ 个陈述的通信成本为单个陈述成本的 $(1+o(1))$ 倍）的障碍。
• 未来潜力： 作者指出，他们的直接构造方法指向了“一个更有前景的改进路径”，暗示通过精炼直接对 TISP 计算进行批处理，而非试图克服黑盒无歧义 IP 方法中固有的障碍，可能会实现进一步的优化。

这项工作依赖于标准的密码学和计算复杂性理论原语（有限域、Reed-Solomon 码、GKR 协议、Row-IPP），但通过一种新颖的递归框架将它们综合起来，以实现所述的效率增益。