软件学报

作者：刘莹

单位：刘莹，计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;基础软件与系统重点实验室 (中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004911

关键词：计算复杂性;细密度二分定理;指数时间假设;配分函数;自旋系统

基金：科技部重点研发课题(2023YFA1009500); 国家自然科学基金(61932002, 62272448)

讨论正则图上的对称双态自旋系统的配分函数计算复杂性. 利用计数指数时间假设(#ETH)和随机指数时间假设(rETH), 将该问题类的经典二分定理, 细化到指数型二分定理, 又称细密度二分定理. 换而言之, 证明满足给定易解条件时, 该问题可在多项式时间内求解; 否则, #ETH成立时, 该问题没有亚指数时间算法. 还针对平面图限制下已有插值方法在构造根号亚指数时间归约时失效的问题, 提出两种解决方案, 并利用这两种方案探讨平面限制下该问题相关的细密度复杂性和二分定理.

来源：2025年第10期

《软件学报》期刊编辑部

查看软件学报杂志2025年第10期