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

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

(2) ab = 1;
(3) ab = −1 且 a = b .
2k
2k
否则, 若#ETH 成立, 则配分函数不能在 2 O(N) 时间内计算, 其中 N 表示系统内粒子数 (点数).
第 4.2 节进一步探讨平面 k 正则图上该问题的细密度二分定理. 当限制图结构为平面时, 已有插值技术的失效
使得细密度复杂性的分析论证更为困难. 本文退一步考虑, 除了相互作用函数 g, 粒子可能会被额外的一个一元函
数 [0,1] 作用时, 平面图上的双态自旋系统. 一个粒子被额外的一元函数 [0,1] 作用时, 例如图 1 所示 (黑点表示粒
子, 边表示函数), 该粒子的状态被限制为 1 (自旋向上).

g [0, 1]
g

[0,1] 作用的粒子
图 1 被两个相互作用函数 g 和一个一元函数

第 4.2.1 节利用比#ETH 更强的 rETH 假设, 规避了插值的使用, 从而论证了这样的系统配分函数计算问题的
细密度二分定理.
定理 2. 给定一个底层图结构为 k 正则图的双态自旋系统, 其中 为大于 2 的整数, 该系统中粒子受到相互作
k
(
用函数 g = [a,1,b] a,b ∈ Q) 或独立作用函数 [0,1] 的约束. 当 g 满足以下条件之一时, 该系统的配分函数可以在多
项式时间内计算.
(1) a = b = 0;
(2) ab = 1;
2k
2k
(3) ab = −1 且 a = b , 即 (a,b) ∈ {(1,−1),(−1,1)}.
√
否则, 若 rETH 成立, 配分函数不能在 2 O( N) 时间内计算, 其中 N 表示系统内粒子数 (点数).
第 4.2.2 节给出一个利用小规模构件实现两两线性无关函数的创新性方法, 并将该方法与多项式时间插值结
合, 从而论证了平面正则图上受限对称双态自旋系统的配分函数计算的细密度复杂性下界.
定理 3. 给定一个底层图结构为平面 k 正则图的双态自旋系统, 该系统中相互作用函数为 g = [0,1,b], 其中 k 为
√
大于 2 的整数且 b 为非负实数. 若#ETH 成立, 则配分函数不能在 2 O( N/(logN)) 时间内计算, 其中 N 表示系统内粒子
数 (点数).
第 5 节总结本文成果并给出几个待解决问题.

2 基础知识

2.1 相关记号与定义
q [q] 表示一个大小为 的有限集合
N、 R 和 C 分别表示自然数集、实数集和复数集. 对于某个正整数 , q
{1,2,...,q}. 若 q = 2, 则 [q] 称为布尔域, 该域中任意元素被赋值为 0 或 1. 一个定义在 [q] 上的复数值函数 F 将 [q] k
内的项映射到复数, 其中 k ∈ N 被称作函数的元. 布尔一元函数 F 通常写作 [F(0),F(1)], 布尔二元函数 H 通常写
( )
H (0,0) H (0,1)
作矩阵形式 . 一个 k 元函数 F 是对称函数, 当且仅当函数值与变量赋值的顺序无关, 即
H (1,0) H (1,1)
π : [k] → [k] 为一个置换函数. 根据
F(a 1 ,a 2 ,...,a k ) = F(a π(1) ,a π(2) ,...,a π(k) ), 其中 a 1 ,a 2 ,...,a k 为 F 的一组变量赋值且
定义, 一个 k 元对称布尔函数 F 的值仅由变量赋值中 1 的个数 (也称汉明权重) 决定, 故 F 可写作 [ f 0 , f 1 ,..., f k ], 其
i
中 f i 表示 F 在汉明权重为 的变量赋值下的函数值. 例如, 二元布尔相等函数, 记作 = 2 , 可写作 [1,0,1].
张量积的一个特例就是 Kronecker 积, 用 ⊗ 表示. 假设 a,b,c,d 为正整数, 两个矩阵 X = X {a×b} 和 Y = Y {c×d} 之间
的张量积 X ⊗Y 是一个 ac×bd 矩阵, 且其在第 (i, j) ∈ [a]×[c] 行、第 (k,l) ∈ [b]×[d] 列的元素为 X i,k ×Y j,l . 递归定义