可满足性问题的结构特征进展综述

摘要：

可满足性(SAT)问题是人工智能的基础问题,也是 NP 难问题,在机器学习、模式识别和自然语言处理等领域有着实际应用.然而,随着人工智能发展,越来越多的问题呈现出更为复杂的形态,原有的算法不再适用,需进一步优化或者改进,这对基础研究提出了更高要求.为了研究 SAT问题难解的内在本质,需要研究其结构特征,进而找出求解 SAT问题的高效算法.近年来备受研究人员关注的相变、树宽、结构熵、DNA 折纸术是 SAT 问题结构特征的 4 种常用度量模型.为了理清关于 SAT问题结构特征的研究进展,基于上述 4 种度量模型,对 SAT 问题的结构特征进行了综述,指出了 SAT问题结构特征研究所面临的挑战及未来的方向.在 SAT 问题求解中相变分析、树分解算法、结构熵及 DNA折纸术等方面虽已取得一定的研究成果,但在相变点精确上界的求解、结构度量模型指导 SAT求解器设计,以及树分解算法效率的提高等方面仍待突破,这将成为未来关于 SAT 问题结构特征研究的重点.

关键词：SAT问题、相变、树分解、结构熵、DNA折纸术

所属期刊栏目：44

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;宁夏自然科学基金资助项目;宁夏青年拔尖人才项目

在线出版日期：2023-11-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：40-47