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

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

O(s(n)) 空间内可判定的问题集合. 在此基础上, 一些经典的复杂
NSPACE(s(n)) 表示所有确定、非确定图灵机在
性类定义如下:

∪ ∪ ∪
( ) c c c
NL = NSPACE log n , P = TIME(n ), NP = NTIME(n ), PSPACE = SPACE(n ) (1)
c∈N c∈N c∈N
.
. . 2 n }
若考虑形如 k-exp(n) := 2 k times 的函数, 则还可以定义如下的复杂性谱系:

∪
( ) ( )
c
c
k-EXP = TIME k-exp(n ) , k-EXPSPACE = SPACE k-exp(n ) (2)
c∈N
在复杂性理论中, 我们通常用多项式时间归约 (reduction) 比较问题的相对难度, 其形式化定义如下.
定义 1. 给定问题 A,B, 若存在一个多项式时间可计算函数 (polynomial-time computable function) f 使得 x ∈ A
当且仅当 f (x) ∈ B, 则称 A 能多项式时间归约到 B, 记作 A⩽ p B.
将归约函数限制为多项式时间可计算函数可以保证构造过程的高效性, 但有时我们也会考虑其他形式的归约
函数, 届时将以不同的下标加以区别, 例如 A⩽ L B 表示可以使用一个对数空间可计算函数将问题 A 归约到问题 B.
在给定某归约 ⩽ 的基础上, 我们给出完备性 (completeness) 的定义.
定义 2. 给定复杂性类 C 和问题 A, 若对任意 B ∈ C, 都有 B ⩽ A, 则称问题 A 是 C- 难的 ( C-hard); 若进一步有
A ∈ C, 则称问题 A 是 C- 完备的 ( C-complete).
直观上, 完备问题刻画了一个复杂性类中“最难的问题”. 一般而言, 定义完备性时需要指定归约的类型: 在定
⩽ p , 在定义 NL-完备问题时
义 P、NP、PSPACE、k-EXP、k-EXPSPACE 的完备问题时通常使用多项式时间归约
则使用对数空间归约 ⩽ L . 若问题 A ∈ C, 我们称 C 是 A 的复杂性上界; 若 A 是 C- 难的, 我们称 C 是 A 的复杂性下界.
由于本文主要聚焦于 VASS 的复杂性下界, 因此会涉及较多归约相关的证明. 值得注意的是, 复杂性下界具有传递

性: 若问题 A 是 C- 难 (包括 C- 完备), 且在对应归约下 A ⩽ B, 则问题 B 也是 C -难. 因此, 我们无须考虑 C 中的所有
问题, 只需从 C- 难或 C- 完备问题出发进行归约即可.
下面列出几个经典复杂性类上的完备问题, 便于后文归约.
● 子集和问题. 子集和问题是经典的 NP-完备问题, 其定义如下.
子集和问题 (subset sum)

输入: 集合 S = {a 1 ,...,a n } ⊆ N, 目标 c ∈ N;
∑
输出: 是否存在子集 T ⊆ S 使得 a = c?
a∈T
● 子集和博弈 (subset sum game) 问题. 子集和博弈问题本质上是一个双人博弈: 两个玩家 ∀, ∃ 依次选数, ∃ 玩
家的目标是使得所选数之和为某个给定的自然数 C. 问题是: ∃ 玩家是否有必胜策略? 该问题形式化描述如下.
子集和博弈问题 (subset sum game)

输入: 自然数 A 1 ,B 1 ,E 1 ,F 1 ,...,A n ,B n ,E n ,F n ,C ∈ N;
∑ n
输出: ∀x 1 ∈ {A 1 ,B 1 }∃y 1 ∈ {E 1 ,F 1 }...∀x n ∈ {A n ,B n }∃y n ∈ {E n ,F n } (x i +y i ) = C. 是否为真?
i=1
Travers 证明了 PSPACE-完备问题 TQBF ⩽ L subset sum game, 同时该问题自身也在 PSPACE 中, 从而有如下
引理.
引理 1 [19] . 子集和博弈问题是 PSPACE-完备的.
● 图灵机 s(n)-空间接收问题 ((s(n))-space TMSAT). 这是一类平凡的问题, 其难度与 s(n) 相关.

图灵机 s(n)-空间接收问题
n
1
输入: 图灵机 M, 输入 x, 参数 ;
输出: M 在输入 x 上是否能够在 s(n) 空间内接收?