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

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

模拟函数求值的过程. 此方法虽然较为复杂, 但提供了更广阔的思路, 同时得到的下界相对而言更好. 本节将对这
一方法做详细介绍.
d
对于向量 u ∈ N , 定义如下一般形式的快速增长函数:

F u = F (u(d)) ◦ F (u(d−1)) ◦...◦ F (u(1)) (12)
d d−1 1
即 u 的第 i 个元素对应公式 (12) 中 F i 复合的次数. 于是, 元组 (u,n) 可以用于编码唯一的函数值 F u (n), 我们将这个
d
:
,
映射关系记作 Val N ×N → N,(u,n) 7→ F u (n). 显然 Val 不是单射, 例如 Val(e d ,n) = F e d (n) = F d (n) Val(0 d ,F d (n)) =
Id(F d (n)) = F d (n), 其中, Id : N → N 是恒等函数. 因此 (e d ,n) 和 (0 d ,F d (n)) 都是值 F d (n) 的有效编码, 二者的区别在
于 (e d ,n) = n, 因此是可以高效构造的编码; (0 d ,F d (n)) = F d (n) 是个大数, 无法直接构造但却可以在乘法三元组中直
接使用. 下面我们将这种编码记作 λ = (u,n) : [d] 0 → N, 并且定义 λ(0) = n 以及当 i ∈ [d] 时 λ(i) = u(i), 这相当于将 n
看作 λ 的第 0 维. 利用这种编码, 我们可以构造 F d (n)-放大器如下.
′ ′ ′
1) 假设初始格局为 τ s = (a ,b ,c ,A s ,B,X), 构造编码 λ 0 = (e d ,B).
′ ′
2) 构造一段计数器程序将一个给定编码 λ 转换为等价的编码 λ 使得 λ < lex λ.
3) 不断执行上述程序直到无法继续, 完成转换: (e d ,B) = λ 0 → λ 1 → ... → λ k = (0 d ,F d (B)), 根据最终得到的 λ k
构造三元组 τ t = (a,b,c,A t ,F d (B),X).
步骤 2) 中使用的序关系 ⩽ lex 是字典序, λ ⩽ lex λ 当且仅当最大的使得 λ (i) , λ(i)的下标i 满足 λ (i) ⩽ λ(i). 显然
′
′
′
d 维向量中字典序最小的, 这也是步骤 3) 的转换能够终止的原因. 整个过程的关键是如何找到合适的变
0 d 是所有
换并且构造对应的程序.
给定 λ = (u, x), 若 u 的元素全为 0, 则 Val(λ) = x, 无法也不需要继续进行变换, 这种情况我们称作是平凡的. 若
(u(d−1))
λ 非平凡, 则可定义 index(λ) = min{i ∈ [d] : u(i) , 0}, 不妨设 index(λ) = i 0 , 则 Val(u, x) = F (u(d)) ◦ F d−1 ◦...◦ F (u(i 0 )) (x),
d
i 0
对复合序列的末端分离出一个 F i 0 使用快速增长函数的定义有:

( )
Val(u, x) = F (u(d)) ◦ F (u(d−1)) ◦...◦ F (u(i 0 )−1) F (x+1) (x) (13)
d d−1 i 0 i 0 −1
( )
当 i 0 ⩾ 2 时, 上述结果说明了 Val(u, x) = Val u−e i 0 +(x+1)e i 0 −1 , x . 定义 ε 0 = (0 d ,1); 对 i ∈ [d], 定义 ε i = (e i ,0),
则上述结果可以统一写作:

( )
(14)
+(λ(0)+1)ε i 0 −1
Val(λ) = Val λ−ε i 0
d d
上述讨论定义了一个确定的变换过程 Eval : N ×N → N ×N, λ 7→ λ−ε i 0 +(λ(0)+1)ε i 0 −1 , 其中, i 0 = index(λ).
观察可知: 首先对 i > i 0 都有 Eval(λ)(i) = λ(i) 但 Eval(λ)(i 0 ) < λ(i 0 ), 从而 Eval(λ)< lex λ; 其次, Val(λ) = Val(Eval(λ)),
*
Eval
(k)
从而变换 Eval 保持编码的含义不变. 对 λ 0 = (e d ,B) 不断应用该变换即可得到迁移: λ 0 −−→ Eval (λ 0 ) = (0 d ,F d (B)),
其中, k 是一个由 λ 0 唯一确定的自然数. 我们无须关心 的真实值, 只需使用程序 eval 实现变换 Eval, 并执行 loop
k
′ v = 0 d 即可.
eval 从 λ 0 出发得到 λ = (v,y), 最终检查是否有
Eval 的计数器程序实现
3.4.1
从上述讨论中可以看出, Eval 的计数器程序实现是此方法的核心. 本节将介绍 Leroux [15] 基于乘法形式不变量
的构造方法, 并简要分析该方法的局限性与改进方向. 另外, Leroux 原证明因缺少对特殊情况的讨论而有些许瑕
疵, 在后文中我们予以纠正.
首先, 我们需要使用若干个计数器保存一个给定编码 λ. 我们显然不能只令 b i = λ(i), 否则在非确定地修改 b i
时很容易丢失原有的 λ(i) 值. 根据上文介绍的相关技术, 比较容易想到的方法是使用一对计数器维护 b i +b i = λ(i).
同时因为三元组 (a,b,c,A,B,X) 中需要满足 c = ab, 因此对合适的 A, 我们需要记录 Aλ( j) 的值. Leroux [15] 的方法是:
A i+1 = (1+λ(i))A i . 这里因子设
对 i ∈ [d] 0 构造 b i +b i = λ(i), 对 i ∈ [d +1] 0 构造 a i +a i = A i 且保持对任何 i ∈ [d] 0 都有
定为 λ(i)+1 而非 λ(i) 的用意在于: 若某个 λ(i) 为 0, 则无论 A i 是多少, 使用关系式 A i+1 = λ(i)A i 将导致对任意 j > i
λ A i+1 =
都有 A j = 0, 因此一组 {A i } i∈[d+1] 0 即便满足 A 0 , 0 也可能对应多组 , 这造成了信息的丢失; 使用关系式
(1+λ(i))A i 保证了若 A 0 不为 0, 则对任意 λ 和 j ∈ [d +1] 都有 A j , 0, 因此一组满足 A 0 , 0 的 {A i } i∈[d+1] 0 至多只能对