Page 141 - 《软件学报》2025年第10期

4538 软件学报 2025 年第 36 卷第 10 期

义的局限性, 无法推广到更一般的实数域乃至复数域.
4.2.2 插值与小规模构件结合
仍然考虑插值方法. 想构造根号亚指数归约, 多项式时间插值的局限性在于新实例规模非线性变化; 块插值的
√
局限性在于所需构造的新实例个数过多 (归约时间过长), 即使增大 d 至非常数, 如 N, 也无法在满足根号亚指数
归约时间的同时保持新实例规模仅线性变化. 一个直观的想法是, 减少模拟线性无关函数构件的规模. 考虑一个
N 个点的平面图, 若每个点随机赋予函数 A 或 B, 则会产生 2 N 个构件 (有重复), 这暗示了 N 个点的平面构件所能
实现的函数个数极多, 很多时候远超所需要的 N 个. 根据这点, 本节提出了仅利用 O(logN) 规模的构件来实现 N
个两两线性无关函数的方案, 创新地将其与多项式时间插值结合, 从而在更弱的#ETH 假设下探索 pl-Holant
([a,1,b]|= k ) 相关的细密度复杂性.
根据定理 3, 若#ETH 成立, 对于任意正实数 b 和任意正整数 k ⩾ 3, 存在 ε > 0, 使得 pl-Holant([0,1,b]|= k ) 不能
√
在 2 ε N/logN 时间内计算, 其中 N 表示输入图的点数.
1 2
b , , 则利用图 ,
证明: 利用 k −3 或 k −2 个 [1,1] 与 (= k ) 相连实现 (= 3 ) 或 (= 2 ). 若 7 所示构件, 令 x = −
2 b 2
2 1
y = − , 实现 [0,1,1]; 否则, b = , 令 x = −4,y = −2, 图 7 所示构件实现 [0,4,0] 函数, 再利用路径构件:
b(2b−1) 2
[ ] [ ]
1 1
0,1, ,[1,0,1],[0,4,0],[1,0,1], 0,1, , 实现 [0,1,1]. 即根据构件构造有 pl-Holant({[0,1,1],[1,−1]}|= 3 )⩽ poly pl-Holant
2 2
({[0,1,b],[1, x],[1,y],[1,1],[1,−1]}|= k ). 接下来只需要考虑在 pl-Holant([0,1,b]|= k ) 内插值出这 4 个一元函数. 根据引
理 3, 若对于任意正整数 n, 可以在 poly(n) 时间内构造 n 个 {[0,1,b]|= k } 门实现 n 个两两线性无关函数, 且每个构件
的规模为 O(logn), 则 pl-Holant({[0,1,b],[1, x],[1,y],[1,1],[1,−1]}|= k )⩽ poly pl-Holant([0,1,b]|= k ), 且若原实例的规模为
N, 生成的新实例的规模为 O(N logN). 下面考虑构造所需的两两线性无关函数.

[1, y] [1, x] [1, y]

[0, 1, b] =3 [0, 1, b] =3 [0, 1, b] =3 [0, 1, b]

图 7 实现函数 [0,1,1] 的平面构件

[0,1,b] 与图 6 2
利用一个或两个 类似构造连接可以实现左侧一元函数 [1,b] 或二元函数 [1,b,b ] = [1,b]⊗[1,b]
( )( )
0 1 0 1
(归一化后). 利用图 4 类似构造可以实现函数 [0,1,b k−1 ]; 从而可以构造一个二元函数 A = =
1 b 1 b k−1
( )
1 b k−1 = k 与
k
k
b b +1 , 且总可以通过 A 和左侧一元函数 [1, x] 连接, 实现新的左侧一元函数. 若 为奇数, 利用一个
( )
0 b +1
k
k −3 个一元相等相连得到三元函数 [1,0,0,b k−1 ]; 从而可以实现图 8(a) 所示构件 B = 2 k+1 , 且连接 B 和
b b +b
( ) [ k−1 ]
1 k b
左侧一元函数 [1,y] 能实现新的左侧一元函数. 记 s = A = (b +1) 1,b+ ; 利用上述方法, 总可以递归地
b b +1
k
+
构造一系列 {[0,1,b]|= k } 门, 实现一元函数集合 {M l M l−1 ... M 1 s|M i = A或B,i ∈ [l],l ∈ N }.

k−3
[0, 1, b] [1, 0, 0, b ] [1, b] [0, 1, b] [0, 1, b]
k−2
k−4
[1, 0, 0, 0, b ] [0, 1, b ]
k−3
[1, 0, 0, b ] [1, b] [0, 1, b]
(a) k 为奇数 (b) k 为偶数
( )
k
0 b +1
图 8 实现函数 2 k+1 的构件
b b +b

,
k
归纳法证明 {M l M l−1 ... M 1 s} 集合内函数两两线性无关. 若 l = 1 As = [b 2k+1 +2b +1,b 2k+3 +b k+2 +b k+1 +b] 和
2
Bs = [b 2k+2 +b k+1 +b k+2 +b,b 2k+3 +b k+3 +2b k+1 +2b ] 线性无关. 假设从 {M l−1 ... M 1 s} 内任取两个一元函数, 归一化后记