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

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

∪ c L 都可以多项式时间归约到对应的图灵机 s(n)-空间接收问题, 这说明了图灵
任何 SPACE(s(n )) 中的问题
c∈N
机 s(n)-空间接收问题在多项式归约下是 ∪ SPACE(s(n ))- 难的. 若 s(n) 是空间可构造的, 图灵机 s(n)-有界问题还
c
c∈N
有一个变体, 即 s(n)-有界图灵机问题 (s(n)-Bounded Automata): 给定输入 ⟨M, x,1 ⟩, 其中, M 是一个能且仅能使用
n
∪ c
s(n) 空间的图灵机, 判定 M 在输入 x 上是否能输出 1. 该问题同样是 SPACE(s(n ))- 难的. 例如, 当 s(n) = n 时, 该
c∈N
问题即是著名的 PSPACE-完备问题: 线性有界自动机接受问题 (LBA).
● f(n)-有界计数器机器可达性问题. 此问题为 s(n)-有界图灵机问题在计数器机器中的推广. 易知, 3 个计数器
可以模拟一个图灵机: 其中, 两个计数器分别以数的形式记录图灵机磁头左右两端的, 剩下一个用于辅助模拟图灵
机的迁移. 特别的对于一个 s(n)-有界图灵机, 模拟过程中计数器的值永远不会超过 c s(n) , 常数 c 和图灵机使用的符
f (n) 的计数器机器称作 f(n)-有界的 (f(n)-bounded). 故可以使用
号表有关. 常把执行过程中所有计数器之和不超过
′
3 个计数器 x、y、z 的 c s(n) - 有界计数器机器 M 模拟一个 s(n)-有界图灵机 M. 不妨设终止后 a 给出了 M 的输出, 令
′
a −=1, 其他计数器循环递减, 最终执行“zero? a, b, c;”, 则 M 在 x 上输出 1 当且仅当 M 存在完全执行. 定义如下.
f(n)-有界计数器机器可达性问题 (f(n)-BCM reachability)

输入: 1 和仅使用 3 个计数器的 f(n)-有界计数器机器 M;
n
输出: M 是否存在完全执行?
2 n
n
上述讨论中令 s(n) = 2 , f (n) = 2 , 可以得到如下引理.
引理 2. 2 - 有界计数器机器可达性问题是 EXPSPACE-难的.
2 n
此外, 图灵机 s(n)-空间接收问题也可以推广到计数器机器模型上: 给定参数 n, 函数 f (n) 和计数器机器 M, 若
M 的某完全执行中所有格局的计数器值之和不超过 f (n), 则此次执行称为 f(n)-有界执行. 定义如下计数器机器
f(n)-有界可达性问题 (CM f(n)-bounded reachability).

计数器机器 f(n)-有界可达性问题
n
输入: 1 和仅使用 3 个计数器的计数器机器 M;
输出: M 是否存在 f(n)-有界 0-执行?
该问题难度与图灵机 s(n)-空间接收问题一致.
● 计数器机器 f(n)-时间可达性问题 (CM f(n)-reachability). 给定参数 n 后, 若计数器机器 M 的某次执行恰好使
f (n) 次测零语句, 我们将此次执行称作 f(n)-时间执行, 定义如下新问题.
用了
计数器机器 f(n)-时间可达性问题
n
输入: 1 和仅使用 3 个计数器的计数器机器 M;
输出: M 是否存在 f(n)-时间执行?

计数器机器 f(n)-时间可达性问题和 f(n)-有界可达性问题分别对应图灵机的时间和空间复杂性. 类似地, 我们
∪ c
可以证明该问题在多项式归约下是 TIME( f (n ))- 难的.
c∈N
1.4.2 快速增长复杂性类
回顾 VASS 的研究历史, 可达性问题之所以在很长一段时间处于开放状态, 其难度不仅在于算法设计、问题
归约等方面, 还在于对基本复杂度类认识的不足. 事实上, 经典的算法问题一般位于人们认识比较充分的复杂性
类, 如 NL、P 等; 其次是指数时间复杂性谱系 k-EXP 以及初等复杂性类 ELEM = ∪ k-EXP. 过去对 VASS 的研究
k∈N
工作表明, 可达性问题不太可能位于指数时间谱系中 [14] . 然而 ELEM 没有完备问题, 无法直接进行归约; 人们又对
该谱系之外的问题和复杂性类缺乏了解. 为了解决这一状况, Schmitz [20] 提出了一族基于序数 (ordinal) 的快速增长
函数 {F ι } ι 和对应的复杂性谱系 {F ι } ι . 该谱系成为研究 d-VASS 可达性下界的基础. 本节简单给出这类函数和谱系