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

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

定理 14 [39] . 一进制编码下 5-VASS 可达性问题是 PSPACE-难的.
4.3 二进制编码下 6-VASS 的 EXPSPACE-难归约
2 n
根据引理 2, 我们考虑给出 2 - 有界计数器机器可达性问题到 6-VASS 可达性问题的归约. 给定使用 3 个计数
2 n
)
(
2 n
器的 2 2 n 有界计数器机器 M, 其测零次数不超过 3s4 , 只需构造出平方二元组 τ = b,c,6s4 ,X . 虽然此形式与第
n
4.2 节形式相似, 但 B = 6s4 2 n 需要从 6s 出发做 2 次乘法, 不能直接采用上面的方法, 否则会构造出一个指数长的
程序. 如果转而将 for 语句替换成普通的 loop, 则需要设法保证该循环恰好执行 2 次. 注意, 每次循环会进行 4 次
n
n
测零, 因此只需保证进行 4×2 次测零即可. 这可以通过构造三元组实现.
如图 22 所示, 在 P 中, 我们构造了三元组 τ = (a ,b ,c ,A,8×2 +2,X), 并在得到 τ 后执行了 P , 即将 P τ 中所
′
n
′
′
′
′
′
τ
′ τ. 最终我们希望复用 , 因此对其进行了一次模拟
′
有测零使用三元组 τ 模拟, 最终可以{c'}-计算出需要的二元组 a
′ n n X = {a ,b ,c ,b,c,d} 共使用 6 个计数器, 注
′
′
′
测零, 这也是 τ 测零次数为 4×2 +1 而非恰好 4×2 的原因. 整个程序中
意, a 、b 、d 均可以复用. 可得到如下定理.
′
′

n
b += 6s , c += 36s ; 2 b′ += 8 × 2 + 2
n
loop loop a′ +=1 c′ += 8 × 2 + 2;
,
multiply ( , ,4b d ) ; ′ P τ
multiply ( , ,4c d ) ; zero-test ( a′ )
P τ P
( 2 n )
图 22 构造平方二元组 τ = b,c,6s4 ,X

定理 15 [39] . 二进制编码下 6-VASS 可达性问题是 EXPSPACE-难的.
4.4 一进制编码下 8-VASS 的 Tower-难归约
证明 Tower-难的核心在于构造一个 F 3 -放大器, 在第 3 节介绍的结论中, 给出的最好构造方法需要使用
2d +3 = 9 个计数器, 注意到该方法是从 F 1 -放大器开始递归构造的, 但事实上直接构造 F 2 -放大器并不困难, 并且
借此可以减少一次递推, 从而省去一个计数器. 图 23 中的程序 P 2 给出了一个 F 2 -放大器 Ampl 2 = (P 2 ,X 2 ,(a ,b ,c ),
′
′
′
,
(a,b,c),Z 2 ), 其中, X 2 = {a ,b ,c ,a,b,c,d} Z 2 = {a ,c }.
′
′
′
′
′

b′ +=1
loop a′ +=1, c′ +=1;
b +=1 , a′ -=1;
loop a +=1, c +=1, c′ -=1; for i := 1 to n
2 P ;
loop
multiply ( , ,2b d 8 ) ; zero? a′, c′;
loop a -=1 a′ +=1;
,
multiply ( , ,2c d 8 ) ; loop b -=1 b′ +=1;,
loop a′ -=1;
loop c -=1 c′ +=1;,
zero? a, b, c;
P 2 P′ 3
图 23 构造 Ampl 3

τ s = (a ,b ,c ,A s ,B,X 2 ) 出发, 循环中 multiply 内的 4 B/8
′
′
′
若该程序从 次测零均使用 τ s 模拟, 则一共可以进行
)
(
次循环, 因此最终可以 Z 2 -计算出 τ t = a,b,c,A t ,2 ,X 2 . 基于 P 2 可以进一步构造出计数器机器 P , 该程序一进制编
B
′
3
t
码为 O(n) 长, 且只需进行 5n 次测零. 设引入 并使用控制计数器方法变换后的程序为 P 3 , 我们高效构造出了一个
一进制编码、8 计数器的 F 3 (n)-生成器 Gen 3 = {X 2 ∪{t},P 3 ,(a ,b ,c ),Z 2 ∪{c}}. 根据推论 2 有如下定理.
′
′
′
定理 16 [39] . 一进制编码下 8-VASS 可达性问题是 Tower-难的.
F 3 以上的情形. 直观
本节有一个细节问题, 即为何此处放弃了平方二元组思想, 以及平方二元组能否推广到
上, 三元组使用 A 限制计数器的值, B 限制计数器的测零次数, 二元组中用 B 同时限制这二者, 因此少使用了一个
计数器. 但前者 A、B 不必相同, 从而对待测零计数器的限制较少; 使用二元组则要求该计数器的值和测零次数都
B/2, 这导致了二元组无法使用 P 构造出
不能超过 f(n)-放大器构造: 若给定 τ s = (b,c,B,X), 我们希望通过一个程序
′ ′ f (B) ⩽ B, 但这样的放大器是平
τ t = (b ,c, f (B),X), 则此过程中需要有 b ⩽ B, 否则无法使用 τ s 模拟测零; 从而有
凡的.