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

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

2) 减法: “ x− a;”. 同上.
=
L L 等是有限个指令的标签.
3) 非确定跳转: “goto L (or or ...);”. 其中, , ′
L
′
4) 测零: “zero? x,y,z,...;” 对单个计数器 x 或一组计数器“ x,y,z,... ”测零.
5) 停机: “halt;”. 表示程序运行至此停机, 只在程序末出现一次.
X
若某计数器机器 P = (I 1 ,...,I n ) 使用的计数器集合为 , 则它的格局形如 α = I (u), 描述了下一条执行的指令 I
,
和当前所有计数器的取值函数 u : X → N (本质上也是一个有限维向量). 给定计数器 x ∈ X α 中 x 的取值可直接表
α( f) := f (α(x 1 ),...,α(x n )). 计数器机器的语义
示为 α(x) := u(x), 这种写法还可以拓展到函数 f (x 1 ,..., x n ) 上, 定义
( )
如下: 初始时 α 0 = I 1 0 |X| , 顺序执行 P 中指令; 若某次减法操作对应的计数器值 < 0 或测零时指定的计数器值不
0, 则终止执行; 若遇到 goto 语句, 则非确定地选择一个分支执行. 最终得到一个极大的有限长的迁移序列
为
I i 1 I i k
(u) ↛, 称作 P 的一次执行 (execution), 若 = halt, 则称 R 为完全的 (complete), 记作 R:
R : α 0 → α 1 ... → α k = I i k+1 I i k+1
α 0 → P α k ; 否则称其为部分的 (partial). 通常我们只会针对程序 (或片段) 的某个执行讨论其初始格局和终止格局,
此时对应指令已被隐式地确定, 后文中均直接省略. 不包含任何测零指令的计数器机器又称作计数器程序 (counter
program, CP).
若某次完全执行的终止格局为 0, 则称这是一个 0-执行. 可以在计数器程序模型上定义可达性问题 (CP
P, 判定其是否存在 0-执行. 类比 d-VASS d 个计数器的机器
reachability): 给定某计数器程序 的概念, 我们将使用
(程序) 分别称作 d-计数器机器 (程序), 在这些模型上同样可以类似地定义对应的可达性问题. 下面的命题阐述了
d-VASS 与 d-计数器程序的等价性.
命题 2. d-VASS 可达性问题与 d-计数器程序可达性问题可以在对数空间内互相归约.
此命题的证明较为简单: 直接为 d-VASS 构造对应的 d-计数器程序, 反之亦然. 例如, 例 2 中的 V 2 可以通过此
方法转换为图 2 左侧的计数器程序 P 1 使得 p(1,0,n)→ V 2 p(k ,0,0) 当且仅当 P 1 存在 0-执行.
n

a +=1; c += n;
p : goto t 1 or t 2 or end; a +=1; c += n;
1 t : a -=1; b +=1; goto p; loop loop a -=1, b +=1;
2 t : goto q; loop a += k, b -=1;
3 t : a += k; b-=1; goto q; c -=1;
4 t : c -=1; goto p; n
q : goto t 3 or t ; 4 a -= k ;
end: a -= k ; n halt; halt;
P 1 P 2
V 2 的等价计数器程序
图 2

为了提高程序的易读性, 文献中常引入一些语法糖.
● loop 指令: 非确定地将循环体重复执行若干次. 它可以使用 goto 语句实现, 因此并不影响计数器机器或程

序的计算能力. 使用这一语法糖, 我们可以将 P 1 改写成图 2 右侧的程序 P 2 .
● “do s 1 or ;” 语句: 非确定地执行语句 s 1 或 , 这里, s 1 , s 2 可以是 skip, 即什么操作都不做.
s 2
s 2
● “for i:= 1 to M 重复 n 次, 本质上这是一段 O(n|M|) 长的程序.
n M;” 语句: 将
最后, VASS 还有一种带测零操作的变体, 它们的迁移规则集合中允许形如 t = (p,zero-test i ,q) 的规则. 给定格
t
,
局 p(u), q(v) p(u) → q(v) 当且仅当 v = u 且 u(i) = 0. 显然, 此模型和计数器机器是等价的.
1.4 归约、复杂性类、完备性
本节主要介绍后文中涉及的复杂性理论的相关前置知识.
1.4.1 归约与完备性
我们假定读者对图灵机 (Turing machine)、时间函数、空间函数等传统复杂性理论的重要概念均有基础的了

解, 本文仅做一些记号上的约定. 给定时间函数 t(n), 我们用 TIME(t(n)) 和 NTIME(t(n)) 分别表示为所有确定、非
O(t(n)) 时间内可判定的判定问题集合, FNTIME(t(n)) 则分别对应它们的计算版本,
确定图灵机在 FTIME(t(n)) 和
即所有确定 (非确定) 图灵机在 O(t(n)) 时间内可计算的函数集合. 给定空间函数 s(n), 我们用 SPACE(s(n)) 和