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

陈蔚骏 等: 向量加法系统可达性问题复杂性下界研究综述 27

用 P d 时可以使用具体的数值替代, 则有如下定理.
定理 12 [37] . 当 d ⩾ 3 时, (2d + 3)-VASS 可达性问题是 F d -难的.
此定理虽然相较于定理 11 并无本质上的提升, 但给我们如下启发.
1) 在构造 F d (n)-放大器时, 基于快速增加的向量编码的构造方法与基于递归的构造方法很可能互相等价. 在
没有提出全新构造方案的情况下, 后续研究者可以自由选择其一进行深入, 而没必要从二者的角度都进行思考.
2) 不变量的形式是关键的. 为了构造使用更少计数器的 F d (n)-放大器, 我们很可能需要寄希望于寻找一些合
适的不变量, 至少不应局限于目前已有的乘法与指数形式.

4 固定维 VASS 的现有下界

本节主要介绍固定维 VASS 的最新研究进展. 与第 2 节相比, 本节的研究对象大都是尚未定论的开放问题, 值
得后续研究者深入探索. 同时在 d-VASS 可达性问题下界的研究中, 1–2 个的计数器差异往往不会对结果造成本
质上的差异, 但在低维 VASS 的可达性问题中并非如此, 因此人们需要更加注重归约的细节. 另外, 基于乘法三元
组和放大器的证明框架需要 3 个向量充当三元组、至少两个向量用于模拟计数器机器的行为, 难以得到 5 维以下
的相关结果. 因此到目前为止, 除了第 2 节介绍的关于 1 维 VASS 和 2 维 VASS 的完备性结论外, 3 维–8 维 VASS
的可达性问题仅有一些难 (hardness) 结论 [39] . 表 3 总结了最新结论.

表 3 固定维 VASS 可达性问题相关结论

维度 3 4 5 6 7 ⩾ 8
一进制编码 NL-难 NP-难 PSPACE-难
Tower-难
二进制编码 PSPACE-难 EXPSPACE-难

表 3 中大部分结果都是继承自更低维的 VASS, 真正非平凡的结论主要有 4 条, 以下我们分节介绍.
4.1 一进制编码下 4-VASS 的 NP-难归约
我们可以将一进制程序理解为只使用 x ± = d 形式语句的程序, 其中, d 是一个与输入无关常量. 图 3 给出的

a 形式的程序, 因此不能直接推广到一进制 1-VASS 上. 但如果允许程序使用更多计数器, 我们则
归约使用了 x +=
可以等价实现该功能. 本节的核心是用 3 个额外的维度来实现二进制到一进制的转换.
∑
k
k
a = a k 2 , 现考虑下面带测零的计数器机器 inc( , a
给定二进制表示 x a), 该机器使用了辅助计数器 y,z, 将
i=0
y
逐位累加到计数器 y 上, 随后再将 转移到 x 上, 从而实现了 x += a. 同理, 若将最后一个循环更改为“loop x −=1,
y −=1;”, 则可以得到 dec( x,a).
给定子集和问题实例 ⟨{a 1 ,...,a n },c⟩, 可以高效归约到图 20 中的 3-计数器机器 P, 其正确性同引理 5. 最后, 为
了得到 VASS 相关结论, 我们需要去掉程序 P 中的测零 (来自模块 multiply). 令 k m = max|a i | 表示这些数在二进制
′
i∈[n]
下的最大长度, 则 inc 或 dec 至多使用 2k m −1 次测零, P 至多使用 (2k m −1)(n+1) 次测零, 整体上与输入规模成多
′
项式关系, 只需利用第 3.2.2.1 节介绍的控制计数器方法即可解决. 更具体地说, P 中待测零计数器包括 z, y, 我们
′
y
需要引入控制计数器 t, 以 为例, 每次进行操作 y 进行多少次测零, 不
y ± = d 时, 我们修改考察剩余程序中还需对
c ± = dm. 最终得到计数器程序
妨设为 m 次, 则需同时令 P, 其长度是 n 和 k m 的多项式, 且 P 有 0-执行当且仅当
⟨{a 1 ,...,a n },c⟩ ∈ subset sum.

y += a ; k
loop y -=1, z +=2; for i := k − 1 to 0 for i := 1 to n
do inc ( x, a );
zero? y ; multiply ( , ;2y z ); or skip ; i
loop z -=1, y +=1; y += a ;
i dec ( ,x c );
zero? z ; loop x +=1, y -=1;
halt;
zero? y ;
multiply (y, z; k) inc (x, a) P′
图 20 从子集和问题到 3-计数器机器的归约