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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(10):4525−4541 [doi: 10.13328/j.cnki.jos.007302] [CSTR: 32375.14.jos.007302] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
正则图上对称双态自旋系统相关的细密度二分定理

刘 莹 1,2,3

(计算机科学国家重点实验室 (中国科学院 软件研究所), 北京 100190)
1
2
(基础软件与系统重点实验室 (中国科学院 软件研究所), 北京 100190)
3
(中国科学院大学, 北京 100049)
通信作者: 刘莹, E-mail: liuy@ios.ac.cn

摘 要: 讨论正则图上的对称双态自旋系统的配分函数计算复杂性. 利用计数指数时间假设 (#ETH) 和随机指数时
间假设 (rETH), 将该问题类的经典二分定理, 细化到指数型二分定理, 又称细密度二分定理. 换而言之, 证明满足给

定易解条件时, 该问题可在多项式时间内求解; 否则, #ETH 成立时, 该问题没有亚指数时间算法. 还针对平面图限
制下已有插值方法在构造根号亚指数时间归约时失效的问题, 提出两种解决方案, 并利用这两种方案探讨平面限
制下该问题相关的细密度复杂性和二分定理.
关键词: 计算复杂性; 细密度二分定理; 指数时间假设; 配分函数; 自旋系统
中图法分类号: TP301

中文引用格式: 刘莹. 正则图上对称双态自旋系统相关的细密度二分定理. 软件学报, 2025, 36(10): 4525–4541. http://www.jos.org.
cn/1000-9825/7302.htm
英文引用格式: Liu Y. Fine-grained Dichotomies for Symmetric 2-spin System on Regular Graphs. Ruan Jian Xue Bao/Journal of
Software, 2025, 36(10): 4525–4541 (in Chinese). http://www.jos.org.cn/1000-9825/7302.htm

Fine-grained Dichotomies for Symmetric 2-spin System on Regular Graphs
LIU Ying 1,2,3
1
(Sate Key Laboratory of Computer Science (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China)
2
(Key Laboratory of System Software (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China)
3
(University of Chinese Academy of Sciences, Beijing 100049, China)
Abstract: This study discusses the computational complexity of the partition function of the symmetric dual-spin system on regular
graphs. Based on # exponential time hypothesis (#ETH) and random exponential time hypothesis (rETH), this study develops the classical
dichotomies of this problem class into the exponential dichotomies, also known as the fine-grained dichotomies. In other words, this study
proves that when the given tractable conditions are satisfied, then the problem is solvable in polynomial time; otherwise, there is no sub-
exponential time algorithm when #ETH holds. This study also proposes two solutions to solve the in-effectiveness of existing interpolation
methods on building sqrt-sub-exponential time reductions under the restriction of planar graphs. It also utilizes these two solutions to
discuss the related fine-grained complexity and dichotomy of this problem under the planar graph restriction.
Key words: computational complexity; fine-grained dichotomy; exponential time hypothesis; partition function; spin system

1 研究背景与相关工作

自旋系统是描述微观粒子相互作用的重要框架. 在统计物理中, 可用于描述伊辛模型 [1] 、玻茨模型 [2] 等重要
框架, 其配分函数的值, 反映着物质的能量、磁矩等重要物理性质; 在理论计算机科学中, 自旋系统可用于描述图

* 基金项目: 科技部重点研发课题 (2023YFA1009500); 国家自然科学基金 (61932002, 62272448)
收稿时间: 2024-06-14; 修改时间: 2024-08-10; 采用时间: 2024-10-02; jos 在线出版时间: 2025-02-26
CNKI 网络首发时间: 2025-02-26