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

Review of phase transition of random constraint satisfaction problems

作　　者：牛鹏飞 王晓峰[1,2] 芦磊 张九龙 NIU Peng-fei;WANG Xiao-feng;LU Lei;ZHANG Jiu-long(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021;The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021

出　　处：《计算机工程与科学》2022年第7期1321-1330,共10页Computer Engineering & Science

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

摘　　要：随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。Random constraint satisfaction problem is a classical NP complete problem,which is widely used in theoretical research and real life.The random constraint satisfaction problem has phase transition phenomenon.In recent decades,the research results of phase transitions on this issue have continuously emerged.In this paper,random graph coloring problem and random satisfiability problem are selected,which are classical constraint satisfaction problems.Based on the method from algorithm research,statistical physic,mathematical proof,this paper summarizes and reviews the research results on phase transition of random graph coloring problem and random satisfiability problem.Finally,we provided a suggestion for the direction of future development.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]