可满足性问题相变研究综述

来源：计算机应用杂志2024年第11期北京时间：

作者：彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞

单位：1.北方民族大学 计算机科学与工程学院，银川 750021；2.图形图像智能处理国家民委重点实验室（北方民族大学），银川 750021

摘要：约束满足问题（CSP）是理论计算机科学领域的组合优化问题，可满足性问题（SAT问题）作为CSP中的一种特殊情形，是理论计算机科学、数理逻辑和人工智能等领域十分关注的热点问题。相变是SAT问题中存在的一种现象，而研究SAT问题的相变现象和相变机制对深入认识SAT问题的难解本质和一般数学现象以及设计更高效的算法求解SAT问题有重要的指导意义。因此，根据近年来国内外学者针对SAT问题的相变现象取得的一些重要研究成果，首先介绍了SAT问题相变的相关知识以及SAT问题的概率分析方法和实例生成模型，其次总结并分析了SAT问题的不可满足相变和可满足相变这两种相变的相变点求解方法和相变阈值，最后展望了SAT问题相变的研究趋势。

关键词：可满足性问题,概率分析方法,实例生成模型,不可满足相变,可满足相变

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