随机约束满足问题相变研究综述

来源：计算机工程与科学杂志2022年第7期北京时间：

作者：牛鹏飞, 王晓峰, 芦磊, 张九龙

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

摘要：随机约束满足问题是经典的NP完全问题，在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象，近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手，从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。

关键词：随机约束满足问题,随机可满足问题,随机图着色问题,相变,

基金资助：国家自然科学基金(62062001,61762019,61862051,61962002)；宁夏自然科学基金(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119);北方民族大学重大专项(ZDZX201901)