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

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

P 是没有嵌套循环的, 这种程序对应的 VASS 中也不存在嵌套的环 (cycle), 因此被称作平
值得注意的是, 程序
坦的 (flat). 这类 VASS 在上界的证明中扮演着重要的角色, 也有研究者 [40,41] 专门从事过平坦 VASS 的研究, 因此
我们有必要在下面的定理中特地强调 flat 这一性质.
定理 13 [39] . 一进制编码下平坦 4-VASS 可达性问题是 NP-难的.
4.2 一进制编码下 5-VASS 的 PSPACE-难归约
针对 PSPACE-难下界的证明, 前文已经提供了两个思路: 其一是利用子集和博弈问题进行归约; 其二是利用
n
3 个计数器的 2 -有界计数器机器可达性问题. 受限于编码方案, 目前暂无人使用子集和博弈问题进行证明; 后者
的难点主要在于可用计数器过少上. 为此, 我们至少需要从两个方面进行优化: 首先, 是否可以证明 2 个计数器的
2 有界计数器机器可达性问题也是 PSPACE-难的? 其次, 能否使用更少的计数器进行模拟测零? 解决这两个问题
n
是证明 5 维以下的一进制 VASS 是 PSPACE-难的前提.
4.2.1 2 个计数器的 2 -有界计数器机器可达性问题
n
前文中, 我们使用了较为平凡的方法论证 Tower 以上的下界可以使用 2 个计数器的 f(n)-有界计数器机器进
x y
行归约, 即利用 2 3 编码两个计数器 x、y, 但这涉及指数量级的放大, 不能应用于需要多项式归约的情景.
Czerwiński 等人 [39] 针对这种特殊情况给出了一种更精妙的证明方法, 使得如下引理成立.
n
引理 17 [39] . 在一进制编码下, 只使用 2 个计数器的 2 -有界计数器机器可达性问题是 PSPACE-难的.
证明: 给定 LBA 实例 ⟨M, x⟩, 其纸带长度为 n = |x|, 不妨设 x = x 1 ◦...◦ x n . 令 p i 为第 个素数, 则我们可以使用
i
i
x 1
a = p p ... p x n n 编码输入, 后续迁移过程使用 a *= p i 和 a /= p i 修改纸带上第 位的内容. 易知这可以使用辅助计数
x 2
2
1
′ nl l M
器 t 实现. 最终我们得到了一个有界计数器机器 M , 它一共具有两个计数器 a, t, 且 a+t ⩽ 2p , 其中, 是一个和
n
′
的字符表有关的常数. 根据素数定理 p n = O(nlnn), 因此 a+t = 2 poly(n) . 注意, M 的所有操作中涉及的常数都是
poly(n) 量级的, 可以采用一进制编码. 由此可知, LBA 问题可以多项式时间归约到一进制编码的只有 2 个计数器
的 2 -有界计数器机器可达性问题上. 证毕.
n
4.2.2 平方二元组
Czerwiński 等人 [39] 基于三元组的思想提出了平方二元组 (quadratic pair) 的概念, 所谓平方二元组是指元组
2
τ = (b,c,B,X), 其中, b,c ∈ X 是两个计数器, 满足 b = B, c = B , 且对任意 x ∈ X\{b,c} 都有 x = 0. 使用过程中需要维
x y 同理.
持待测零计数器 x, y 满足 b+ x+y = B, 并将所有 zero? x 都替换为下面的 zero-test( ),
设某次执行该段程序的初始和终止格局分别为 α、β, 则 β(c) ⩾ α(c)−2α(B)+1, β(B) = α(B)−1. 若初始格局
2 2 2
l
有 α(c) ⩾ α(B) , 则 β(c) ⩾ β(B) , 且 β(c) = β(B) 可推导出 α(x) = β(x) = 0. 模拟测零的过程中 B 也会减少, 经过 次
测零后有 b+ x+y = B−l, 因此 x、y 必须满足 x+y+l ⩽ B. 我们不妨只考虑 x+y ⩽ B/2 与 l ⩽ B/2 的情形, 由此可知
平方二元组可为 (B/2)-有界计数器机器进行 B/2 次模拟测零.
n
给定使用 2 个计数器的 2 -有界计数器机器 M, 易知其测零次数不会超过 2 n+1 s, 其中, 是 M 的状态数. 而 M
s
同时也是 2 n+1 s 有界的 (这也是我们只能从有界计数器机器可达性问题进行归约, 而不能从有界可达性问题进行归
( n+2 ) n+2 2n+4 2
约的原因), 为了模拟 M 的执行, 我们只需构造平方二元组 τ = b,c,2 s,X . 注意, 2 s 和 2 s 是输入规模的指
2
数, 无法直接构造, 而应当分别从 4s、16s 出发进行 n 次乘法, 对应图 21 中的程序 P. 该程序使用计数器 b,c,d, 并
重复了 multiply( b,d,2); multiply( c,d,2); n 次, 每次需要进行 4 次测零, 最终共进行 4n 次测零. 引入 后使用控制
t
计数器方法后, 最终得到 poly(n) 长的程序, 可以{t}-计算出 τ.

loop y -=1, x +=1, c -=1; b = 4s, c =16s 2
loop b -=1, y +=1, c-=1;
loop b +=1, y -=1, c -=1; for i := 1 to n
multiply ( , ,2b d );
loop y +=1, x -=1, c -=1;
multiply ( , ,2c d );
b -=1; c +=1;
zero-text (x) P
图 21 平方二元组的模拟测零和构造

构造平方二元组的过程中使用了 4 个计数器, 模拟 M 的过程需要两个计数器, 总共 6 个. 但注意, 计数器 d 可
以复用, 因此最终只需要 5 个计数器. 如下定理成立.