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

Abstract: 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.

Key words: random constraint satisfaction problem, random satisfiability problem, random graph coloring problem, phase transition