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

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

(
对称布尔函数. 若 g = [a,0,b] a,b ∈ C), 则 Holant(g|= k ) 实例的任一连通分支内的边的赋值只有两种: 全 0 或全 1,
通过穷举即可在多项式时间内计算实例的值; 若 k ⩽ 2, 则 Holant(g|= k ) 任意实例的任一连通分支为一条路径或者
一个圈, 通过穷举也可在多项式时间内计算该实例的值.
故只需考虑 k ⩾ 3 且 g 形如 [a,1,b] 的情况.
4.1 一般图
Cai 等人 [17,19,20] 已经证明该问题的经典二分定理.
定理 7 [17,19,20] . 若函数 g = [a,1,b] a,b ∈ C) 满足以下某一条件, 则对于任意正整数 k ⩾ 3 Holant(g|= k ) 有多项式
,
(
时间算法.
(1) a = b = 0;
(2) ab = 1;
2k
2k
(3) ab = −1 且 a = b .
否则, 该问题是#P 难的. 该结论对 Holant({g,[0,1],[1,0]}|= k ) 仍然成立.
当 g 不满足易解条件时, Cai 等人 [17,19,20] 以两个已知#P 难的问题: Holant([c,1,c]|EQ) 和 Holant([0,1,1]|= 3 ) 为起
√
3
2
3
3
c
始问题, 其中 c = ±a b/a 或 满足 c = ab 且 2c = a +b ; 并利用构件构造、全息变换和多项式时间插值, 根据
a,b 取值的不同, 分别建立了这两个问题到 Holant(g|= k ) 的多项式时间归约链. 参考定理 7 的证明, 容易证明以下细
密度二分定理.
根据定理 1, 若函数 g = [a,1,b] a,b ∈ C) 满足 (1) a = b = 0 或 (2) ab = 1, 或 (3) ab = −1 且 a = b , 则对于任意
2k
2k
(
,
正整数 k ⩾ 3 Holant(g|= k ) 有多项式时间算法; 否则, 若#ETH 成立, 则存在 ε > 0 使得该问题没有 2 εN 时间的确定性
算法, 其中 N 为输入图点数. 该结论对 Holant({g,[0,1],[1,0]}|= k ) 仍然成立.
g 满足易解条件时, 定理 7 论证了定理 g 不满足易解条件时, 参考定理 7 中#P 困难性的证
证明: 当 1. 当
明 [17,19,20] , 总可以建立以下某一条归约链.
(1) Holant([c,1,c]|EQ)≡ serf Holant({[c,1,c],[1,0,1]}|= 3 ) (平凡的构件构造)
⩽ serf Holant({[c,1,c]}∪{[x i ,y i , x i ]} i⩾1 |= 3 ) (块插值)
⩽ serf Holant([c,1,c]|= 3 ) (构件构造, 见文献 [20] 中定理 5 的证明)
≡ serf Holant([a,1,b]|= 3 ) (见文献 [20] 中引理 5),

3
3
其中, {[x i ,y i , x i ]} i⩾1 表示一系列两两线性无关函数的集合; c 满足 c = ab 且 2c = a +b .
2
3
(2) Holant([ec,1,ec]|= 3 )≡ serf Holant([c,1,c]|[1,0,0,e]) (全息变换, 见文献 [17] 中引理 14)
⩽ serf Holant({[c,1,c],[1,1,1]}|[1,0,...,0,e])(平凡的构件构造)
⩽ serf Holant({[c,1,c]}∪{[x i ,y i , x i ]} i⩾1 |[1,0,...,0,e]) (块插值)
⩽ serf Holant([c,1,c]|[1,0,...,0,e])(构件构造, 见文献 [17] 中引理 15, 16, 17)

≡ serf Holant([a,1,b]|= k ) (全息变换, 见文献 [17] 中引理 14),

( ) 1
b 2
其中, c = a , e = ±1 {[x i ,y i , x i ]} i⩾1 表示一系列两两线性无关函数的集合.
,
a
(3) Holant([0,1,1]|= 3 )⩽ serf Holant([0,1,1]|= k ) (构件构造, 见文献 [19] 中引理 15)
⩽ serf Holant([a,1,b]|{= k }∪{[x 1 ,0,y 1 ],...,[x m ,0,y m ]}) (构件构造, 见文献 [20] 引理 4)
⩽ serf Holant([a,1,b]|{= k }∪{[x j ,0,y j ]} j⩾1 ) (块插值)

≡ serf Holant([a,1,b]|= k ) (构件构造, 见文献 [19] 中第 4.2 节),
其中, m 为某个常数, [x 1 ,0,y 1 ],...,[x m ,0,y m ] 为 m 个二元函数, 它们仅与 a,b,k 有关; {[x j ,0,y j ]} j⩾1 表示一系列两两线
性无关函数的集合.
以上归约链中涉及的块插值方法皆与引理 4 中类似. 根据定理 4, 存在正数 ε 1 使得 Holant([c,1,c]|EQ) 没有
2 ε 1 N 时间算法, 则由归约链 (1) 得 Holant([ec,1,ec]|= 3 ) 对某个正数 ε 2 没有 2 ε 2 N 时间算法; 又根据定理 5, 存在正数
ε 3 使得Holant([0,1,1]|= 3 ) 也没有 2 ε 3 N 时间算法. 由此, 对任意不满足易解条件的 g 所定义的 Holant([a,1,b]|= k ) 问题,