%0 Journal Article
%T Analysis for Phase Transition of the 2-3-SAT Problem<br>2-3-SAT问题相变现象剖析及其应用
%A BAI Shuo
%A BU Dong-bo
%A <br>白　硕
%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<br>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