计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (07): 1321-1330.
• 人工智能与数据挖掘 • 上一篇
牛鹏飞1,王晓峰1,2,芦磊1,张九龙1
收稿日期:
2021-10-18
修回日期:
2021-12-26
接受日期:
2022-07-25
出版日期:
2022-07-25
发布日期:
2022-07-25
基金资助:
NIU Peng-fei1,WANG Xiao-feng1,2,LU Lei1,ZHANG Jiu-long1
Received:
2021-10-18
Revised:
2021-12-26
Accepted:
2022-07-25
Online:
2022-07-25
Published:
2022-07-25
摘要: 随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。
牛鹏飞, 王晓峰, 芦磊, 张九龙. 随机约束满足问题相变研究综述[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.
[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] | Erds 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] | Chvtal 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, Markstrm 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. |
No related articles found! |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
湘公网安备 43010502000083号
湘ICP备10006030号
版权所有 © 《计算机工程与科学》 编辑部
地址:中国湖南省长沙市开福区德雅路109号(410073) 电话:0731-87002567 Email: jsjgcykx@vip.163.com
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn