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

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

对于 P ′ , 我们引入辅助计数器 t k+1 , 用 i k+1 从 0 到 B−1 记录当且循环的次数. 以 a k 为例, 它一共进行了 B 次测
k+1
零, 第 i 次循环时的 b k −=1 位于第 i k+1 次测零前, 因此需要修改 t k+1 如下: t k+1 −= B−i k+1 , 其他计数器同理. P k 中对 a k
P , 最终可以初步得到图 10
i
等计数器也有增减, 因此也需要在其中对 t k+1 做出调整, 记第 i 次循环中调整后的程序为
k
中没有测零语句的程序 P k+1 .

k b′ +=1, k t + 1 += b + ′ ; 1
k
loop a′ +=1, ' k c +=1, 1 +=2 b + ′ loop
k k t + k 1
loop k b + ′ 1 -=1, k b + ′ 1 +=1, k t + 1 +=1;
k P ; i zero-test ( b + ′ ) 1
k
loop a -=1, k a′ +=1, k t + 1 -=1; loop
k
loop b -=1, k b′ +=1, k t + 1 -=1; k b + ′ 1 +=1, k b + ′ 1 -=1
k
(
loop c -=1, k c′ +=1, k t + 1 -=1; zero-test b + ′ ) 1
k
k
k b + ′ 1 -=1; i + +=1;
1
k
P k+1 t k+1 +=b′ k+1
图 10 基于控制计数器方法完成 Ampl k+1 的构造

i b ′ t k+1 +=
观察可知, 执行 P 时需要引入形如 t k+1 += d(B−i k+1 ) 的修改, 而此时有 的值恰为 B−i k+1 , 只需令
k k+1
db ′ 即可. 事实上, 常量 d 不会超过 2, 因此可以只通过重复 t k+1 += b ′ 操作 d 次实现. 但这显然不是计数器程序允
k+1 k+1
许的语句格式, 需要替换成图 10 右侧的程序片段. 该片段中引入了计数器 b ′ 使得 b ′ +b ′ 之和不变. 当 P k+1 的
k+1 k+1 k+1
( )
初始格局是 τ s = a ′ ,b ′ ,c ′ ,A s ,B,X k+1 时, 因为不变量 b ′ +b ′ +i k+1 = B 始终成立, 符合使用 τ s 模拟测零的前
k+1 k+1 k+1 k+1 k+1
提, 因此 zero-test 可以和图 7 同理实现.
最终我们构造了一个 F k + 1 (n)-放大器 Ampl k+1 = P k+1 ,X k+1 , a ′ ,b ′ ,c ′ ) ( ′ ′ ′ ) )
(
(
, a ,b ,c ,Z k . 其中, 输入计数器是
k+1 k+1 k+1 k k k
{
Ampl k 的输入计数器; Z k+1 = a ′ ,b ′ ,c ′ ,t ′ } X k+1 = X k ∪
一组新的计数器; 输出计数器复用了 k+1 k+1 k+1 k+1 ; 整体上使用了
{ } { }
Z k+1 ∪ i k+1 , b ′ k+1 . P k+1 的 Z k + 1 -执行相当于 P ′ k+1 的 b ′ k+1 - 执行, 此处不再重新论证为何 Ampl k+1 符合 F k + 1 (n)-放大
器的定义. 易知计数器总数符合递推关系式 g(1) = |X 1 | = 6 和当 k ⩾ 1 时 g(k) = |X k | = g(k −1)+6, 解得对任意 d ⩾ 3
都有 g(d) = 6d. 程序的长度大致为 exp(d) 量级, 与 n 无关. 因此我们得到如下引理.
引理 11 [14] d ⩾ 3 时, 存在一族 ( ( ′ ′ ′ ) ) P d 长度
Ampl d = P d ,X d , a ,b ,c ,(a d ,b d ,c d ),Z d 使得其中程序
F d (n)-放大器
. 当
d d d
,
为 2 O(d) , |X d | = 6d |Z d | ⩽ 4.
结合推论 2 知, 当 d ⩾ 3 时, D = max(|X d |,2+|{a d ,b d ,c d }∪Z d |) = max(6d,7) = 6d, 因此有如下定理.
定理 8 [14] . 当 d ⩾ 3 时, (6d)-VASS 可达性问题是 F d -难的.
● 技术局限. 上述方法给出了一般 VASS 可达性问题的 Ackermann 完备性, 其重要性不言而喻. 但从维度的
角度思考, 每当 d 增加 1, 我们便需要引入额外 6 个计数器用于计算, 直观上, 该方法仍有优化空间. 注意, 在使用
放大器时, 我们保证了其初始格局中输入计数器构成乘法三元组, 例如图 9 中的 P ′ k+1 , 其初始格局是某个 τ s =
( )
a ′ ,b ′ ,c ′ ,A s ,B,X k+1 . 但后续程序并未直接应用该三元组模拟测零, 事实上使用 τ s 测零的前提如下.
k+1 k+1 k+1
1) 初始格局中 A s 可以设定得充分大, 使之能够覆盖 P ′ 中测零次数的 2 倍.
k+1
2) 给定计数器上界 B 后, 后续执行所有格局中待测零计数器值之和都不超过 B.
而 P ′ 中待测零的计数器 b k+1 最终会增长到 F k+1 (B) 量级, 不可能满足条件 2). 文献 [14] 中采取的策略是使用
k+1
控制计数器方法将测零转移到一些“小”计数器 b ′ k+1 , b ′ k+1 上, 它们满足 b ′ k+1 +b ′ k+1 ⩽ B, 最终用三元组 τ s 配合 zero-
test 模块即可完成模拟测零, 但代价是引入 3 个额外的控制计数器. 若能够想办法直接使用 τ s 测零而不引入多余
的计数器, 则最终可以将定理 8 的结论优化到 3d 量级.
3.3.2 优化: 测零次数与计数器上界的交换
Czerwiński 等人 [36] 注意到任意三元组 τ s = (a ,b ,c ,A s ,B,X) 中 a , b 的角色完全是对称的, 完全可以将 A s 看作
′
′
′
′
′
计数器值上界, B 用于覆盖测零次数的 2 倍. 观察程序 P ′ , 它一共进行了 7B 次测零, 尽管没有被 B 覆盖, 但已经
k+1
是线性关系, 只需对 P ′ k+1 稍加改进减少测零次数即可; 另一方面待测零计数器的值都是有上界的, 可以通过将 A 设

定得充分大使得所有待测零计数器值之和都不超过 A. 最终一个 f(n)-放大器可以将 τ s 放大为 τ t = (a,b,c, A t , f (B),X).
在这种对乘法三元组新的解释下, τ t 无法用于 f(n)-有界计数器机器的模拟, 因为 f (B) 现在是对测零次数的限制.
我们转而考虑计数器机器 f(n)-时间可达性问题, 有如下引理.