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

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

∑ ∏
#(G l ) = ρ t t i ).
x = µ(x l 1
l i , x l 2 ,..., x l m
t i∈[m]
∏
m µ 在
由于 {g j } 两两线性无关, 故通过上述方式构造 (n i +1) ⩽ n 个实例去询问 Holant(F) 的神谕, 可以得到
i∈[m]
(∏ )
∏ ∏
(n i +1) 个不同点上的值. 根据拉格朗日插值法, 已知 µ 在 (n i +1) 个不同点上的值, 可以在 poly (n i +1)
i∈[m] i∈[m] i∈[m]
时间内计算出 µ 中所有未知系数 . 从而可以计算得 µ(a 1 ,a 2 ,...,a m ) = #(G).
ρ t
接下来分析以上归约所需时间. 每构造一个 G l 需要 poly(|V|) 时间, 访问一次 Holant(F) 的神谕所花费的时间
(∏ ) (∏ )
为 O(1); 计算出所有 ρ t 需要 poly (n i +1) 时间; 计算 µ(a 1 ,a 2 ,...,a m ) 需要 poly (n i +1) 时间; 故总时间
i∈[m] i∈[m]
为 poly(|V|), 即以上归约可在 poly(|V|) 时间内完成.
(2) 块插值: 构造亚指数时间归约来证明 Holant(F ∪H)⩽ serf Holant(F). 由于亚指数时间归约具有传递性, 因此
在这里简单展示 H 内只有一个一元函数 [1,a] 时的归约细节.
′ ′
G(V,E) 为 Holant(F ∪{[1,a]}) 的一个实例, 且其中对应函数 [1,a] 的点集记作 V . 设 V = n ⩽ |V|.
′ d. 这些集合被称为
任给一个正整数 d, 将 V 分成 r = ⌈n/d⌉ 个不相交集合 B 1 ,B 2 ,...,B r , 满足每个集合大小不超过
r
“块”. 不妨设 n 被 d 整除, 即每块大小恰好为 d. 为 E 的每组布尔赋值都新设计一个标签 ⃗ t = (t 1 ,t 2 ,...,t r ) ∈ {0,1,...,d} :
,
该组赋值下, ∀i ∈ [r] B i 内恰好有 t i 个点的邻边被赋值为 1. 根据定义:

∑ ∏
#(G) = ρ ⃗ t a ,
t i
r i∈[r]
⃗ t∈{0,1,...,d}
⃗ t
其中, ρ ⃗ t 仍然为标签 的所有可能赋值下的 V −V 中点对应函数值的积. 定义 n 次 元多项式:
′
r

∑ ∏
t i
µ(z 1 ,z 2 ,...,z r ) = ρ ⃗ t z i .
r
⃗ t∈{0,1,...,d} i∈[r]
有 µ(a,a,...,a) = #(G). 根据假设, 利用 F 门可以实现 (d +1) 个两两线性无关的一元函数, 记为 {g j = [1, x j ] | x j ∈
⃗ r B i 内点
C, j ∈ [d +1]}. 由于 d 为常数, 则这些 F 门的规模为常数. 任取 l = (l 1 ,l 2 ,...,l r ) ∈ [d +1] , 对于任意 i ∈ [r], 将
对应函数替换成 , 得到新的 Holant(F) 的实例 . 根据定义:
g l i G ⃗ l

∑ ∏
) = t i ).
#(G ⃗ l ρ ⃗ t (x l i ) = µ(x l 1 , x l 2 ,..., x l r
r
⃗ t∈{0,1,...,d} i∈[r]
r
r
由于 {g j } 两两线性无关, 故取遍 ⃗ l ∈ [d +1] 并按照上述方式构造 (d +1) 个新的实例去询问 Holant(F) 的神谕,
r
能得到 µ 在 (d +1) 个不同点上的值, 恢复出所有的系数 , 从而计算 #(G).
ρ ⃗ t
r F 门的规模为常数, 故每个
以上归约构造 (d +1) 个新的实例, 每个实例构造需要 poly(|V|) 时间. 由于涉及的
新的实例规模为 O(|V|). 以上归约的时间为:

r
r
r
T(|V|;d) = (d +1) (poly(|V|)+O(1))+poly((d +1) )+poly((d +1) ) ⩽ 2 c log(d+1) |V| ,
d
其中, c 为某个常数 (与 G 相关). 任给一个时间运行参数 ε > 0, 总可以选取足够大的常数 d, 使得 T(|V|;d) ⩽ 2 ε|V| , 故
以上归约为亚指数时间归约.
由引理 4 的证明可以看出, 若原问题实例有 N 个点, 多项式时间插值归约会构造常数元 O(N) 次多项式, 求解
( )
N
O 元
其中的 poly(N) 个系数需要构造 poly(N) 个新的实例, 其中每个新的实例规模为 poly(N); 而块插值会构造
d
log(d+1) N log(d+1) N
O(N) 次多项式, 求解其中的 O(2 d ) 个系数需要构造 O(2 d ) 个新的实例, 其中每个新的实例规模为 O(N). 容
易看出, 块插值牺牲归约时间, 将归约中需要构建的新实例规模限制在线性规模 O(N); 同时, 通过调节常数 d 的大
2 , 从而构造了亚指数时间归约. 多项式时间插值需要
εN
小, 使得构造的新实例个数及整个归约的时间小于给定的
O(N) 个线性无关函数的构件帮助构造新的实例, 而块插值仅需要常数个 d ( 个). 因此, 对于两个问题 A 和 B, 若能
通过多项式时间插值方法证明 A ⩽ poly B, 则必能通过块插值方法证明 A ⩽ serf B.
4 对称双态自旋系统相关的细密度二分定理
2
考虑 k 正则图上的对称双态自旋系统的配分函数计算问题, 即 Holant(g|= k ), 其中 k 为正整数, g : {0,1} → C 为