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

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

是 |Q|+4|δ|, 迁移规则有 5|δ| 条, 总体是一个线性的放大. 因此二者可对数空间互相归约, 故有以下引理.
引理 6 [24] . 1-BCA reachability⩽ L 2-VASS reachability.
证明: 给定 1-BCA 可达性实例 ⟨M = (Q,b,δ), p s , p t ⟩, 由上述讨论知 δ 可以直接定义为 Q×Z× Q 的有限子集. 构
(p,a,q)
2 -VASS ⟨V = (2,Q,T), p s (0,b), p t (0,b)⟩, 其中, T = {(p,(a,−a),q) : (p,a,q) ∈ δ}. 显然, p(x)−−−−→ M q(y)
造 可达性实例
(p,(a,−a),q)
p(x,b− x)−−−−−−−→ V q(y,b−y), 如果原问题实例是可达的, 对该可达的证据逐步应用这一观察即可知有
当且仅当
p s (0,b)→ V p t (0,b). 反之, 若 p s (0,b)→ V p t (0,b), 将每一步向量投影到第 1 维即可得到 p s (0)→ M p t (0). 若两问题采
用的编码方案相同, 此归约可在对数空间完成. 证毕.
2.2.3.2 计数器栈自动机
计数器栈自动机是一个 3-元组 M = (Q,d,δ), 其中, Q 是有限状态集, d ∈ N 是计数器数量, δ 是有限迁移规则
t
d
,
集. M 的格局形如 p(u) ∈ Q×N , 迁移规则形如 t = (p,E, I,R,q) ∈ δ. 给定格局 p(u), q(v) p(u)→ M q(v) 当且仅当下
述条件成立.
● E : [d] → N 是偏函数, 指定了对某些维度的测量, 对于每个 i ∈ dom(E) 都有 u(i) = E (i); 若 E ( j) 有定义, 则对
,
任意 j ⩽ i ⩽ d E (i) 也有定义.
● R ⊆ dom(E) 指定了需要置为 0 的计数器, 对于每个 i ∈ R 都有 v(i) = 0.
d
● I ∈ N 指定了 d 个计数器的增量, 对于每个 i < R 都有 v(i) = u(i)+ I(i).
上述规则本质上是为了模拟 1-BCA 的行为. 事实上, 给定 d 个计数器构成的栈 u, 可以选择一个充分大的 k 按
∑ d
i−1
照 k 进制用单个计数器记录下 C (u) = u(i)k . 图 4 以 k = 16, d = 3 为例展示了这一编码过程的直观解释.
i=1

C= 1 0 1 0 0 1 1 0 1 0 1 0
C 3 C 2 C 1
图 4 CSA 的直观解释

t
给定规则 t = (p,E, I,R,q), 若 p(u) → q(v) 成立, 易知 dom(E) 一定形如 { j, j+1,...,d}, 定义:

∑
i−1
lb = E (i)k , ub = lb+k j−1 −1 (8)
j⩽i⩽d
∑ ∑ ∑ ∑
则一定有 lb ⩽ C (u) = E (i)k i−1 + c i k i−1 ⩽ ub. 令 a = I(i)k i−1 − E (i)k i−1 , 则有 C (u)+a = C (v).
j⩽i⩽d i∈[j−1] i<R i∈R
(p,a,lb,ub,q)
最终可知, 可用 1-BCA 中的迁移 p(C (u)) −−−−−−−→ q(C (v)) 模拟原 CSA 中的迁移. 对所有 t ∈ δ 构造对应的迁移构
d
′ B = k , 我们可以得到一个 1-BCA ′ ′ k 的选取十分重要, 否则计数器栈
成集合 δ , 并令 M = (Q,B,δ ). 需要注意的是,
有上溢的风险, 导致编码不是一一对应的. 因此, 在归约中我们仅考虑一类特殊的 CSA, 它运行中任意可达的格局
,
p(u) 都满足对任意 i ∈ [d] u(i) ⩽ b, 此性质称为 b-安全的 (b-safe). 这样只需在上述证明中取 k = b 即可保证这样
的 CSA 都能够被 M 模拟. M 的构造过程可在对数空间完成, 即有如下引理.
′
′
引理 7 [24] . b-Safe CSA reachability⩽ L 1-BCA reachability.
综合引理 1、引理 6、引理 7, 为了证明 2-VASS 可达性问题是 PSPACE-难的, 还需证明下述引理.
引理 8 [24] . subset sum game⩽ L b-Safe CSA reachability.
证明: 这里使用 CSA 的程序表示, 我们在计数器程序中额外引入形如“assert x A reset x;”的断言语句, 表示
=
A 1 , B 1 , E 1 ,
若计数器 x 值为常量 A 则把 x 置零, 否则终止该次执行, reset 动作也可省略不做. 给定子集和博弈问题实例
F 1 ,..., A n , B n , E n , F n , C, 我们需要遍历博弈中 x i (i ∈ [n]) 的所有可能取值, 随后判定是否存在对应的一组 y i 满足
∑ n
c
(x i +y i ) = C. 为此我们可以使用一组计数器 a i , b i , e i , f i (i ∈ [n]) 记录遍历过程中选择的分支, 用于累加选择
i=1
的数, 即构造下面形式的语句.
∀play = do a i +=1, c += ; or b i +=1, c += ;
A i
B i
i
∃play = do e i +=1, c += ; or f i +=1, c += ;
i E i F i
最终博弈阶段的程序如图 5 中的 P play 所示.