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

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

f (n) 构造计数器尽可能少的 f(n)-放
这使得在后续的证明中, 我们无须再关注繁琐的模拟步骤, 只需对给定的
f (n) = tower(n) 的情形, Czerwiński 等人 [35] 构造出了一族 n 呈线性关系,
大器即可. 对于 tower(n)-放大器, 但 |X n | 和
.
}
因此只能证明一般 VASS 可达性问题是 Tower-难的. 但如果考虑 f k (n) = k-exp(n) = 2 . . 2 n k times 且固定 k, 他们
实际上构造了一族一致 (计数器集合 X 与 n 无关) 的 k-exp(n)-放大器. 和引理 2 同理可证, 计数器机器 (k +1)-exp(n)-
可达性问题是 k-EXPSPACE-难的, 最终有如下定理.
定理 7 [35] . (k + 13)-VASS 可达性问题是 k-EXPSPACE-难的.
但文献 [35] 的构造方式过于繁琐, 且在最新技术下完全可以使用常数个计数器完成 [37] , 因此我们认为其技术
参考价值不大, 故省略证明细节.
3.2.3 d-VASS 相关非初等下界总览
由于一般 VASS 可达性问题下界是非初等的, 上界甚至是非原始递归的, 我们有理由相信 F d -难问题可以归约
到某个维度的 VASS 上. 根据引理 10 和推论 1, 有如下推论.
推论 2. d ⩾ 3 时, 若存在一族 F d (n)-放大器 Ampl d = (P d ,X d ,(a ,b ,c ),(a,b,c),Z d ) 使得程序 P d 的长度为 p(n) ∈
′
′
′
F <d , 令 D = max(|X d |,2+|{a,b,c}∪Z d |), 则 D-VASS 可达性问题是 F d -难的.
D 的计算, 其他和引理 10 X d 中的计数器可分为 3 类: 输出
证明: 只需给出 同理. 事实上, 在初始化阶段结束后
a, b, c; 控制计数器 Z d ; 剩余的 |X d |−|{a,b,c}∪Z d | 个可复用计数器. 模拟阶段的两个计数器完全可以从可复用计数
器里选择 (如有), 因此整体只需 D = |X d |+max(0,2−|X d |+|{a,b,c}∪Z d |) 个计数器. 证毕.
若能构造一族 F d (n)-放大器 Ampl d = (P d ,X d ,(a ,b ,c ),(a,b,c),Z d ) 并考察其计数器的个数 |X d |, 根据上述推论
′
′
′
便可得到 d-VASS 可达性问题的相关下界. 当然, 后续研究证明这是可以做到的, 同时人们还探讨了使得 D(d)-VASS
可达性是 F d -难的函数 D(d) 的形式. 显然 D(d) 增长速度越慢, 对应的下界与上界越接近, 目前最新研究成果已将
此优化为线性函数的形式, 相关结论可以总结如图 8 所示. 此图中的箭头表示技术之间的依赖关系. 总体而言,
F d (n)-放大器构造技术可以分为两条路线.
路线 1. Czerwiński 等人基于递归的构造方法.
路线 2. Leroux 的基于向量编码的构造方法.

6d-VASS (3d+2)-VASS
路线1 Czerwiński等人 [14] Czerwiński等人 [36]

(2d+3)-VASS
Czerwiński等人 [37]

(4d+5)-VASS (2d+4)-VASS
路线2
Leroux [15] Leroux [38]
图 8 d-VASS 可达性问题复杂性下界

目前最好的构造集两者所长, 最终证明了 (2d + 3)-VASS 可达性是 F d -难的. 我们将在第 3.3 和 3.4 节分别介
绍这两条技术路线, 并在第 3.5 节给出最优下界的证明方法.
F d (n) -放大器
3.3 递归构造
Czerwiński 等人 [14] 和 Leroux [15] 的思路是根据 F d (n) 的定义式 (3)、(4) 递归地构造出 F d (n)-放大器. 但为了方
(n)
便构造, 可以考虑重新定义 F 1 (n) = 2n 以及当 k ⩾ 1 时 F k+1 (n) = F (1), 这样得到的一族新的快速增长函数 {F d (n)} d∈N
k
和前文中的定义在量级上是一致的. 更具体地说, 构造过程有以下两步.
1) 构造一个 F 1 (n)-放大器 Ampl 1 .
2) 假设已经得到了 F k (n)-放大器 Ampl k , 通过 Ampl k 构造出 Ampl k+1 .
根据数学归纳法可知, 只要完成上述两步, 即可构造出一族 F d (n)-放大器 {Ampl d } d∈N .