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

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

染色数目问题 [3] 、点独立集数目问题 [4] 等图论上问题, 其配分函数的值对应着问题的解; 在人工智能和概率论等
领域, 自旋系统也被称为马尔可夫随机场 [5] , 被广泛研究. 自旋系统的配分函数计算问题, 是多领域关心的重点问
题, 其求解算法与计算复杂性也得到持续的关注和研究.
自旋系统由点阵构成, 每个阵点代表一个微观粒子, 具有不同的自旋状态. 自旋系统假设只有最相近的两个粒
子的自旋状态之间具有相互作用. 若粒子只有自旋向上或自旋向下两种状态, 这样的自旋系统被称为双态自旋系
S(V,E) V 表示粒子的集合, 每个粒子的状态用一个取值为 0 (自旋向下) 或 1 (自旋向上) 的
.
统, 可以抽象成一个图
2
布尔变量来表示; E 表示图中边的集合, 每对相互作用的粒子之间连一条边, 边上赋有一个二元函数 g : {0,1} → C
以表示粒子间的相互作用. 这个自旋系统的配分函数定义为:

∑ ∏
Z(S) = g(σ(u),σ(v)),
σ:V→{0,1} (u,v)∈E
其中, σ 表示所有状态变量的一组布尔赋值; σ(u),σ(v) 表示在赋值 σ 下点 u,v 对应变量的赋值.
[6]
配分函数计算问题属于计数问题类 #P . 一个问题 A 属于 #P 类, 则存在一个非确定性多项式时间图灵机对
于输入 x 满足, 接受路径的数量等于 A(x). 一个问题是 #P 难的, 则任意 #P 内的问题可以多项式时间内归约到该问
题; 若该问题也在 #P 内, 则它是 #P 完全的. 自旋系统的配分函数计算问题, 除少数情况外, 是#P 难的. 基于计数复
, #P, 大多数情况下, 人们相信配分函数的精确求解不能在多项式时间内完成. 因此, 探寻
杂性领域重要的假设: P
其的近似算法 [7−10] 或量子算法 [11,12] 是研究的热点之一. 此外, 配分函数的计算复杂性 [13] , 也得到长久的关注和研
究. 根据定义, 配分函数的计算复杂性与图 G 的结构和函数 g 有关. 在过去几十年, 人们从图结构和相互作用函数
两个维度, 对配分函数的计算复杂性进行分析, 给出了一系列经典的二分定理 [14−20] : 图结构或相互作用函数满足
给定条件时, 能给出配分函数的多项式时间确定性求解算法; 否则能证明问题是 #P 难 (#P 完全) 的.
计算复杂性领域内另一被广泛相信的假设由 Impagliazzo 等人 [21,22] 提出, 称为指数时间假设 (exponential time
hypothesis), 简写为 ETH. 该假设认为布尔可满足性问题 (satisfiability) 没有亚指数时间内的确定性算法. 利用
ETH, 可以将 NP 难的问题的计算复杂性, 进一步细化到没有亚指数时间算法 [23] . 该假设被 Dell 等人 [24] 发展到计
数版本#ETH 和随机版本 rETH, 用于证明#P 难问题没有亚指数时间算法, 如图的完美匹配数目问题 [25] . 一些经典
的二分定理, 也被细化到指数型二分定理, 即问题在满足易解条件时有多项式时间内的算法, 否则#ETH 成立时问
题没有亚指数时间算法 (或根号亚指数时间算法), 例如计数约束求解问题的指数型二分定理 [26] . 这样的指数型二
分定理又称为细密度二分定理.
在自旋系统的配分函数计算问题上, 相比于经典二分定理的大量系统性结果 [14−20] , 细密度二分定理还处于兴
起阶段, 仅有小部分结果: 关于 Tutte 多项式 [24,27,28] 、计数约束求解问题 [26,28] 和 Holant*问题 [29] 的细密度二分定理
包含了一些受限自旋系统上配分函数计算的细密度复杂性分类; Chen 等人 [30] 给出了当相互作用函数为布尔值域
的对称函数时, 配分函数计算的细密度二分定理.
本文考虑对称双态自旋系统的配分函数计算的细密度复杂性, 即相互作用函数为对称布尔函数. 根据已有的
正则图上该问题的经典二分定理 [17,19,20] , 发展#ETH 和 rETH 下相关的细密度二分定理. 这是对配分函数计算复杂
性的更细致探讨, 有助于更深层理解该问题的计算复杂性; 同时, 在探索过程中出现的新的归约技术和方法, 也对
其他问题的细密度复杂性研究提供了工具和引导.
1.1 本文成果与结构
本文第 2 节介绍相关基础知识. 第 3 节介绍文章中使用的已有归约技术: 构件构造、全息变换和插值. 第 4 节
为本文核心, 论证正则图结构上对称双态自旋系统相关的细密度复杂性.
第 4.1 节根据经典二分定理的证明, 利用已有归约手段, 证明 k 正则图上该问题的细密度二分定理.
定理 1. 给定一个底层图结构为 k 正则图的双态自旋系统, 其中 为大于 2 的整数. 若粒子间的相互作用函数
k
(
g = [a,1,b] a,b ∈ C) 满足以下某一条件, 则该系统的配分函数可以在多项式时间内计算.
(1) a = b = 0;