摘要: Phase transition is an important feature of SAT problem. For randomk-SAT model, it proved that asr (ratio clauses to variables) increases, the structure solutions will undergo a sudden change like satisfiability phase whenr reaches threshold point (r=r σ ). This phenomenon shows satisfying truth assignments suddenly shift from being relatively different each other very similar other.
springer.com
harvard.edu
cnki.com.cn参考文章(7)
David A. Clark, Jeremy Frank, Ian P. Gent, Ewan MacIntyre, Neven Tomov, Toby Walsh, Local search and the number of solutions principles and practice of constraint programming. pp. 119- 133 ,(1996) , 10.1007/3-540-61551-2_70
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou, Approximating the unsatisfiability threshold of random formulas Random Structures and Algorithms. ,vol. 12, pp. 253- 269 ,(1998) , 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U
Tad Hogg, Bernardo A. Huberman, Colin P. Williams, Phase transitions and the search problem Artificial Intelligence. ,vol. 81, pp. 1- 15 ,(1996) , 10.1016/0004-3702(95)00044-5
O Dubois, Y Boufkhad, A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae Journal of Algorithms. ,vol. 24, pp. 395- 420 ,(1997) , 10.1006/JAGM.1997.0867
Bart Selman, Scott Kirkpatrick, Critical behavior in the computational cost of satisfiability testing Artificial Intelligence. ,vol. 81, pp. 273- 295 ,(1996) , 10.1016/0004-3702(95)00056-9
Toby Walsh, Ian P. Gent, The SAT phase transition european conference on artificial intelligence. pp. 105- 109 ,(1994)
Li Wei, A mathematic-physical approach to the satisfiability problem 中国科学A辑(英文版). ,(1995)