Page 33 - 《软件学报》2026年第1期

30 软件学报 2026 年第 37 卷第 1 期

4.5 固定维平坦 VASS
所谓平坦 VASS, 是指那些迁移函数无法构成嵌套环的 VASS. 这是一个很强的性质, 因此对平坦 VASS 的研
究相对简单, 并且有机会对一般 VASS 的研究带来启发. 目前相关的结论可以总结如表 4 所示.

表 4 平坦 VASS 可达性问题相关结论

维度 ⩽ 2 3 ⩾ 4
一进制编码 NL-完备 [21] NL-难 NP-完备 [39]
二进制编码 NP-完备 [21]

由此可见, 平坦 VASS 可达性问题的复杂性仅剩下唯一一块“拼图”: 一进制编码下 3-VASS 可达性问题究竟
应当如何刻画? 已知它是 NL-难的, 并且在 NP 内, 这几乎是所有 VASS 可达性问题中, 已知上界与下界最为接近
的一种情形. 在更高维的情形下, 平坦 d-VASS 是一个严格简单于普通 d-VASS 的模型, 我们有如下猜想.
猜想 1. 一进制编码下平坦 3-VASS 可达性问题是 NP-完备的.
此外, 一进制编码下固定维 VASS 可覆盖性问题是 NL-完备的; 二进制编码下固定维 VASS 可覆盖性问题在
NP 中, 暂时不能证明其严格比可达性问题简单 [42] .
4.6 短证据
在证明 VASS 可达性问题上界时, 常需要说明若任意两个格局可达, 则一定存在一条对应的“短”证据 π. 同理,
d 0 , 若存在一族 d 0 -VASS Ω( f (n)), 则一定程度上能
给定 实例 {(V n , p n ,q n )} n∈N , 使得 p n (0)→ V q n (0) 的任何证据都是
(
)
够说明 d 0 -VASS 比 SPACE logf (n) 中的问题都难. Czerwiński 等人 [43] 证明了如下命题.
猜想 2 [43] . 存在一族 O(n ) 长、具有 2 2 Ω(n) 长可达证据的二进制 4-VASS 可达性实例 {(V n , p n ,q n )} n∈N .
3
目前最好的相关结论是定理 15: 6-VASS 可达性问题是 EXPSPACE-难的. 根据此命题, 我们有希望将其提升
至 4 维或 5 维. 同一篇文献中还证明了如下猜想.
猜想 3 [43] . 存在一族 O(n ) 长、具有 2 Ω(n) 长可达证据的一进制平坦 3-VASS 可达性实例 {(V n , p n ,q n )} n∈N .
2
这说明我们有希望证明 3 维或 4 维一进制 VASS 可达性问题是 PSPACE-难的. 目前最优结果是定理 14 (仍
然需要 5 个计数器). 第 4.2 节中曾提到过受限于编码方案, 暂无人考虑过将子集和博弈归约到一进制 VASS 上,
但第 4.1 节中关于 NP-难的归约启发我们可以在线地构造出每一个数, 这也是一种未来可以考虑的证明思路.

5 总结与展望

Petri 网凭借其简洁的建模形式和强大的表达能力, 被普遍应用于工程优化和理论分析等诸多领域. 向量加法
系统作为其等价模型, 也相应地受到了学术界的广泛关注. 在前文中, 我们主要从理论研究的角度切入, 综述了向
量加法系统可达性问题复杂性下界的相关模型和概念、最新进展和核心技术. 特别地, 对 d-VASS 可达性问题梳
理了基于三元组和放大器方法的证明框架, 并以此串联起了自 1976 年以来该领域中的重要结论, 揭示了不同研究
者提出的方法之间的联系及演变规律. 接下来, 将根据我们对该问题的深入理解, 给出一系列重要开放的问题, 以
及相关可能的突破方向, 以期为有志研究者提供支持与启发.
1) d-VASS 可达性问题. d-VASS 可达性问题在快速增长函数类中的层级目前还没有精确的刻画, 上界结论表
明该问题复杂性不高于 F d , 下界结论则大致说明其复杂性至少是 F d/2 . 不妨猜想该问题落在 Cd +O(1) 层中, 当下
的主要工作仍在确定 C 的范围, 由定理 12 可知, 1/2 ⩽ C ⩽ 1. 然而上界的工作已很难推进, 下界方面最大的短板则
在于 F d -放大器的构造, 在现有测零技术 (三元组) 下, 递归构造放大器时每次至少增加两个新计数器, 导致人们无
C > 1/2 的结论. 同时, 上文中断言放大器不适用于构造平方二元组, 因此暂时也无法将平方二元组推
法得到任何
广到更高维. 除非未来有研究者能够提出类似平方二元组的方法对模拟测零做出改进, 同时还能配合放大器进行
O(2d) 个计数器所能记录的信息可以使用更少的计数器覆盖, 否
递归构造, 或是提出更简洁的编码形式, 使得目前
则 d-VASS 可达性问题的下界研究仍会处于僵局.