正则图上对称双态自旋系统相关的细密度二分定理
作者:
中图分类号:

TP301

基金项目:

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


Fine-grained Dichotomies for Symmetric 2-spin System on Regular Graphs
Author:
  • LIU Ying

    LIU Ying

    Sate Key Laboratory of Computer Science (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China;Key Laboratory of System Software (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100049, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

刘莹.正则图上对称双态自旋系统相关的细密度二分定理.软件学报,,():1-17

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2024-06-14
  • 最后修改日期:2024-08-10
  • 在线发布日期: 2025-02-26
文章二维码
您是第19728356位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号