2-3-sat问题相变现象剖析及其应用

3-sat问题有一个非常奇妙的相变现象.对于固定的变量数n，合取范式的可满足概率随着子句个数k的变化而发生剧烈的变化;当k≈4.3*n时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了sat问题的更一般形式，即2-3-sat问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系，发现了2-子句和3-子句在约束能力意义下的当量关系，并提出了如何有效地利用2-3-sat的相变现象.