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

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

引理 12. 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 -难的.
证明: 与引理 10、推论 2 同理, 只需将归约问题改为计数器机器 F d (n)/2-时间可达性问题, 并对调模拟和结束
;
a、b 的角色: x+y+a = A b 用于记录测零次数, 每次减 2.
阶段中三元组内 a 用于维持不变量
为了解决三元组只能进行 B/2 次测零, 但 P ′ 中却需要进行 ⩾ B 次测零的问题, Czerwiński 等人 [36] 使用了快速增
k+1
长函数的另一等价定义 (等价性证明见原文): F 1 (n) = 2n 以及 k ⩾ 1 时 F k+1 (n) = F (n/4) (4). 最终得到一族 F d : N 4 →
k
N 4 , 这里, N 4 表示 4 的自然数倍数. 函数族的定义域限制并不影响引理 12 的正确性, 因为将 n 替换成为稍大的 N 4
中的数是容易的. 本节后续证明中仅考虑满足 B ∈ N 4 的乘法三元组. 同时, 为了减少 Z k 中的计数器数量, 我们必须
′
′
′
从 Z 1 开始优化. 定义计数器程序 P 1 (a ,b ,c ,a,b,c;l) 如图 11 所示.

k b′ +=4;
loop a′ +=1, k c′ +=4;
k
loop
loop a′ -=1, a +=1, c′ -=1, c += l ; loop k P ; zero-test ( c′ )
loop a′ +=1, a -=1, c′ -=1, c += l ; , , ,b c a′ ′ k )
, , ;1b c′
b′ -=2, b += 2l ; 1 P (a k k k k k k
zero-test ( c )
loop a′ -=2, a +=2, c′ -=2, c += 2l ; k P ; zero-test ( c′ )
k
b′ -=2, b += 2l ; k
loop a + ′ -=1, k c + ′ 1 -=2;
k 1
zero-test ( a + ′ )
k 1
P 1 (a′, b′, c′, a, b, c: l) P k+1
图 11 优化后的 F d (n)-放大器

′ ′ ′ l = 2 时即可得到一个 ( ( ′ ′ ′ ) { })
′
设 X = {a,b,c,a ,b ,c }, 容易验证 F 1 (n)-放大器 Ampl 1 = P 1 ,X 1 , a ,b ,c ,(a 1 ,b 1 ,c 1 ), c ,
1 1 1 1
}
(
)
{
其中, P 1 = P 1 a ,b ,c ,a,b,c;2 , X 1 = a 1 ,b 1 ,c 1 ,a ,b ,c .
′
′
′
′
′
′
1 1 1 1
)
假设我们已经得到了一个 F k (n)-放大器 Ampl k = P k ,X k , a ,b ,c ,(a k ,b k ,c k ),Z k , 其中, Z k = c , 构造 P k+1 如
{ }
(
(
)
′
′
′
′
k
k
k
k
图 11 a ′ , b ′ , c ′ 构成的三元组模拟, 需要对其中的加法语句进行适当的互补操作, 此
所示. 程序中的测零使用
k+1 k+1 k+1
{ } { }
处隐去了这些操作. 令 X k+1 = X k ∪ a ′ ,b ′ ,c ′ , Z k+1 = c ′ .
k+1 k+1 k+1 k+1
( )
τ s = a ′ ,b ′ ,c ′ τ s 出发的 X k 上, 第 1
● 假设初始格局为 k+1 k+1 k+1 ,A s ,B,X k+1 , 将任意从 Z k + 1 -执行限制在计数器集合
(
)
个 loop τ 0 = a ,b ,c ,A 0 ,4,X k . 第 2 个 loop c 的模拟测零保证了该执行对应
′
′
′
′
A 1 构造了三元组
语句对某个
k k k 语句对 k
P k 的一次 Z k -执行, 因此将 τ 0 放大到了 τ = (a k ,b k ,c k ,A 1 ,F k (4),X k ), 其中, A 1 是某个自然数; 对 c k 的模拟测零保证了
′
0
( ′ ′ ′ ) ( ′ ′ ′ )
该执行对应 P 1 a k ,b k ,c k ,a ,b ,c ;1 的一次{c k }-执行, 得到 τ 1 = a ,b ,c ,A 1 ,F k (4),X k . 由于 B = 0 (mod 4), 乘法三元
k
k
k
k
τ s 保证一次 τ t = (a k ,b k ,c k ,
组 Z k + 1 -执行中恰好能够进行 B/2 次模拟测零, 从而 P k 可以循环执行 B/4 次, 最终得到
)
A B/4 ,F (B/4) (4),X k+1 .
k
● 若给定 A ∈ N , 其中, B ∈ N 4 , 借用 Ampl k 的性质不断倒推可知: 存在 A s ∈ N , 使得 P k+1 能从 τ s = (a ′ k+1 ,
b ′ ,c ′ ,A s ,B,X k+1 ) Z k + 1 -计算出某个 τ t = (a k ,b k ,c k ,A,F k+1 (B),X k+1 ) 使得 A t ⩾ A .
k+1 k+1
(
)
(
综上, Ampl k+1 = P k+1 ,X k+1 , a ′ k+1 ,b ′ k+1 ,c ′ k+1 ) ,(a k ,b k ,c k ),Z k+1 是一个 F k + 1 (n)-放大器. 由构造过程可知: |X d | = 3d+
,
3 |Z d | = 1, 程序长度为 2 O(d) , 从而有如下引理.
(
(
引理 13 [36] . d ⩾ 3 时, 存在一族 F d (n)-放大器 Ampl d = P d ,X d , a ,b ,c ,(a d ,b d ,c d ),Z d 使得其中程序 P d 长度为
)
)
′
′
′
d d d
,
2 O(d) , |X d | = 3d +3 |Z d | = 1.
′
′
当 d ⩾ 3 时, D = max(|X d |,2+|{a d ,b d ,c d }∪Z d |) = max(3d +3,4) = 3d +3. 注意, b 只会减少, 因此在图 7 的 P 中
d
′ O(d) . 因此有如下定理.
可以使用 n, n−1,..., 0 替换每次 b 的出现, 从而减少一个计数器, 代价是程序长度变为 n2
d
定理 9 [36] . d ⩾ 3 时, (3d + 2)-VASS 可达性问题是 F d -难的.
相较于定理 8, 这是一个更好的下界. 事实上, 在不复用任何一组三元组中的计数器的情况下, 计数器数量必
然有 3d +Ω(1) 的下界, 此方法已经几乎对应此时的最优下界了.
3.4 快速增长函数的向量编码
本节介绍 F d (n)-放大器的构造路线 2: Leroux [15,30] 的基于向量编码的构造方法. 与第 3.3 节中阐述的思路不同,
2021 年 Leroux [15] 在构造 F d (n)-放大器的过程中巧妙地使用向量对一般形式的快速增长函数进行编码, 同时用程序