技术摘要：3-VASS 可达性问题属于 EXPSPACE

问题陈述

本文研究了 三维向量加法系统（3-dimensional Vector Addition Systems with States, 3-VASS）的可达性问题。VASS 是一种配备了固定数量计数器（维度）且计数器持有非负整数的有限状态自动机。可达性问题询问是否可以通过一系列有效的转换，从一个源配置（状态和计数器值）到达一个目标配置（状态和计数器值）。

虽然一般的 VASS 可达性问题（其中维度作为输入的一部分）在 2021 年被证明是 ACKERMANN-complete 的，但对于固定维度 $d > 2$ 的确切复杂度仍然是一个核心开放问题。特别针对 3-VASS：

• 下界： 该问题已知是 PSPACE-hard，这继承自二维情况。
• 此前的上界： 在这项工作之前，已知的最佳上界是 2-EXPSPACE（双指数空间），由 Czerwiński 等人（ICALP 2025）建立。在此之前，算法是非初等的（non-elementary）。

本文旨在通过证明 3-VASS 可达性属于 EXPSPACE（单指数空间），来缩小 PSPACE 下界与 2-EXPSPACE 上界之间的差距。

方法论与证明策略

证明的核心是为 3-VASS 中两个配置之间的最短运行路径建立一个 双指数长度界限。如果最短运行长度被限制在 $N^{2^{poly(k)}}$ 内（其中 $N$ 是输入规模，$k$ 是强连通分量的数量），那么可以通过非确定性地猜测一条该长度的路径，在 EXPSPACE 内判定可达性。

作者采用了 层次化归约策略 和 关注点分离（separation-of-concerns） 证明技术，将 3-VASS 实例类细分为一系列子类。这种方法避免了导致以往工作中出现三指数界限的“嵌套”归纳。

1. VASS 的层次化分类

论文定义了一个按生成性递增排序的 3-VASS 子类层次结构：
$$\text{DiagVASS}_3 \subsetneq \text{Semi-diagVASS}_3 \subsetneq \text{PumpVASS}_3 \subsetneq \text{Semi-pumpVASS}_3 \subsetneq \text{SeqVASS}_3$$

• DiagVASS： 前向和后向都存在“对角线”循环（即可以正向泵送所有计数器的循环）的实例。
• PumpVASS： 前向和后向都存在“可泵送”循环（即可以正向泵送至少一个计数器的循环）的实例。
• SeqVASS： 通用的顺序 VASS，其运行过程经过由桥接连接的一系列强连通分量（SCCs）。

证明过程通过为最受限的类别（DiagVASS）建立长度界限，然后使用 长度控制的自归约（length-controlled self-reductions） 将这些界限传递给更一般的类别。

2. 关键技术组件

A. 高效表示可达集（几何 2D VASS）

一个关键工具是对 几何 2 维 VASS 的分析，在这种系统中，所有的运行都保持在两个平行的 2D 平面之间。作者扩展了 Czerwiński 等人的结果，证明即使从“混合集”（一个基础向量加上一个受限的周期集）开始，此类系统的可达集也可以表示为具有多项式大小描述的 混合集 的有限并集。这使得高效地操纵可达集成为可能，而不会导致表示规模的指数级膨胀。

B. 处理非宽对角实例（Non-Wide Diagonal Instances）

对于 DiagVASS，作者区分了“宽”（wide）和“非宽”（non-wide）实例。

• 宽： 系统的顺序锥（sequential cone）包含所有正向量。这些实例通过归约为已知结果来处理。
• 非宽： 作者证明，在非宽对角实例中，运行的前缀和后缀的顺序锥被一个超平面分隔。这种几何上的分离意味着中间组件中的计数器值被约束在一对平行的 2D 平面内。因此，该问题可以转化为一系列几何 2 维 VASS 实例，从而应用上述高效表示技术来推导出双指数界限。

C. 长度控制的自归约

为了从 PumpVASS 和 SeqVASS 转向 DiagVASS，论文引入了 长度控制的自归约。

• 提取联合对角性： 对于一个可泵送（pumpable）实例，作者表明可以提取出一个“联合对角”（jointly diagonal）前缀（即一组共同泵送所有计数器的循环序列）。
• 归约： 该前缀用于构造一个新的具有更少组件（或更简单结构）且为对角的 VASS 实例。这个新实例的大小受目标类别的长度函数控制。
• 避免嵌套： 与以往嵌套长度界限函数（例如 $h_k(h_{k-1}(\dots))$）的方法不同，这种方法确保长度界限仅在递归式的右侧出现一次。这种结构性的改变将复杂度从 2-EXPSPACE 降低到了 EXPSPACE。

主要贡献与结果

1. 主定理： 3-VASS 可达性问题属于 EXPSPACE。

   • 这对一元和二进制编码的输入均成立。
   • 证明依赖于显示对于任何 $k$ 组件的 3-VASS，最短运行的长度被限制在 $size(V, s, t)^{2^{poly(k)}}$ 内。

2. 精细化的复杂度图谱： 论文对 3-VASS 子类的复杂度进行了详细分析：

   • DiagVASS3： 被证明属于 EXPSPACE（改进了之前的 2-EXPSPACE 界限）。
   • PumpVASS3： 被证明允许双指数长度的运行。
   • SeqVASS3： 通过向 PumpVASS 的自归约，被证明允许双指数长度的运行。

3. 方法论进步： 论文引入了 层次化泵送分析 和 关注点分离 策略。通过将问题分解为几何 2D 子问题，并使用尊重组件层次结构的自归约，作者消除了以往归纳证明中固有的三指数增长。

意义与主张

该论文声称显著推进了对 3-VASS 可达性问题理解的进程，这是一个理论计算机科学领域长期存在的挑战。

• 收紧界限： 该结果将 3-VASS 的复杂度差距从双指数上界缩小到了单指数上界。虽然下界仍为 PSPACE，但作者指出，从一般 3-VASS 到可泵送 3-VASS 的归约可能无法在多项式空间内完成，这表明 3-VASS 确实可能是 EXPSPACE-hard 的。
• 为未来工作奠定基础： 论文明确指出，确定 确切 复杂度（PSPACE vs. EXPSPACE）仍然是一个开放问题。它强调，若要给出确定性的 EXPSPACE-hardness 证明，需要找到一个允许双指数最短运行的 3-VASS 实例，而目前尚不清楚是否存在这样的实例。
• 对更高维度的影响： 作者建议，他们关于限制最短运行的方法对于分析维度 $d \ge 4$ 的 VASS 可能是有益的，因为在这些维度中，目前的上界距离初等界限还非常遥远。

总之，本文提供了一个严谨的证明，证明 3-VASS 可达性问题是可以在指数空间内求解的，它利用了结合几何分离论证、高效可达集表示以及精细自归约框架的新颖方法，避免了以往方法中的复杂度膨胀。