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

摘要/Abstract

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

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

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

牛鹏飞, 王晓峰, 芦磊, 张九龙. 随机约束满足问题相变研究综述[J]. 计算机工程与科学, 2022, 44(07): 1321-1330.

NIU Peng-fei, WANG Xiao-feng, LU Lei, ZHANG Jiu-long. Review of phase transition of random constraint satisfaction problems[J]. Computer Engineering & Science, 2022, 44(07): 1321-1330.

参考文献［62］

［1］	Guo Bing-hui. The complexity and dynamics in phase transition of random systems［D］. Beijing; Beijing University of Aeronautics and Astronautics, 2010.(in Chinese)
［2］	Cheeseman P, Kanefsky B, Taylor W M. Where the really hard problems are［C］∥Proc of the 12th International Joint Conference on Artificial Intelligence, 1991:331-337.
［3］	Karp R M. Reducibility among combinatorial problem ［M］∥Complexity of Computer Computations. Boston, MA:Springer, 1972:85-103.
［4］	Cook S A. The complexity of theorem-proving procedures［C］∥Proc of the 3rd Annual ACM Symposium on Theory of Computing ,1971:151-158.
［5］	Erds P, Rényi A. On the evolution of random graphs［M］∥The Structure and Dynamics of Networks. Princeton,NJ:Princeton University Press, 2011:38-82.
［6］	Lu You-jun, Xu Dao-yun. Phase transition properties of k-independent sets in random graphs［J］. Journal of Computer Research and Development, 2017,54(12):2843-2850.(in Chinese)
［7］	Achlioptas D, Friedgut E. A sharp threshold for k-colorability［J］. Random Structures & Algorithms, 1999, 14(1):63-70.
［8］	Mézard M, Montanari A. Information, physics, and computation［M］. Oxford:Oxford University Press, 2009.
［9］	Mézard M, Parisi G, Zecchina R. Analytic and algorithmic solution of random satisfiability problems［J］. Science, 2002, 297(5582):812-815.
［10］	Braunstein A, Mézard M, Zecchina R. Survey propagation:An algorithm for satisfiability［J］. Random Structures & Algorithms, 2005, 27(2):201-226.
［11］	Krzkaa F, Zdeborov L. Phase transitions and computational difficulty in random constraint satisfaction problems［J］. Journal of Physics:Conference Series, 2008, 95:012012.
［12］	Zdeborov L, Krzkaa F. Phase transitions in the coloring of random graphs［J］. Physical Review E, 2007, 76(3):031131.
［13］	Budzynski L, Semerjian G. Biased measures for random constraint satisfaction problems:Larger interaction range and asymptotic expansion［J］. Journal of Statistical Mechanics:Theory and Experiment, 2020, 10:103406.
［14］	van Mourik J, Saad D. Random graph coloring:Statistical physics approach［J］. Physical Review E, 2002, 66(5):056120.
［15］	Boettcher S, Percus A G. Extremal optimization at the phase transition of the three-coloring problem［J］. Physical Review E, 2004, 69(6):066703.
［16］	Achlioptas D, Moore C. Almost all graphs with average degree 4 are 3-colorable［J］. Journal of Computer and System Sciences, 2003, 67(2):441-471.
［17］	Krzkaa F, Pagnani A, Weigt M. Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs［J］. Physical Review E, 2004, 70(4):046705.
［18］	Bapst V, Coja-Oghlan A, Hetterich S, et al. The condensation phase transition in random graph coloring［J］. Communications in Mathematical Physics, 2016, 341(2):543-606.
［19］	Molloy M. The freezing threshold for k-colorings of a random graph［J］. Journal of the ACM, 2018, 65(2):1-62.
［20］	Coja-Oghlan A, Vilenchik D. Chasing the k-colorability threshold［C］∥Proc of 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013:380-389.
［21］	Coja-Oghlan A. Upper-bounding the k-colorability threshold by counting covers［J］. arXiv:1305.0177, 2013.
［22］	Kaporis A C, Kirousis L M, Stamatiou Y C. A note on the non-colorability threshold of a random graph［J］. The Electronic Journal of Combinatorics, 2000, 7:R29.
［23］	Zhou Jin-cheng. A study on the satisfiability problem of the regular random formulas［D］. Guiyang:Guizhou University, 2016. (in Chinese)
［24］	Achlioptas D, Ricci-Tersenghi F. On the solution-space geometry of random constraint satisfaction problems［C］∥Proc of the 38th Annual ACM Symposium on Theory of Computing, 2006:130-139.
［25］	Zeng Y, Zhou H J. Solution space coupling in the random k-satisfiability problem［J］. Communications in Theoretical Physics, 2013, 60(3):363-374.
［26］	Zhou H, Ma H. Communities of solutions in single solution clusters of a random k-satisfiability formula［J］. Physical Review E, 2009, 80(6):066108.
［27］	Mézard M, Mora T, Zecchina R. Clustering of solutions in the random satisfiability problem［J］. Physical Review Letters, 2005, 94(19):197205.
［28］	Krzkaa F, Montanari A, Ricci-Tersenghi F, et al. Gibbs states and the set of solutions of random constraint satisfaction problems［J］. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(25):10318-10323.
［29］	Montanari A, Ricci-Tersenghi F, Semerjian G. Clusters of solutions and replica symmetry breaking in random k- satisfiability［J］. Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008:P04004.
［30］	Davis M, Putnam H. A computing procedure for quantification theory［J］. Journal of the ACM, 1960, 7(3):201-215.
［31］	Crawford J M, Auton L D. Experimental results on the crossover point in random 3-SAT［J］. Artificial Intelligence, 1996, 81(1-2):31-57.
［32］	Monasson R, Zecchina R, Kirkpatrick S, et al. Determin- ing computational complexity from characteristic ‘phase transitions’［J］. Nature, 1999, 400(6740):133-137.
［33］	Mann A, Hartmann A K. Numerical solution-space analysis of satisfiability problems［J］. Physical Review E, 2010, 82(5):056702.
［34］	Kirkpatrick S, Selman B. Critical behavior in the satisfiability of random boolean expressions［J］. Science, 1994, 264(5163):1297-1301.
［35］	Chao M T, Franco J. Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem［J］. Information Sciences, 1990, 51(3):289-314.
［36］	Chvtal V, Reed B. Mick gets some (the odds are on his side)(satisfiability)［C］∥Proc of the 33rd Annual Sympo- sium on Foundations of Computer Science, 1992:620-627.
［37］	Broder A Z, Frieze A M, Upfal E. On the satisfiability and maximum satisfiability of random 3-CNF formulas［C］∥Proc of the 4th Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993:322-330.
［38］	Frieze A, Suen S. Analysis of two simple heuristics on a random instance of k-SAT［J］. Journal of Algorithms, 1996, 20(2):312-355.
［39］	Achlioptas D. Setting 2 variables at a time yields a new lower bound for random 3-SAT［C］∥Proc of the 32nd Annual ACM Symposium on Theory of Computing, 2000:28-37.
［40］	Achioptas D, Sorkin G B. Optimal myopic algorithms for random 3-SAT［C］∥Proc of the 41st Annual Symposium on Foundations of Computer Science, 2000:590-600.
［41］	Kaporis A C, Kirousis L M, Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm［J］. Random Structures & Algorithms, 2006, 28(4):444-480.
［42］	Kaporis A C, Kirousis L M, Lalas E. Selecting complementary pairs of literals［J］. Electronic Notes in Discrete Mathematics, 2003, 16:47-70.
［43］	Gent I P, Walsh T. The SAT phase transition［C］∥ Proc of the 11th European Conference on Artificial Intelligence, 1994:105-109.
［44］	Kim J H. Poisson cloning model for random graphs［J］. arXiv:0805.4133, 2007.
［45］	Coja-Oghlan A, Feige U, Frieze A, et al. On smoothed k-CNF formulas and the Walksat algorithm［C］∥Proc of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 2009:451-460.
［46］	Semerjian G, Monasson R. A study of pure random walk on random satisfiability problems with “physical” methods［C］∥ Proc of International Conference on Theory and Applications of Satisfiability Testing, 2003:120-134.
［47］	Monasson R, Zecchina R. Entropy of the k-satisfiability problem［J］. Physical Review Letters, 1996, 76(21):3881.
［48］	Mézard M, Zecchina R. Random k-satisfiability problem:From an analytic solution to an efficient algorithm［J］. Physical Review E, 2002, 66(5):056126.
［49］	Mertens S, Mézard M, Zecchina R. Threshold values of random k‐SAT from the cavity method［J］. Random Structures & Algorithms, 2006, 28(3):340-373.
［50］	Lundow P H, Markstrm K. Revisiting the cavity-method threshold for random 3-SAT［J］. Physical Review E, 2019,99(2):022106.
［51］	Franco J, Paull M. Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem［J］. Discrete Applied Mathematics, 1983, 5(1):77-87.
［52］	El Maftouhi A, de la Vega W F. On random 3-SAT［J］. Combinatorics, Probability and Computing, 1995, 4(3):189-195.
［53］	Kamath A, Motwani R, Palem K, et al. Tail bounds for occupancy and the satisfiability threshold conjecture［J］. Random Structures & Algorithms, 1995, 7(1):59-80.
［54］	Dubois O, Boufkhad Y. A general upper bound for the satisfiability threshold of randomr-SAT formulae［J］. Journal of Algorithms, 1997, 24(2):395-420.
［55］	Kirousis L M, Kranakis E, Krizanc D, et al. Approximating the unsatisfiability threshold of random formulas［J］. Random Structures & Algorithms, 1998, 12(3):253-269.
［56］	Janson S, Stamatiou Y C, Vamvakari M. Bounding the unsatisfiability threshold of random 3‐SAT［J］. Random Structures & Algorithms, 2000, 17(2):103-116.
［57］	Kaporis A C, Kirousis L M, Stamatiou Y C, et al. Coupon collectors, q-binomial coefficients and the unsatisfiability threshold［C］∥Proc of Italian Conference on Theoretical Computer Science, 2001:328-338.
［58］	Dubois O, Boufkhad Y, Mandler J. Typical random 3-SAT formulae and the satisfiability threshold［C］∥Proc of the 11th ACM-SIAM Symposium on Discrete Algorithms, 2000:124-126.
［59］	Díaz J, Kirousis L, Mitsche D, et al. On the satisfiability threshold of formulas with three literals per clause［J］. Theoretical Computer Science, 2009, 410:30-32.
［60］	Achlioptas D, Moore C. Random k-SAT:Two moments suffice to cross a sharp threshold［J］.SIAM Journal on Computing, 2006,36(1):740-762.
［61］	Achlioptas D, Peres Y. The threshold for random k-sat is 2k (ln 2-o(k))［C］∥Proc of the 35th Annual ACM Symposium on Theory of Computing, 2003:223-231.
［62］	Liu Jun. Several studies about exact phase transition in random constraint satisfaction problem［D］. Beijing; Beijing University of Aeronautics and Astronautics, 2014. (in Chinese)
［63］	Coja-Oglan A, Panagiotou K. Catching the k-NAESAT threshold［C］∥Proc of the 44th Annual ACM Symposium on Theory of Computing, 2012:899-908.
［64］	Coja-Oghlan A, Panagiotou K. The asymptotic k-SAT threshold［J］. Advances in Mathematics, 2016, 288:985-1068.
［65］	Ding J, Sly A, Sun N. Proof of the satisfiability conjecture for large k［C］∥Proc of the 47th Annual ACM Symposium on Theory of Computing, 2015:59-68.
	附中文参考文献:
［1］	郭炳晖. 随机系统相变的复杂性及动力学研究［D］.北京:北京航空航天大学, 2010.
［6］	卢友军, 许道云. 随机图中k-独立集的相变性质［J］.计算机研究与发展,2017,54(12):2843-2850.
［23］	周锦程. 随机正则公式的满足性问题研究［D］.贵阳:贵州大学, 2016.
［62］	刘军. 关于约束满足问题精确相变的若干研究［D］.北京:北京航空航天大学, 2014.