%0 Journal Article %T Analysis for Phase Transition of the 2-3-SAT Problem
2-3-SAT问题相变现象剖析及其应用 %A BAI Shuo %A BU Dong-bo %A
白 硕 %A 卜东波 %J 软件学报 %D 1998 %I %X 3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N,合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式,即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系,发现了2-子句和3-子句在约束能力意义下的当量关系,并提出了如何有效地利用2-3-SAT的相变现象. %K SAT problem %K 2-3-SAT %K phase transition %K 2-3-ratio %K constraint power
NP完全问题 %K 合取范式 %K SAT问题 %K 相变现象 %K 可满足概率 %K 2-3-当量. %U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=D17B59D20DBA8E8FAA02DA3F52487656&yid=8CAA3A429E3EA654&vid=9CF7A0430CBB2DFD&iid=708DD6B15D2464E8&sid=E0FF0FB27B45F84E&eid=AB1DE136C335A86C&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=7