Page 16 - 《软件学报》2021年第9期

2640 Journal of Software 软件学报 Vol.32, No.9, September 2021

取定时的可满足临界.通过构造一个特殊随机实验以及使用一阶矩方法,我们得到了该可满足临界值的一个下
界.随后进行的模拟实验结果,验证了理论证明所得下界的正确性.
需要说明的是:从模拟实验结果看,本文所得下界仍然比较粗糙,需要进一步改进.此外,研究讨论该可满足
临界值的上界以确定 SAT-UNSAT 相变点也十分必要.这些工作将为研究参数 d 如何影响公式求解难度以及设
计随机难解实例生成算法奠定基础.

References:
[1] Levin LA. Universal sequential search problems. Problemy Peredachi Informatsii, 1973,9(3):115−116.
[2] Friedgut E, Bourgain J. Sharp thresholds of graph properties, and the k-sat problem. Journal of the American Mathematical Society,
1999,12(4):1017−1054. [doi: 10.1090/S0894-0347-99-00305-7]
[3] Kaporis AC, Kirousis LM, Lalas EG. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures &
Algorithms, 2006,28(4):444−480. [doi: 10.1002/rsa.20104]
[4] Díaz J, Kirousis L, Mitsche D, Pérez-Giménez X. On the satisfiability threshold of formulas with three literals per clause.
Theoretical Computer Science, 2009,410(30-32):2920−2934. [doi: 10.1016/j.tcs.2009.02.020]
[5] Lundow PH, Markström K. Revisiting the cavity-method threshold for random 3-SAT. Physical Review E, 2019,99(2):022106(5).
[6] Crawford JM, Auton LD. Experimental results on the crossover point in random 3-SAT. Artificial Intelligence, 1996,81(1-2):31−57.
[doi: 10.1016/0004-3702(95)00046-1]
[7] Selman B, Kirkpatrick S. Critical behavior in the computational cost of satisfiability testing. Artificial Intelligence, 1996,81(1-2):
273−295. [doi: 10.1016/0004-3702(95)00056-9]
[8] Monasson R, Zecchina R, Kirkpatrick S, Selman B, Troyansky L. Determining computational complexity from characteristic ‘phase
transitions’. Nature, 1999,400(6740):133−137. [doi: 10.1038/22055]
[9] Braunstein A, Mézard M, Zecchina R. Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms, 2002,
27(2):201−226. [doi: 10.1002/rsa.20057]
[10] Xu DY, Wang XF. A regular NP-complete problem and its inapproximability. Journal of Frontiers of Computer Science and
Technology, 2013,7(8):691−697 (in Chinese with English abstract). [doi: 10.3778/j.issn.1673-9418.1305025]
[11] Zhou JC, Xu DY, Lu YJ, Dai CK. Strictly regular random (3,s)-SAT model and its phase transition phenomenon. Journal of Beijing
University of Aeronautics and Astronautics, 2016,42(12):2563−2571 (in Chinese with English abstract). [doi: 10.13700/j.bh.1001-
5965.2015.0845]
[12] Mahajan YS, Fu ZH, Malik S. Zchaff2004: An efficient SAT solver. In: Hoos HH, Mitchell DG, eds. Theory & Applications of
Satisfiability Testing. Berlin: Springer-Verlag, 2004. 360−375. [doi: 10.1007/11527695_27]
[13] Zhou JC, Xu DY, Lu YJ. Satisfiability threshold of the regular random (k,r)-SAT problem. Ruan Jian Xue Bao/Journal of Software,
2016,27(12):2985−2993 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5129.htm [doi: 10.13328/j.cnki.jos.
005129]
[14] Sumedha, Krishnamurthy S, Sahoo S. Balanced k-satisfiability and biased random k-satisfiability on trees. Physical Review E, 2013,
87(4):042130(9). [doi: 10.1103/PhysRevE.87.042130]
[15] Zhou JC, Xu DY, Lu YJ. Satisfiability threshold of regular (k,r)-SAT problem via 1RSB theory. Journal of Huazhong University of
Science and Technology (Natural Science Edition), 2017,45(12):7−13 (in Chinese with English abstract). [doi: 10.13245/j.hust.
171202]
[16] Coja-Oghlan A, Wormald N. The number of satisfying assignments of random regular k-SAT formulas. Combinatorics, Probability
and Computing, 2018,27:496−530. [doi: 10.1017/S0963548318000263]
[17] Boufkhad Y, Dubois O, Interian Y, Selman B. Regular random k-SAT: Properties of balanced formulas. Journal of Automated
Reasoning, 2005,35:181−200. [doi: 10.1007/978-1-4020-5571-3_9]
[18] Rathi V, Aurell E, Rasmussen L, Skoglund M. Bounds on threshold of regular random k-SAT. In: Strichman O, Szeider S, eds.
Theory & Applications of Satisfiability Testing-SAT 2010. Berlin: Springer-Verlag, 2010. 264−277. [doi: 10.1007/978-3-642-
14186-7_22]