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

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

的形式化定义.
由于已知一般 VASS 可达性问题是 Ackermann-完备的, 这里只给出基于 N ω 的快速增长函数 (fast-growing
function) F d : N → N 如下:
{F ι } ι∈N ω . 首先对于自然数 d, 归纳定义
F 0 (x) = x+1 (3)

F d+1 (x) = F (x+1) (x) (4)
d
其中, f (k) 表示将函数 f 复合 k 次. 对于极限序数 ω, 定义 F ω : N → N 为 F ω (x) = F x+1 (x). 例如, F 1 (x) = 2x+1 F 2 (x) =
;
.
. . 2 x }
2 x+1 (x+1)−1 是一个指数量级的函数; F 3 (x) 的表达式已经十分复杂了, 是一个达到 tower(x) = 2 x times
量级的非初等函数 (elementary function); F ω (x) 是非原始递归 (primitive-recursive function) 的 Ackermann 函数.

在上述定义的基础上, 可以定义如下两种函数类:

∪ ( ) ∪
(c)
F ι = FTIME F (n) , F <ι = F ι ′ (5)
ι
c∈N ι ′ <ι
易知, F 1 = F 0 是线性时间可计算的函数; F 2 = F <3 表示初等函数类 FELEM (前文中的 ELEM 是对应的判定
问题类); F <ω 表示原始递归函数类 FPR. 此谱系 {F ι } ι 一般称为扩展 Grzegorczyk 谱系 (extended Grzegorczyk
hierarchy), 由于谱系中的层级均无对应的完备问题, 它依然不是刻画复杂性的良好选择, 仅作为快速增长复杂性谱
系的中间定义引入.
Schmitz 的关键贡献在于定义了快速增长复杂性谱系 {F ι } ι , 其中, F ι = ∪ TIME(F ι (p(n))). 函数 p 在谱系 {F ι } ι
p∈F <ι
中层级低于 ι. 注意, 当 ι ⩾ 3 时将定义中的 TIME 替换成 NTIME 或 SPACE 不会改变所定义的复杂性类, 因为此时
,
p 已覆盖所有初等函数, 而对应选项之间的转换却只涉及至多指数量级的放大. 一般令 Tower = F 3 Ackermann =
F ω , 这也解释了前文中相关记号的含义. 引入复杂性类 {F ι } ι 的主要原因是这些类均有完备问题. 在定义 F ι - 难问题
时通常使用 F <ι 时间归约, 结合第 1.4.1 节的内容, 有如下引理.
引理 3. 当 ι ⩾ 3 时, 计数器机器 ι(n)- 有界可达性问题、计数器机器 F ι (n)- 时间可达性问题是 F ι - 难的.

当 ι ⩾ 3 时, 可以将上述问题的输入 M 限定为只使用 2 个计数器的机器, 因为我们可以将原来的 x, y 编码为
x y 2 F ι (n) 2 F ι (n) - 有界可达性问
2 3 , 这是一个 2 量级的数值. 因此图灵机 F ι (n)- 空间接收问题可以初等归约到计数器机器 2
2 2 F ι (n) ( ) F ι (n)- 时间可达性同理, 故有如下推论.
题上, 且 远小于 F ι poly(n) . 计数器机器
推论 1. 当 ι ⩾ 3 时, 只使用 2 个计数器的计数器机器 F ι (n)- 有界可达性问题、计数器机器 F ι (n)- 时间可达性问
题也均为 F ι - 难的.
2 1-VASS 和 2-VASS 的完备性结论

本节梳理加法向量模型上已有的完备性结论, 重点聚焦于下界证明技术. 需要指出的是, 迄今 VASS 模型上关
于可达性问题复杂性的完备性结论屈指可数: 除了前文提到的 Ackermann-完备性, 只有关于 1 维 VASS 和 2 维
VASS 的结论. 表 1 总结了已有的完备性结论.

表 1 VASS 可达性问题的完备性结论

编码方案 1-VASS 2-VASS 一般情形
一进制编码 NL-完备 NL-完备
Ackermann-完备
二进制编码 NP-完备 PSPACE-完备

关于一般 VASS 可达性问题 (Ackermann-完备) 可以基于维度得到更精细的参数复杂性结果, 更多细节将在
第 3 节讨论. 参考第 1.2 节的分类方式, 我们按一进制和二进制编码方案对 1 维 VASS 和 2 维 VASS 的可达性问
题复杂性分别进行讨论.