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

刘莹 等: 正则图上对称双态自旋系统相关的细密度二分定理 4531

k
一个定义在 [q] 上的 元函数 F 总可以写成列向量的形式, 即选取某个变量作为列标, 其余变量作为行标, 按
3 元布尔相等函数 (对称函数值与变量顺序无关) 可写作:
照字母序展开, 相应位置填入对应函数值. 如

 
1 0
 
 
 
 0 0 
 
   ,

(= 3 ) =   
 0 0 
 
 
 
0 1
其中, 行标展开为 00, 01, 10, 11; 列标展开为 0, 1. 对任意矩阵 T ∈ C q×q , T F 即为 F 被 T 作用后的转换函数. 类似
⊗k
⊗k ⊗k ⊗k
定义 FT , 其中 F 写作行向量. 对于 [q] 上的函数集 , FT = {FT |F ∈ F}.
F TF = {T F|F ∈ F} 且
, [q] 上的函数集, 一个可逆矩阵 T ∈ C q×q 定义的全息变换为: 对于 Holant q (F|H) 的一个二
H F 为两个定义在
−1 ′ ′ F ∈ F (或
部图实例 Ω(G,π), 构建一个 Holant q (FT|T H) 的一个二部图实例 Ω (G,π ); 若 π 将 v ∈ V(G) 映射到函数
T # q (Ω) = # q (Ω ), 故容易得
−1 ⊗d(v)
′ FT ⊗d(v) (T ) H). Valiant [31] 证明了, 对任意可逆矩阵 , ′
H ∈ H), 则 π 将 v 映射到函数 (或
到以下结论.
引理 3. , q 为大于 1 T ∈ C q×q , 有:
H F 为两个定义在 [q] 上的函数集, 其中 的正整数. 对于任意可逆矩阵
−1
−1
Holant q (F|H)≡ poly Holant q (FT|T H)且Holant q (F|H)≡ serf Holant q (FT|T H).
3.3 插 值
构件构造和全息变化这两个归约方法, 对于输入实例都一对一的构造一个新的等值实例. 插值方法与它们不
同, 插值方法生成多个新的实例, 利用这多个实例的值来计算原始输入实例的值. A 和 B 是两个图上的问题, 利用
插值方法构造 A 到 B 的归约一般分两步.
(1) 根据 A 的输入实例 G, 构造一个多项式 µ, 满足在某个点 a 上 µ(a) = A(G).
(2) 根据 G 构造一系列 B 的实例 G 1 ,G 2 ,... 满足 B(G 1 ) = µ(b 1 ),B(G 2 ) = µ(b 2 ),..., 利用 B 的神谕得到 µ 在多个不
同点的值, 根据拉格朗日插值恢复出 µ 内每项的系数, 从而计算得到 µ(a) = A(G).
以下例子展示了通过插值方法构建多项式时间归约 [4,6] 和亚指数时间归约 [25] .
引理 4. F 为一个布尔函数集, m 为正整数, H = {[1,a i ]|a i ∈ C,i ∈ [m]} 为 m 个布尔一元函数构成的集合. 对于任
意正整数 N, 若能构造出一系列 poly(N) 规模的 F 门以实现 N 个形如 [1, x] 的一元函数, 其中 x ∈ C, 且这 N 个函数
两两线性无关, 则:

Holant(F ∪H)⩽ poly Holant(F)且Holant(F ∪H)⩽ serf Holant(F).
若涉及的 F 门都是平面的, 则以上结论在平面限制下仍成立.
证明: (1) 多项式时间插值: 构造多项式时间归约来证明 Holant(F ∪H)⩽ poly Holant(F).
令 G(V,E) 为 Holant(F ∪H) 的一个实例. V 中每个点都对应 F 内某个函数或 H 内某个函数 h i = [1,a i ], 记
∑
′
′
V
对应 h i 的点构成的集合为 , 不妨设 |V | = n i 且 n i = n ⩽ |V| . 为 E 的每组布尔赋值都设计一个标签 t =
i i
i∈[m]
(t 1 ,...,t m ) ∈ {0,1,...,n 1 }×...×{0,1,...,n m }: 该组赋值下, V i 内有 t i 个点的邻边被赋值为 1. 根据定义:
′

∑ ∏ ∏ ∑ ∏
t i
#(G) = F v (σ| E(v) ) h i (σ| E(v) ) = ρ t a ,
i
′ ′
v∈V i ,i∈[m] t i∈[m]
σ:E→[q] v∈V−∪ i V i
∑ ∏
t
其中, ρ t = ′ F v (σ| E(v) ), 即有相同标签 的所有可能赋值下的 V −∪ i V 中点对应函数值的积. 定义 n
′
v∈V−∪ i V i i
σ with label t
次 m 元多项式:

∑ ∏
t i
µ(z 1 ,z 2 ,...,z m ) = ρ t z .
i
t i∈[m]
有 µ(a 1 ,a 2 ,...,a m ) = #(G). 根据假设, 存在 (n+1) 个大小为 poly(n+1) 的 F 门实现了 (n+1) 个两两线性无关的
l
一元函数 {g j = [1, x j ]|x j ∈ C, j ∈ [n+1]}. 定义 l = (l 1 ,l 2 ,...,l m ) ∈ [n 1 +1]×[n 2 +1]×...×[n m +1]. 任取 对 G 作以下操
作: ∀i ∈ [m], 将 V 内点对应函数由 h i 替换成 (本质上是替换成实现 g l i 的 F 门), 得到新的 Holant(F) 的实例 G l .
′
i
g l i
G l 的规模为 poly(|V|). 根据定义, 可知: