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

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

( ) ( ) ( ) ( ) ( )
1 1 1 1 1
作 [1, x] 和 [1,y], 它们线性无关, 即 x , y. 容易判断 A 和 A , B 和 B 线性无关. A 归一化
x y x y x
( ) [ ] k−1
1 b k−1 b
−1 −1
−2 −1 −1
,
后为 [1,b+(b k−1 + x ) ] B 归一化后为 [1,b+(b k−2 +b ) y ]; 由于 s = 1,b+ 且 b > 0, 故 b+ > b,
y b +1 b +1
k
k
则 x,y > b ; 又 b+(b k−1 + x ) 单 调 递 增 , b+(b k−2 +b ) y 单 调 递 减 , 则 b+(b k−1 + x ) < b+(b k−1 +b ) < b+
−1 −1
−1 −1
−2 −1 −1
−1 −1

( ) ( )
1 1
−2 −1 −1
(b k−2 +b ) y , 即 A 和 B 线性无关. 则综上可知 {AM l−1 ... M 1 s}∪{BM l−1 ... M 1 s} 集合内函数两两线性
x y
无关.
若 k 为偶数, 利用一个 = k 与 k −2 个一元相等相连得到四元函数 [1,0,0,0,b k−2 ]; 利用一个 = k 与 k −2 个一元相
( ) ( ) ⊗2
0 b +1 ⊗2 1
k
′
等相连得到二元函数 [1,0,b k−2 ]; 从而可以实现图 8(b) 所示构件 B = 2 k+1 . 此时, 令 s = A , 由于
b b +b b
k 为偶数, 则 pl-Holant({[0,1,b],[1, x],[1,y],[1,1],[1,−1]}|= k ) 的任意实例中一元函数出现的个数为偶数, 且可以通过
( ) ⊗2 ( )
1 1
′
调整平面实例, 使其满足每一个面包含偶数个一元函数, 则 s = A ⊗2 可视为两个独立的 s = A 使用;
b b
′
′
′
′
′
同理, 形如 ((M l M l−1 ... M 1 )⊗(M M ′ l−1 ... M ))s 的函数可以视为两个独立的一元函数 M l M l−1 ... M 1 s 和 M M ′ l−1 ... M s
l
l
1
1
B i ∈ [l]. 故仍可以按照引理
′
使用, 其中 M i , M = A 或 , 3 所给方式进行插值.
i
G 是
上述归约方法建立了 pl-Holant({[0,1,1],[1,−1]}|= 3 ) 到 pl-Holant([0,1,b]|= 3 ) 的多项式时间归约. 不妨设
pl-Holant({[0,1,1],[1,−1]}|= 3 ) 的一个 N 个点的实例, 则上述归约时间为 poly(N), 归约过程中产生 poly(N) 个 pl-Holant
,
([0,1,b]|= 3 ) 的实例, 且新实例的点数不超过 cN logN c 为某个常数. 若定理 3 不成立, 则对任意 ε > 0, 每个新实例
√ √
′
的值能在 2 ε cNlogN/log(cN logN) ⩽ 2 ε c ′ N 时间内计算, c 为某个常数. 结合上述归约算法, 对于任意 ϵ > 0, 在 N 足够大时,
√ ϵ N
√
ε c ′ N
总可以选取足够小的 ε, 使得 poly(N)+poly(N)2 ⩽ 2 时间内能计算出 #(G), 这与定理 6 矛盾.
5 总 结
本文探讨了, #ETH 假设和 rETH 假设下, Holant([a,1,b]|= k ) 的相关细密度复杂性. 当无额外图结构限制时, 利
用已有的归约技术和证明思路, 容易发展#ETH 假设下 Holant([a,1,b]|= k ) 的细密度二分定理. 当要求图结构为平面
时, 对归约时间和生成实例规模的进一步限制使得已有的插值方法失效. 本文提出了两种解决方案: 一种是在更强
的 rETH 假设下, 只需实现出与目标函数在模 p 意义下等价的函数即可, 从而规避掉插值运算; 第 2 种方法仍在
#ETH 假设下, 利用 O(logn) 规模构件来实现 n 个线性无关的函数, 将其与多项式时间插值结合, 降低多项式时间
pl-Holant({[a,1,b],[0,1]}|= k ) 问题 ( a,b ∈ Q) 在 rETH 下的
插值产生的新实例的规模. 利用这两种方案, 本文论证了
+
细密度二分定理和 pl-Holant([0,1,c]|= k ) 问题 ( c ∈ R ) 在#ETH 下的细密度复杂性下界. 这两个结论仍待改进. 一方
pl-Holant([a,1,b]|= k ) 在 rETH 下的细密度二分定理;
面思考如何在 pl-Holant([a,1,b]|= k ) 内实现 [0,1] 函数, 以得到
另一方面是找到小规模构件模拟线性无关函数的充分条件, 扩大改进后的多项式时间插值的适用范围, 以探讨
#ETH 下, 实数域乃至复数域上 pl-Holant([a,1,b]|= k ) 问题的细密度下界.
本文在较强的 rETH 假设下, 利用取模操作降低了函数实现的难度, 得到了平面正则图上双态自旋系统相关
√
√ Ω( N/(logN))
Ω( N)
的 2 下界结论; 在较弱的#ETH 假设下, 改进了现有插值方法, 得到了相关的 2 下界结论. 若想在
√
#ETH 下得到更强的 2 Ω( N) 下界结论, 两个可能的研究思路是: (1) 寻找函数集更易于实现的归约起始问题, 从而规
避插值; (2) 本文在使用插值方法时, 求解了所有的系数, 但很多时候只需求解某些特定系数即可, 从这点入手或可
改进块插值方法.
References:
[1] Cipra BA. An introduction to the Ising model. The American Mathematical Monthly, 1987, 94(10): 937–959. [doi: 10.1080/00029890.
1987.12000742]
[2] Martin PP. Potts Models and Related Problems in Statistical Mechanics. Singapore: World Scientific, 1991. 1–16. [doi: 10.1142/0983].
[3] Kotek T, Makowsky JA, Zilber B. On counting generalized colorings. In: Kaminski M, Martini S, eds. Computer Science Logic. Berlin:
Springer, 2008. 339–353. [doi: 10.1007/978-3-540-87531-4_25]