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

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

2.2.2 二进制编码下 1-VASS 可达性问题的 NP-难归约
本节介绍下述引理的证明技巧, 同时解释了为何引理中二进制编码这一条件是必要的.
引理 5 [23] . 二进制编码下的 1-VASS 可达性问题是 NP-难的.
证明: 思路是归约经典 NP-完备问题“子集和问题”, 其定义参见第 1.4.1 节. 子集和问题中所有自然数用二进
制编码. 文献 [19] 中给出了从子集和问题到 1-VASS 可达性问题的对数空间归约. 这里我们展示一种更便捷的归
约到 1-计数器程序的构造方法.

给定子集和问题实例 ⟨S,c⟩, 构造对应的程序 f (⟨S,c⟩) 如图 3 所示.

for i := 1 to n
do x += a ; i or skip;
x -= c; halt;
图 3 从子集和问题到 1-计数器程序的归约 P

程序中的 a 1 , a 2 ,..., a n , c 即原子集和问题中的参数. 注意, 为了保证归约的高效性, 此构造中 1-计数器程序也
应采用二进制编码方案 (否则原问题中的 a i 转换为对应的一进制编码需要花费指数时间).
P 仅使用了一个计数器 , 故是一个 1-计数器程序. 该程序的任意一次执行等价于非确定选择一个子集
x

∑ ∑
T ⊆ S , 若 a−c ⩾ 0 则该执行是完全的且终止格局 β T 满足 β T (x) = a−c, 否则该执行是部分的. 显然, 若
a∈T a∈T
∑
实例 ⟨S,c⟩ 为真, 则存在子集 T 0 ⊆ S 使得 a−c = 0, 程序中对应的执行路径是完全的且最终 β T 0 (x) = 0, 即 P
a∈T 0
∑
存在一个 0-执行; 若该问题实例为假, 则所有子集 T ⊆ S 都有 a−c , 0, 即 P 不存在 0-执行. 综上, ⟨S,c⟩ ∈
a∈T
(∑ n )
subset sum 当且仅当 f (⟨S,c⟩) ∈ 1-CP reachability. 此程序的长度为 O log(a i )+log(c) , 归约 f 可在对数空间完
i=1
subset sum⩽ L 1-CP reachability. 根据计数器程序和 VASS 的等价性即知: 1-VASS 可达性问题是 NP-难的.
成, 即有
需要指出的是, 经典的 NP-完备问题有很多, 但子集和问题与 VASS 模型都与自然数以及加减法运算有关, 二
者之间的关联较为紧密, 因此归约较简单. 结合第 2.2.1 节给出的上界可得如下定理.
定理 2 [19] . 二进制编码下普通和测零 1-VASS 可达性问题都是 NP-完备的.
2.2.3 二进制编码下 2-VASS 可达性问题的 PSPACE-难归约
正如子集和问题对应于 1-VASS 可达性问题的复杂性下界, 2-VASS 的 PSPACE-难证明源自归约子集和博弈
问题 [19] . 然而子集和博弈到 2-VASS 可达性问题的归约是非平凡的, 主要困难在于对 ∀ 玩家, 需要使用仅有的两个
计数器模拟其所有可能选择的分支. 为了完成归约, 研究者引入了两个中间模型, 即有界计数器自动机 (bounded
counter automaton, BCA) 和计数器栈自动机 (counter-stack automaton, CSA). 这些模型都有各自等价的数学描述和
程序表示, 后续会根据具体情况选择合适的表示方式. Fearnley 等人 [24] 和 Blondin 等人 [21] 的证明路线如下:

subset sum game⩽ L b-Safe CSA reachability⩽ L 1-BCA reachability⩽ L 2-VASS reachability (6)
2.2.3.1 有界 1-计数器自动机
有界 1-计数器自动机 (1-BCA) 是一个 3-元组 M = (Q,b,δ), 其中, Q 是一个有限状态集, b ∈ N 是一个计数器的
t
2
全局上界, δ ⊆ Q×Z×[b] 0 × Q 是有限的迁移规则集合. M 的格局形如 p(x) ∈ Q×[b] 0 , 若迁移 p(x)→q(y) 成立, 则
一定存在 t = (p,y− x,lb,ub,q) ∈ δ 使得 lb ⩽ x ⩽ ub. 直观上, 1-BCA 可以判断计数器的值是否大于 lb 或小于 ub, 自
然也可以完成测零 (令 lb = ub = 0), 故其可达性问题至少是 NP-难的.
实际上, 1-BCA 可以直接看作一个格局在 Q×(N∩[0,b]) 中的 1-VASS (有界 1-VASS). 换言之, 其迁移规则中
t = (p,a,lb,ub,q) ∈ δ, 我们可以用如下的有界
的局部上下界参数 lb、ub 不是必须的. 给定 M = (Q,b,δ), 若有规则
1-VASS V 的运行替代:

π (p,−lb,p 0 ) (p 0 ,lb,p 1 ) (p 1 ,b−ub,p 2 ) (p 2 ,ub−b,p 3 ) (p 3 ,a,q)
− →=−−−−−−→−−−−−→−−−−−−−→−−−−−−−→−−−−→ (7)
t π π
t

若 p(x)→ M q(y), 则 满足 x−lb ⩾ 0, x+b−ub ⩽ b, x+a = y, 于是 p(x)→ V q(y); 反之若 p(x)→ V q(y), 则一定有
t
p(x)→ M q(y). 此过程为每条迁移引入 4 V 状态数
0 ⩽ x−lb ⩽ b, 0 ⩽ x+b−ub ⩽ b, x+a = y, 于是 个中间状态, 最终